C語言實現通用樹結構：節點定義、鏈表存儲、增刪查與遍歷顯示

樹的基本概念

• 樹 = 有限節點集，n=0 為空樹；n>0 有唯一根節點，其餘分為 m 棵互不相交的子樹。
• 節點屬性：資料、父節點指標、子節點鏈表（因子樹數量不固定）。
• 樹的儲存：用「先序遍歷序列」形成一條總鏈表，每個節點同時掛在父節點的子鏈表中。

資料結構定義

typedef struct _GTreeNode {
    void* data;
    struct _GTreeNode* parent;
    LinkList* child; // 子節點鏈表
} GTreeNode;

typedef struct _TLNode { // 總鏈表節點
    LinkListNode header;
    GTreeNode* node;
} TLNode;

typedef LinkList GTree; // 樹即總鏈表

核心操作實作

建立樹

GTree* GTree_Create() { return LinkList_Create(); }

插入節點

int GTree_Insert(GTree* tree, void* data, int parentPos) {
    LinkList* list = (LinkList*)tree;
    if (!list || !data || parentPos >= LinkList_Length(list)) return 0;

    TLNode* treeNode = malloc(sizeof(TLNode));
    TLNode* childNode = malloc(sizeof(TLNode));
    GTreeNode* gnode = malloc(sizeof(GTreeNode));
    if (!treeNode || !childNode || !gnode) { free all; return 0; }

    gnode->data = data;
    gnode->parent = NULL;
    gnode->child = LinkList_Create();

    treeNode->node = gnode;
    childNode->node = gnode;

    LinkList_Insert(list, (LinkListNode*)treeNode, LinkList_Length(list)); // 加入總表

    if (parentPos >= 0) {
        TLNode* pNode = (TLNode*)LinkList_Get(list, parentPos);
        gnode->parent = pNode->node;
        LinkList_Insert(pNode->node->child, (LinkListNode*)childNode,
                        LinkList_Length(pNode->node->child));
    }
    return 1;
}

刪除節點（遞歸刪除子孫）

void* GTree_Delete(GTree* tree, int pos) {
    TLNode* tn = (TLNode*)LinkList_Get(tree, pos);
    if (!tn) return NULL;
    void* data = tn->node->data;
    recursive_delete(tree, tn->node);
    return data;
}

static void recursive_delete(LinkList* list, GTreeNode* node) {
    // 從總表移除
    for (int i=0; inode == node) { LinkList_Delete(list, i); free(tn); break; }
    }
    // 從父節點子表移除
    if (node->parent) {
        for (int i=0; iparent->child); i++) {
            TLNode* tn = (TLNode*)LinkList_Get(node->parent->child, i);
            if (tn->node == node) { LinkList_Delete(node->parent->child, i); free(tn); break; }
        }
    }
    // 遞歸刪除所有子節點
    while (LinkList_Length(node->child) > 0) {
        TLNode* cn = (TLNode*)LinkList_Get(node->child, 0);
        recursive_delete(list, cn->node);
    }
    LinkList_Destroy(node->child);
    free(node);
}

查詢、高度、度、節點數

void* GTree_Get(GTree* tree, int pos) {
    TLNode* tn = (TLNode*)LinkList_Get(tree, pos);
    return tn ? tn->node->data : NULL;
}
void* GTree_Root(GTree* tree) { return GTree_Get(tree, 0); }
int GTree_Count(GTree* tree) { return LinkList_Length(tree); }

int GTree_Height(GTree* tree) {
    TLNode* tn = (TLNode*)LinkList_Get(tree, 0);
    return tn ? recursive_height(tn->node) : 0;
}
static int recursive_height(GTreeNode* node) {
    if (!node) return 0;
    int h = 0;
    for (int i=0; ichild); i++) {
        TLNode* cn = (TLNode*)LinkList_Get(node->child, i);
        h = max(h, recursive_height(cn->node));
    }
    return h + 1;
}

int GTree_Degree(GTree* tree) {
    TLNode* tn = (TLNode*)LinkList_Get(tree, 0);
    return tn ? recursive_degree(tn->node) : -1;
}
static int recursive_degree(GTreeNode* node) {
    if (!node) return -1;
    int d = LinkList_Length(node->child);
    for (int i=0; ichild); i++) {
        TLNode* cn = (TLNode*)LinkList_Get(node->child, i);
        d = max(d, recursive_degree(cn->node));
    }
    return d;
}

樹的圖形化顯示

void GTree_Display(GTree* tree, void (*printf)(void*), int gap, char div) {
    TLNode* tn = (TLNode*)LinkList_Get(tree, 0);
    if (tn && printf) recursive_display(tn->node, printf, 0, gap, div);
}
static void recursive_display(GTreeNode* node, void (*pf)(void*), int fmt, int gap, char div) {
    for (int i=0; idata); putchar('\n');
    for (int i=0; ichild); i++) {
        TLNode* cn = (TLNode*)LinkList_Get(node->child, i);
        recursive_display(cn->node, pf, fmt+gap, gap, div);
    }
}

測試主程式與輸出

void print_char(void* d) { putchar((int)d); }

int main() {
    GTree* t = GTree_Create();
    GTree_Insert(t, (void*)'A', -1);
    GTree_Insert(t, (void*)'B', 0);
    GTree_Insert(t, (void*)'C', 0);
    GTree_Insert(t, (void*)'D', 0);
    GTree_Insert(t, (void*)'E', 1);
    GTree_Insert(t, (void*)'F', 1);
    GTree_Insert(t, (void*)'H', 3);
    GTree_Insert(t, (void*)'I', 3);
    GTree_Insert(t, (void*)'J', 3);

    printf("Height: %d\n", GTree_Height(t)); // 3
    printf("Degree: %d\n", GTree_Degree(t)); // 3
    GTree_Display(t, print_char, 2, ' ');

    GTree_Delete(t, 3); // 刪除 D 及其子樹 H,I,J
    GTree_Display(t, print_char, 2, '-');

    GTree_Clear(t);
    GTree_Destroy(t);
    return 0;
}

輸出：
Height: 3
Degree: 3
A
  B
    E
    F
  C
  D
    H
    I
    J
A
--B
----E
----F
--C

設計要點總結

1. 雙鏈表結構：總表支援按序號訪問，子表維護父子關係。
2. 插入/刪除需同步維護兩張表，recursive_delete 確保子孫連帶清理。
3. 高度/度用遞歸後序遍歷計算。
4. 泛型 void* 適配任意資料型別，配合回呼函式顯示。