DIV CSS 佈局教程網

二叉樹的非遞迴後序遍歷:多帶一個 rvisited 標記
編輯:JavaScript綜合知識     

前序、中序、後序的非遞迴遍歷中,要數後序最為麻煩。原因是後序必須在左右子樹都處理完之後才拜訪根節點,而只在堆疊中保留指向節點的指標並不足夠,必須有一些額外資訊存放在堆疊裡。

方法有很多,這裡只舉一種:先定義堆疊節點的資料結構。

堆疊節點的定義

typedef struct {
    Node *p;
    int rvisited;   // ==1 代表 p 所指向的節點的右節點已被訪問過
} SNode;            // Node 是二叉樹的節點結構

演算法

lastOrderTraverse(BiTree bt) {
    // 首先,從根節點開始往左下方走,一直走到頭,
    // 將路徑上的每一個節點入堆疊
    p = bt;
    while (bt) {
        push(bt, 0);      // 入堆疊兩個資訊:節點指標、右節點是否被訪問過
        bt = bt.lchild;
    }

    // 然後進入循環體
    while (!Stack.empty()) {
        sn = Stack.getTop();   // sn 是堆疊頂節點

        // 注意:任意一個節點 N,只要它有左孩子,則 N 入堆疊之後,
        // N 的左孩子必然也跟著入堆疊了(這體現在演算法的後半部分)。
        // 所以當我們拿到堆疊頂元素的時候,可以確信這個元素要麼沒有左孩子,
        // 要麼其左孩子已經被訪問過 —— 此時就不關心它的左孩子,只關心右孩子。

        // 若其右孩子已被訪問過,或該元素沒有右孩子,
        // 則由後序遍歷的定義,此時可以 visit 這個節點了
        if (!sn.p.rchild || sn.rvisited) {
            p = pop();
            visit(p);
        } else {
            // 若它的右孩子存在且 rvisited 為 0,說明以前還沒有動過它的右孩子,
            // 於是就去處理一下其右孩子。

            // 此時要從其右孩子節點開始一直往左下方走,直至走到盡頭,
            // 將這條路徑上的所有節點都入堆疊。

            // 當然,入堆疊之前要先將該節點的 rvisited 設成 1,
            // 因為其右孩子的入堆疊意味著它的右孩子必將先於它被訪問
            //(因為我們總是從堆疊頂取出元素來 visit)。
            // 由此可知,下一次該元素再處於堆疊頂時,
            // 其右孩子必然已被 visit 過了。
            sn.rvisited = 1;

            p = sn.p.rchild;
            while (p != 0) {
                push(p, 0);
                p = p.lchild;
            }
        }
        // 這一輪循環已結束,剛剛入堆疊的那些節點不必管,
        // 下一輪循環會把這些節點照顧得很好
    }
}

為什麼這樣可行

關鍵在於一個不變式:「左孩子一定比父節點晚被拜訪、右孩子也一定比父節點晚被拜訪」,這是由「先一路向左下壓堆疊」的動作保證的。rvisited 只是把「右子樹是否已完成」這個狀態保存在堆疊裡,彌補了單一指標無法表達的資訊。

另一種常見做法是使用 prev 指標:記住上一個拜訪過的節點,若目前堆疊頂的右孩子等於 prev,或(沒有右孩子且)左孩子等於 prev,就可以出堆疊並拜訪。這種寫法不必修改節點結構,實作上往往更清爽,值得一併比較。

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