二叉樹遍歷全解析：遞歸與非遞歸算法完整實現

前言

二叉樹作為非線性資料結構，其遍歷操作是資料結構與算法的核心考點。本文系統梳理前序、中序、後序三種遍歷規則，並提供遞歸與非遞歸（棧模擬）雙重實現，幫助讀家深度理解樹的遍歷本質。

一、二叉樹結構定義與遍歷規則

1. 節點結構定義

typedef struct _BinaryTreeNode {
    int value;
    struct _BinaryTreeNode* pLeft;   // 左子節點指標
    struct _BinaryTreeNode* pRight;  // 右子節點指標
} BinaryTreeNode_t;

2. 遍歷規則本質

設 L=左子樹、R=右子樹、D=根節點，理論上有 6 種排列組合。若限定「先左後右」，則剩三種核心遍歷：

• DLR（前序/先根遍歷）：根 → 左 → 右
• LDR（中序/中根遍歷）：左 → 根 → 右
• LRD（後序/後根遍歷）：左 → 右 → 根

二、前序遍歷（DLR）

1. 遞歸實現

void PreOrder(BinaryTreeNode_t* pRoot) {
    if (pRoot != NULL) {
        printf("%d ", pRoot->value);      // 1. 訪問根
        PreOrder(pRoot->pLeft);           // 2. 遞歸左子樹
        PreOrder(pRoot->pRight);          // 3. 遞歸右子樹
    }
}

2. 非遞歸實現（棧模擬）

核心邏輯：沿左子樹下行時訪問節點並入棧，左子樹耗盡後出棧轉向右子樹。

void PreOrder(const BinaryTreeNode_t* pRoot) {
    std::stack s;
    BinaryTreeNode_t* p = pRoot;

    while (p != NULL || !s.empty()) {
        while (p != NULL) {
            printf("%d ", p->value);  // 訪問當前節點
            s.push(p);                // 入棧
            p = p->pLeft;             // 轉向左子樹
        }
        p = s.top(); s.pop();         // 出棧
        p = p->pRight;                // 轉向右子樹
    }
}

三、中序遍歷（LDR）

1. 遞歸實現

void InOrder(BinaryTreeNode_t* pRoot) {
    if (pRoot != NULL) {
        InOrder(pRoot->pLeft);            // 1. 遞歸左子樹
        printf("%d ", pRoot->value);      // 2. 訪問根
        InOrder(pRoot->pRight);           // 3. 遞歸右子樹
    }
}

2. 非遞歸實現

關鍵差異：入棧過程不訪問，出棧時才訪問（左子樹已處理完畢）。

void InOrder(const BinaryTreeNode_t* pRoot) {
    std::stack s;
    BinaryTreeNode_t* p = pRoot;

    while (p != NULL || !s.empty()) {
        while (p != NULL) {
            s.push(p);        // 僅入棧，不訪問
            p = p->pLeft;
        }
        p = s.top(); s.pop(); // 出棧並訪問
        printf("%d ", p->value);
        p = p->pRight;        // 轉向右子樹
    }
}

四、後序遍歷（LRD）——最複雜的非遞歸實現

1. 遞歸實現

void PostOrder(BinaryTreeNode_t* pRoot) {
    if (pRoot != NULL) {
        PostOrder(pRoot->pLeft);          // 1. 左子樹
        PostOrder(pRoot->pRight);         // 2. 右子樹
        printf("%d ", pRoot->value);      // 3. 訪問根
    }
}

2. 非遞歸實現（雙指標法）

難點分析：節點第二次出棧時才能訪問（需確認右子樹已處理）。引入 pre 指標記錄上一次訪問的節點。

void PostOrder(const BinaryTreeNode_t* pRoot) {
    std::stack s;
    BinaryTreeNode_t* p = pRoot;
    BinaryTreeNode_t* pre = NULL;  // 記錄最近訪問的節點

    while (p != NULL || !s.empty()) {
        while (p != NULL) {
            s.push(p);
            p = p->pLeft;
        }
        p = s.top();  // 查看棧頂，不彈出

        // 右子樹為空 或 右子樹剛被訪問過
        if (p->pRight == NULL || p->pRight == pre) {
            printf("%d ", p->value);
            s.pop();
            pre = p;      // 標記已訪問
            p = NULL;     // 避免重複進入左子樹
        } else {
            p = p->pRight; // 轉向右子樹
        }
    }
}

五、算法複雜度與選型建議

六、總結

掌握二叉樹三種遍歷的遞歸與非遞歸實現，是資料結構學習的必經之路。關鍵在於理解：

1. 遞歸本質是系統隱式棧的調用
2. 非遞歸需顯式維護棧，模擬遞歸的「下行入棧、上行出棧」過程
3. 後序遍歷需額外狀態（pre指標）判斷右子樹處理完成

實際開發中，優先考慮遞歸版本以提高可讀性；當樹深度不可控或需精細控制遍歷流程時，採用非遞歸版本。