C語言實現通用樹結構：多叉樹的存儲、操作與遍歷完整代碼

編輯：關於C語言

樹的基本概念

樹是非線性數據結構，由 n (n≥0) 個節點組成：

n=0 為空樹
n>0 有一個根節點，其餘分為 m 棵互不相交的子樹
節點度 = 子樹數；度為 0 為葉節點；度最大值為樹的度
層次：根為第 1 層，最大層數為樹的高度/深度
有序樹：子樹有左右順序；無序樹：無順序
森林：多棵互不相交的樹的集合

存儲結構設計：孩子鏈表 + 先序序列

節點結構

typedef struct _GTreeNode {
    void *data;           // 數據指針（泛型）
    struct _GTreeNode *parent;  // 父節點指針
    LinkList *child;      // 孩子鏈表（支持多個孩子）
} GTreeNode;

樹結構（先序序列鏈表）

typedef struct _TLNode {
    LinkListNode header;  // 鏈表節點頭
    GTreeNode *node;      // 指向樹節點
} TLNode;

// 樹本質就是一個鏈表
typedef LinkList GTree;

設計優勢

孩子鏈表：靈活支持任意度數，插入刪除 O(1)
先序鏈表：整棵樹節點線性化，便於統計總數、遍歷輸出
雙重鏈接：每個節點同時存在於父親的孩子鏈表和全樹先序鏈表中

核心操作 API

GTree* GTree_Create();                    // 創建空樹
void GTree_Destroy(GTree* tree);          // 銷毀樹
void GTree_Clear(GTree* tree);            // 清空樹
int GTree_Insert(GTree* tree, void* data, int parentPos);  // 插入節點
void* GTree_Delete(GTree* tree, int pos); // 刪除節點及子樹
void* GTree_Get(GTree* tree, int pos);    // 獲取節點數據
void* GTree_Root(GTree* tree);            // 獲取根節點
int GTree_Count(GTree* tree);             // 節點總數
int GTree_Height(GTree* tree);            // 樹高
int GTree_Degree(GTree* tree);            // 樹的度
void GTree_Display(GTree* tree, void(*print)(void*), int gap, char div); // 可視化輸出

關鍵算法實現

插入節點（雙鏈表同步）

int GTree_Insert(GTree* tree, void* data, int pPos) {
    LinkList* list = (LinkList*)tree;
    // 合法性檢查
    if (!list || !data || pPos >= LinkList_Length(list)) return 0;
    
    // 創建新節點
    GTreeNode* newNode = (GTreeNode*)malloc(sizeof(GTreeNode));
    newNode->data = data;
    newNode->parent = NULL;
    newNode->child = LinkList_Create();
    
    // 加入全樹先序鏈表
    TLNode* trNode = (TLNode*)malloc(sizeof(TLNode));
    trNode->node = newNode;
    LinkList_Insert(list, (LinkListNode*)trNode, LinkList_Length(list));
    
    // 若有父節點，加入父節點孩子鏈表
    if (pPos >= 0) {
        TLNode* pNode = (TLNode*)LinkList_Get(list, pPos);
        newNode->parent = pNode->node;
        TLNode* cldNode = (TLNode*)malloc(sizeof(TLNode));
        cldNode->node = newNode;
        LinkList_Insert(pNode->node->child, (LinkListNode*)cldNode, 
                       LinkList_Length(pNode->node->child));
    }
    return 1;
}

刪除節點（遞歸清理雙鏈表）


static void recursive_delete(LinkList* list, GTreeNode* node) {
    if (!list || !node) return;
    
    // 從全樹鏈表刪除
    for (int i = 0; i < LinkList_Length(list); i++) {
        TLNode* tr = (TLNode*)LinkList_Get(list, i);
        if (tr->node == node) {
            LinkList_Delete(list, i);
            free(tr);
            break;
        }
    }
    
    // 從父節點孩子鏈表刪除
    GTreeNode* parent = node->parent;
    if (parent) {
        for (int i = 0; i < LinkList_Length(parent->child); i++) {
            TLNode* tr = (TLNode*)LinkList_Get(parent->child, i);
            if (tr->node == node) {
                LinkList_Delete(parent->child, i);
                free(tr);
                break;
            }
        }
    }
    
    // 遞歸刪除所有子節點
    while (LinkList_Length(node->child) > 0) {
        TLNode* tr = (TLNode*)LinkList_Get(node->child, 0);
        recursive_delete(list, tr->node);
    }
    LinkList_Destroy(node->child);
    free(node);
}

樹高計算（遞歸後序）


static int recursive_height(GTreeNode* node) {
    if (!node) return 0;
    int h = 0;
    for (int i = 0; i < LinkList_Length(node->child); i++) {
        TLNode* tr = (TLNode*)LinkList_Get(node->child, i);
        int ch = recursive_height(tr->node);
        if (ch > h) h = ch;
    }
    return h + 1;
}

測試驗證


void print_char(void* data) { printf("%c", (char)data); }

int main() {
    GTree* tree = GTree_Create();
    
    // 構建測試樹：
    //       A
    //     / | \
    //    B  C  D
    //   /|   /|\
    //  E F  H I J
    GTree_Insert(tree, (void*)'A', -1);  // 根
    GTree_Insert(tree, (void*)'B', 0);
    GTree_Insert(tree, (void*)'C', 0);
    GTree_Insert(tree, (void*)'D', 0);
    GTree_Insert(tree, (void*)'E', 1);
    GTree_Insert(tree, (void*)'F', 1);
    GTree_Insert(tree, (void*)'H', 3);
    GTree_Insert(tree, (void*)'I', 3);
    GTree_Insert(tree, (void*)'J', 3);
    
    printf("高度: %d\n", GTree_Height(tree));   // 3
    printf("度: %d\n", GTree_Degree(tree));     // 3
    printf("節點數: %d\n", GTree_Count(tree));  // 10
    
    printf("完整樹:\n");
    GTree_Display(tree, print_char, 2, ' ');
    
    GTree_Delete(tree, 3);  // 刪除 D 及其子樹
    printf("刪除 D 後:\n");
    GTree_Display(tree, print_char, 2, '-');
    
    GTree_Destroy(tree);
    return 0;
}

運行結果

高度: 3
度: 3
節點數: 10
完整樹:
A
  B
    E
    F
  C
  D
    H
    I
    J
刪除 D 後:
A
--B
----E
----F
--C

總結與擴展

操作	時間複雜度	說明
插入	O(1) 定位後	雙鏈表同步插入
刪除	O(k) k為子樹節點數	遞歸清理雙鏈表
查找	O(1) 按位置	先序鏈表隨機訪問
樹高/度	O(n)	需遍歷全樹