前序遍歷順序:**根 → 左 → 右**。本文提供 C++ 樣板類別的遞迴與非遞迴兩種實作,並詳細解析非遞迴演算法的堆疊邏輯。
template
void PreOrder(nodeType *root) {
if (root == NULL) return;
visit(root->data); // 1. 造訪根節點
PreOrder(root->lchild); // 2. 遞迴左子樹
PreOrder(root->rchild); // 3. 遞迴右子樹
}
特點:程式碼簡潔、符合定義直覺,但深度過大時可能堆疊溢位。
temp,造訪之。temp 有右子節點 → 入堆疊 (先右)。temp 有左子節點 → 入堆疊 (後左,保證左子節點在堆疊頂,優先被處理)。void PreOrder_Nonrecursive(BinaryTree T) {
if (!T) return;
stack s;
s.push(T);
while (!s.empty()) {
BinaryTree temp = s.top(); s.pop();
visit(temp->data);
if (temp->rchild) s.push(temp->rchild); // 先壓右
if (temp->lchild) s.push(temp->lchild); // 再壓左
}
}
void PreOrder_Nonrecursive_v2(BinaryTree T) {
if (!T) return;
stack s;
BinaryTree t = T;
while (t || !s.empty()) {
if (t) {
visit(t->data);
s.push(t);
t = t->lchild; // 一路往左
} else {
t = s.top(); s.pop();
t = t->rchild; // 轉向右
}
}
}
| 指標 | 遞迴 | 非遞迴 |
|---|---|---|
| 時間複雜度 | O(n) | O(n) |
| 空間複雜度 | O(h) 隱式呼叫堆疊 | O(h) 顯式堆疊 |
| 堆疊溢位風險 | 有 (極深樹) | 無 (堆積在堆疊區) |
熟練兩種寫法,不僅能應付面試考題,更能深入理解樹結構與堆疊的關係。