二叉樹核心演算法 C 語言完整實現：遞歸與非遞歸遍歷、層序、屬性統計

資料結構定義

typedef char ElemType;
typedef struct tagBinaryTree {
    ElemType data;
    struct tagBinaryTree *lchild, *rchild;
} BTree;

輔助容器：循環佇列與動態棧

非遞歸演算法依賴兩大容器，原碼已提供完整實現：

• Queue：固定容量循環佇列，用於層序遍歷
• Stack：動態擴容順序棧，用於非遞歸深度優先遍歷

核心功能模組

1. 遞歸建樹 CreateBinaryTree()

先序輸入，# 表示空節點：

ABD##E##CF##G##  →  完整二叉樹

2. 三大深度優先遞歸遍歷

3. 層序遍歷 LevelOrderTraverse()

佇列 BFS，逐層由左至右訪問。

4. 樹屬性統計 (全遞歸)

• GetDepth()：樹高 = max(左高, 右高) + 1
• GetLeafCount()、GetCountOfOneDegree()、GetCountOfTwoDegree()、GetNodesCount()
• IsBalanceBinaryTree()：任意節點左右子樹高度差 ≤ 1
• TraverseLeafNodes()：僅輸出葉節點值
• GetLevelByValue()：查找節點層級 (根為第 1 層)
• SwapLeftRightSubtree()：鏡像翻轉整棵樹

5. 三大非遞歸遍歷 (棧模擬)

中序 NoneRecursionInOrder()

while (p || !IsStackEmpty(s)) {
    if (p) { Push(s, *p); p = p->lchild; }
    else   { Pop(s, &q); visit(q); p = q->rchild; }
}

先序 NoneRecursionPreOrder()

while (p || !IsStackEmpty(s)) {
    while (p) { visit(p); Push(s, *p); p = p->lchild; }
    Pop(s, &q); p = q->rchild;
}

後序 NoneRecursionPostOrder()

雙棧法：stack[] 存節點，tag[] 標記 0=左子樹已訪、1=右子樹已訪。

測試驅動 main()

讀取 test.txt (內容：ABC##DE#G##F###)，依序展示：

1. 建樹成功確認
2. 三種遞歸遍歷 + 層序 + 深度
3. 葉節點統計、度統計、總節點數
4. 平衡樹判定
5. 指定節點 (A-G, M) 層級查詢
6. 三種非遞歸遍歷驗證
7. 左右子樹交換前後對比

程式碼品質提升建議

• 移除 conio.h、getch() 非標準依賴
• IsBalanceBinaryTree() 重複計算深度 (O(n²))，可改為後序回傳高度並檢查 (O(n))
• GetLevelByValue() 若樹中有重複值會返回首次匹配層級，建議明確文檔化
• 非遞歸後序 tag[] 固定大小 STACK_INIT_SIZE，深度超過會溢出，應改用動態陣列
• 佇列容量 MAX_QUEUE_SIZE=10 過小，實際應動態分配或設為足夠大
• 錯誤碼 OK/ERROR/OVERFLOW 建議改用 enum 增強可讀性

複雜度總結