DIV CSS 佈局教程網

二元樹的非遞迴後序遍歷:演算法與實作解析
編輯:JavaScript綜合知識     

前序、中序、後序三種深度優先遍歷中,後序是最麻煩的一個。原因是後序要求「左 → 右 → 根」,而當我們沿著左路徑往下走時,必須記得「回頭還要處理右子樹」。若只在堆疊裡放節點指標,資訊是不够的——必須額外記錄每個節點的右子樹是否已拜訪過。

堆疊節點的資料結構

typedef struct {
    Node *p;
    int rvisited;   // ==1 代表 p 所指節點的右子節點已被拜訪過
} SNode;

演算法主體

void lastOrderTraverse(BiTree bt) {
    // 第一步:從根節點出發一路向左下走到底,路徑上每個節點入堆疊
    Node *p = bt;
    while (p) {
        push(p, 0);          // 入堆疊:節點指標 + 右子節點是否已拜訪(0)
        p = p->lchild;
    }

    // 第二步:進入主迴圈
    while (!Stack.empty()) {
        SNode sn = Stack.getTop();   // 取堆疊頂端元素

        // 注意:任一枚舉 N,只要它有左孩子,N 入堆疊後左孩子必然也入堆疊了。
        // 所以拿到堆疊頂時可以確定:這個元素要嘛沒有左孩子,
        // 要嘛左孩子已經被拜訪過 —— 因此不必再管左孩子,只關心右孩子。

        // 情況一:沒有右孩子,或右孩子已拜訪過 → 可以拜訪它了
        if (!sn.p->rchild || sn.rvisited) {
            pop();
            visit(sn.p);
        }
        // 情況二:右孩子存在且未拜訪 → 先處理右子樹
        else {
            sn.rvisited = 1;     // 標記:右孩子即將入堆疊,意味著它會先被拜訪
            // 從右孩子開始一路向左下走到底,路徑上全部入堆疊
            p = sn.p->rchild;
            while (p != 0) {
                push(p, 0);
                p = p->lchild;
            }
            // 這一輪剛入堆疊的節點不必理會,下一輪迴圈會照顧好它們
        }
    }
}

為什麼這樣就對了

關鍵在兩個不變式:

  1. 堆疊頂永遠是「左子樹已處理完」的候選者。因為每次向右轉之前,我們都會先把右孩子的一整條左路徑壓入堆疊,這些元素自然排在更上面,會先被 pop 出來拜訪。
  2. rvisited 標記保證右子樹先於父節點被輸出。當父節點設為 1 之後,它下一次成為堆疊頂時,右子樹必然已經處理完畢——因為我們總是從堆疊頂取元素,而右子樹的節點是後壓入的,一定先被取出。

這兩個性質合起來,正好對應後序遍歷「左右根」的定義。相比遞迴版本,這個寫法用一個整數旗標換掉了系統呼叫堆疊,在深度很大或需要自行管理堆疊的環境中特別有用。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved