二叉樹鏈式存儲是數據結構教學與工程實踐的核心內容。本文提供標準 C/C++ 實現，涵蓋節點定義、先序創建、三種深度優先遍歷（先序/中序/後序）、樹深度計算、層序遍歷（隊列實現）五大核心操作，代碼結構清晰、邏輯嚴密，適合教學參考與考試復習。
順序存儲適合完全二叉樹，鏈式存儲適用於任意形態二叉樹。
typedef char TElemType; // 數據類型，可改為 int/結構體等
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
void CreateBiTree(BiTree &T) {
char ch;
if ((ch = getchar()) == '#') {
T = NULL;
} else {
T = (BiTNode*)malloc(sizeof(BiTNode));
if (!T) exit(OVERFLOW);
T->data = ch;
CreateBiTree(T->lchild); // 遞歸創建左子樹
CreateBiTree(T->rchild); // 遞歸創建右子樹
}
}
輸入約定：# 表示空指針。先序序列 AB##CD##EF##G## 對應樹形：
A
/ \
B C
/ \
D E
/ \
F G
// 先序：根 → 左 → 右
void PreOrderTraverse(BiTree T) {
if (T) {
printf("%c ", T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
// 中序：左 → 根 → 右
void InOrderTraverse(BiTree T) {
if (T) {
InOrderTraverse(T->lchild);
printf("%c ", T->data);
InOrderTraverse(T->rchild);
}
}
// 後序：左 → 右 → 根
void PostOrderTraverse(BiTree T) {
if (T) {
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c ", T->data);
}
}
示例樹輸出：
int TreeDepth(BiTree T) {
if (!T) return 0;
int leftDepth = TreeDepth(T->lchild);
int rightDepth = TreeDepth(T->rchild);
return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}
#include <queue>
using namespace std;
void LevelOrderTraverse(BiTree T) {
if (!T) return;
queue q;
q.push(T);
while (!q.empty()) {
BiTree p = q.front(); q.pop();
printf("%c ", p->data);
if (p->lchild) q.push(p->lchild);
if (p->rchild) q.push(p->rchild);
}
}
隊列軌跡演示：
入隊：[A] → 出A 入BC → [B,C] → 出B 入∅ → [C] → 出C 入DE → [D,E] 出D 入∅ → [E] → 出E 入FG → [F,G] → 出F 入∅ → [G] → 出G 入∅ → [] 輸出：A B C D E F G
#define MAXQ 100
BiTree queue[MAXQ];
int front = 0, rear = 0;
void EnQueue(BiTree node) { queue[rear++] = node; }
BiTree DeQueue() { return queue[front++]; }
int IsEmpty() { return front == rear; }
void LevelOrderTraverse_C(BiTree T) {
if (!T) return;
front = rear = 0;
EnQueue(T);
while (!IsEmpty()) {
BiTree p = DeQueue();
printf("%c ", p->data);
if (p->lchild) EnQueue(p->lchild);
if (p->rchild) EnQueue(p->rchild);
}
}
| 操作 | 時間複雜度 | 空間複雜度 | 核心數據結構 |
|---|---|---|---|
| 創建 | O(n) | O(h) 遞歸棧 | 遞歸/輸入流 |
| DFS遍歷 | O(n) | O(h) 遞歸棧 | 系統調用棧 |
| 深度計算 | O(n) | O(h) 遞歸棧 | 後序遞歸 |
| 層序遍歷 | O(n) | O(w) 隊列 | 隊列（寬度w） |
其中 h 為樹高，w 為最大層寬度。滿二叉樹 h=log₂n, w≈n/2；斜樹 h=n, w=1。
// 非遞歸先序
void PreOrderNonRec(BiTree T) {
stack s;
BiTree p = T;
while (p || !s.empty()) {
while (p) {
printf("%c ", p->data);
s.push(p);
p = p->lchild;
}
p = s.top(); s.pop();
p = p->rchild;
}
}
二叉樹鏈式存儲通過「數據域+左右指針」實現任意樹形的靈活表示。掌握 遞歸創建/遍歷（利用調用棧隱式管理狀態）、深度計算（後序思想）、層序遍歷（隊列顯式管理層級）四大核心模式，即可解決 90% 的二叉樹基礎問題。建議讀者在理解遞歸版本基礎上，嘗試手寫非遞歸版本（棧/隊列），深化對「隱式棧 vs 顯式數據結構」的理解，為平衡樹、紅黑樹、B樹等進階結構打牢基礎。
