typedef char ElemType;
typedef struct Node {
ElemType data;
struct Node *lchild, *rchild;
} BTree;
#define OK 1
#define ERROR 0
#define OVERFLOW -1
| 模組 | 檔案 | 關鍵函數 |
|---|---|---|
| 二叉樹 | BinaryTree.h/.c | 建立、各式遍歷、深度、葉子、度統計、平衡判斷、層次查找、交換子樹 |
| 佇列 | Queue.h/.c | 循環佇列：初始化、入隊、出隊、空/滿判斷（層序遍歷用） |
| 堆疊 | Stack.h/.c | 動態陣列堆疊：初始化、推入、彈出、取頂、空判斷（非遞迴遍歷用） |
| 遍歷 | 遞迴版 | 非遞迴版核心邏輯 |
|---|---|---|
| 前序 | 根→左→右 | 堆疊存根，一直向左，彈出轉右 |
| 中序 | 左→根→右 | 堆疊存根，一直向左，彈出訪問根，轉右 |
| 後序 | 左→右→根 | 雙堆疊或單堆疊+標記陣列（0=左訪問完,1=右訪問完） |
| 層序 | — | 佇列 BFS：根入隊，出隊訪問，子節點入隊 |
void InOrderNonRec(BTree *root) {
Stack s; InitStack(&s);
BTree *p = root;
while (p || !IsStackEmpty(s)) {
if (p) { Push(&s, p); p = p->lchild; }
else { Pop(&s, &p); visit(p); p = p->rchild; }
}
}
void PostOrderNonRec(BTree *root) {
BTree *stack[MAX], *p = root;
int tag[MAX], top = 0;
while (p || top) {
while (p) { stack[++top] = p; tag[top] = 0; p = p->lchild; }
if (tag[top] == 1) { p = stack[top--]; visit(p); p = NULL; }
else { p = stack[top]; p = p->rchild; tag[top] = 1; }
}
}
輸入序列（先序，# 表空）：ABC##DE#G##F###
對應樹結構：
A
/ \
B F
/ \
C D
\
E
\
G
呼叫 SwapLeftRightSubtree 後，前序變為 AFBEDGC，結構鏡像翻轉，所有統計數值不變。
gcc -std=c11 -Wall -Wextra -O2 BinaryTree.c Queue.c Stack.c -o btree
echo "ABC##DE#G##F###" | ./btree
完整代碼結構模組化、註釋詳盡，適合資料結構教學與面試準備。
