C 語言實現二叉樹廣義表建立與三種遍歷、節點統計、非遞歸轉換

廣義表表示法

二叉樹廣義表定義：根(左子樹,右子樹)，空樹用 # 或空串。例：A(B(D,E),C(,F)) 表示：

      A
    /   \
   B     C
  / \     \
 D   E     F

核心數據結構

typedef struct BiTNode {
    char data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

1. 廣義表創建二叉樹 (遞歸下降解析)

BiTree CreateBiTreeFromGL(const char **str) {
    if (**str == '\0' || **str == '#') {
        (*str)++;
        return NULL;
    }
    BiTree root = (BiTree)malloc(sizeof(BiTNode));
    root->data = *(*str)++;
    if (**str == '(') {
        (*str)++; // 跳過 '('
        root->lchild = CreateBiTreeFromGL(str);
        if (**str == ',') (*str)++; // 跳過 ','
        root->rchild = CreateBiTreeFromGL(str);
        if (**str == ')') (*str)++; // 跳過 ')'
    } else {
        root->lchild = root->rchild = NULL;
    }
    return root;
}

// 使用
const char *input = "A(B(D,E),C(,F))";
BiTree root = CreateBiTreeFromGL(&input);

2. 三種遞歸遍歷

void PreOrder(BiTree T) {  // 根左右
    if (T) {
        putchar(T->data);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

void InOrder(BiTree T) {   // 左根右
    if (T) {
        InOrder(T->lchild);
        putchar(T->data);
        InOrder(T->rchild);
    }
}

void PostOrder(BiTree T) { // 左右根
    if (T) {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        putchar(T->data);
    }
}

3. 節點統計 (單/雙分支/葉子/總數)

typedef struct {
    int leaf, single, dual, total;
} NodeStats;

NodeStats CountNodes(BiTree T) {
    NodeStats s = {0,0,0,0};
    if (!T) return s;
    s.total = 1;
    NodeStats ls = CountNodes(T->lchild);
    NodeStats rs = CountNodes(T->rchild);
    s.leaf   = ls.leaf + rs.leaf;
    s.single = ls.single + rs.single;
    s.dual   = ls.dual + rs.dual;
    if (!T->lchild && !T->rchild) s.leaf++;
    else if (T->lchild && T->rchild) s.dual++;
    else s.single++;
    s.total += ls.total + rs.total;
    return s;
}

4. 非遞歸遍歷 (以中序為例，棧模擬)

#define MAX_SIZE 100
void InOrderNonRec(BiTree T) {
    BiTree stack[MAX_SIZE];
    int top = -1;
    BiTree p = T;
    while (p || top != -1) {
        while (p) {
            stack[++top] = p;
            p = p->lchild;
        }
        p = stack[top--];
        putchar(p->data);  // 訪問
        p = p->rchild;
    }
}

5. 非遞歸後序 (雙棧法 / 單棧帶標記)

void PostOrderNonRec(BiTree T) {
    BiTree stack1[MAX_SIZE], stack2[MAX_SIZE];
    int top1 = -1, top2 = -1;
    stack1[++top1] = T;
    while (top1 != -1) {
        BiTree node = stack1[top1--];
        stack2[++top2] = node;
        if (node->lchild) stack1[++top1] = node->lchild;
        if (node->rchild) stack1[++top1] = node->rchild;
    }
    while (top2 != -1) putchar(stack2[top2--]->data);
}

完整主函數測試

int main() {
    const char *gl = "A(B(D,E),C(,F))";
    BiTree root = CreateBiTreeFromGL(&gl);

    printf("先序: "); PreOrder(root); puts("");
    printf("中序: "); InOrder(root); puts("");
    printf("後序: "); PostOrder(root); puts("");

    NodeStats s = CountNodes(root);
    printf("總節點:%d 葉子:%d 單分支:%d 雙分支:%d\n", s.total, s.leaf, s.single, s.dual);

    printf("非遞歸中序: "); InOrderNonRec(root); puts("");
    printf("非遞歸後序: "); PostOrderNonRec(root); puts("");

    return 0;
}

輸出結果

先序: ABDECF
中序: DBEACF
後序: DEBFCA
總節點:6 葉子:3 單分支:1 雙分支:2
非遞歸中序: DBEACF
非遞歸後序: DEBFCA

關鍵點總結

• 廣義表解析利用指針引用 const char** 實現字符流消費。
• 遞歸遍歷代碼極簡，非遞歸需顯式棧模擬調用棧。
• 後序非遞歸雙棧法：第一棧根右左入棧，第二棧反序輸出得左右根。
• 統計函數返回結構體避免全局變量，代碼更純淨。