C++ 數據結構核心：二叉樹與二叉搜索樹完整實現與性能分析

二叉樹是模擬現實層級結構（族譜、目錄、決策樹）的基礎模型。本文實現鏈式二叉樹、四種遍歷、線索化分析、二叉搜索樹（BST）插入刪除查找，並通過實測對比遞歸與非遞歸遍歷性能，揭示棧消解遞歸的誤區。

節點結構設計

建議包含雙親指針，以空間換時間簡化多種算法：

template <class T>
struct BTNode {
    T data;
    BTNode *left, *right, *parent;
    BTNode(T d=T(), BTNode* l=nullptr, BTNode* r=nullptr, BTNode* p=nullptr)
        : data(d), left(l), right(r), parent(p) {}
};

基本二叉樹類與四種遍歷

template <class T>
class BTree {
    BTNode<T> *root;
    void destroy(BTNode<T>* p) { // 後序刪除
        if (p) { destroy(p->left); destroy(p->right); delete p; }
    }
public:
    // 1. 前序遍歷：根-左-右
    void PreOrder(void(*visit)(T&)=print) { PreOrder(root, visit); }
    void PreOrder(BTNode<T>* p, void(*visit)(T&)) {
        if (p) { visit(p->data); PreOrder(p->left, visit); PreOrder(p->right, visit); }
    }
    // 2. 中序遍歷：左-根-右
    void InOrder(void(*visit)(T&)=print) { InOrder(root, visit); }
    void InOrder(BTNode<T>* p, void(*visit)(T&)) {
        if (p) { InOrder(p->left, visit); visit(p->data); InOrder(p->right, visit); }
    }
    // 3. 後序遍歷：左-右-根
    void PostOrder(void(*visit)(T&)=print) { PostOrder(root, visit); }
    void PostOrder(BTNode<T>* p, void(*visit)(T&)) {
        if (p) { PostOrder(p->left, visit); PostOrder(p->right, visit); visit(p->data); }
    }
    // 4. 層次遍歷（隊列實現）
    void LevelOrder(void(*visit)(T&)=print) {
        queue<BTNode<T>*> q; BTNode<T>* p = root;
        while (p) {
            visit(p->data);
            if (p->left) q.push(p->left);
            if (p->right) q.push(p->right);
            if (q.empty()) break;
            p = q.front(); q.pop();
        }
    }
    static void print(T& d) { cout << d << ' '; }
};

無棧非遞歸中序遍歷（利用 parent 指針）

BTNode<T> *current;
void first() { current = root; while (current->left) current = current->left; }
BTNode<T>* next() {
    if (!current) return nullptr;
    if (current->right) {
        current = current->right;
        while (current->left) current = current->left;
    } else {
        BTNode<T>* y = current->parent;
        while (y && current == y->right) { current = y; y = y->parent; }
        current = y;
    }
    return current;
}

線索化二叉樹：已過時的技術

利用葉子節點空指針域存儲前驅/後繼，添加標誌位區分線索與子樹指針。現代 PC 上毫無用處：

• 標誌位至少佔 1 字節，內存對齊後無節省（32位系統 4 字節對齊）。
• 不如直接存儲 parent 指針（同樣 4 字節），功能更強（支援無棧遍歷、向上查找）。
• 線索化樹插入刪除維護代價極大。

結論：單片機等極度受限環境也傾向避免樹結構，線索化已無適用場景。

二叉搜索樹 (BST) 完整實現

核心操作：查找（返回內部指針引用）、插入、刪除。

查找：返回內部指針引用支援插入/刪除

BTNode<T>* &find(const T& data) {
    BTNode<T>** p = &root; current = nullptr;
    while (*p) {
        if ((*p)->data == data) break;
        if ((*p)->data < data) { current = *p; p = &((*p)->right); }
        else { current = *p; p = &((*p)->left); }
    }
    return *p; // 返回內部指針引用（如 root 或 parent->left）
}

插入：利用 find 返回的內部指針直接掛接

bool insert(const T& data) {
    BTNode<T>* &p = find(data);
    if (p) return false; // 已存在
    p = new BTNode<T>(data, nullptr, nullptr, current);
    return true;
}

刪除：三種情況統一處理

bool remove(const T& data) { return remove(find(data)); }
bool remove(BTNode<T>* &p) {
    if (!p) return false;
    BTNode<T>* t = p;
    // 情況 1/2：至少一個子樹為空
    if (!p->left || !p->right) {
        p = p->left ? p->left : p->right; // 重連非空子樹（或 nullptr）
        if (p) p->parent = current;
        delete t; return true;
    }
    // 情況 3：雙子樹均非空 → 轉化為情況 1/2
    // 找中序後繼（右子樹最左節點）
    t = p->right; while (t->left) t = t->left;
    p->data = t->data; // 複製數據
    current = t->parent;
    // 遞歸刪除後繼（後繼必無左子樹）
    return remove(current->left == t ? current->left : current->right);
}

關鍵洞察：中序前驅/後繼必有一側子樹為空，將雙子樹刪除轉化為單子樹刪除。

樹形可視化輸出

按層次遍歷補齊為完全二叉樹（空位用佔位節點），根據層級計算域寬輸出，層數 ≤5 時控制檯可讀，更多層數導出文件。

性能實測：遞歸 vs 非遞歸遍歷

測試環境：VC6 Release/Debug，20萬節點隨機構建 BST。

核心發現

1. 遞歸遍歷最快：系統棧操作（push/pop/call/ret）為單指令，ADT 棧模擬需多指令，模擬必然更慢。
2. 棧消解遞歸不提速：流傳「遞歸慢、棧快」源於斐波那契數列（重複計算）或將 I/O 移出遞歸的錯誤對比。純算法遞歸無可比擬。
3. 棧消解唯一優勢：節省系統棧空間：深遞歸導致棧溢出時（如 1.5萬節點有序構建的退化鏈表），非遞歸仍能工作。但這通常意味著算法或數據結構選型有問題（應用平衡樹）。

BST 退化與平衡樹必要性

有序插入導致樹退化為鏈表，查找/插入/刪除從 O(log N) 惡化為 O(N)，遍歷棧深度達 N 導致溢出。這正是 AVL、紅黑樹等平衡樹誕生的原因。

總結

• 二叉樹節點建議含 parent 指針，簡化算法實現。
• 四種遍歷各有適用場景：前序判等、後序銷毀、中序有序輸出、層次可視化。
• 線索化二叉樹在現代硬體上無價值，parent 指針是更優替代。
• BST 刪除核心技巧：利用中序前驅/後繼特性將雙子樹刪除轉化為單子樹。
• 遞歸是高效的，棧消解僅作棧溢出保底，非性能優化手段。
• 無序數據構建 BST 近似平衡，有序數據必退化，生產環境必須使用平衡樹。