歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

三種二叉樹遍歷的非遞歸實現

分享下關於三種二叉樹遍歷的非遞歸實現的,轉到這兒來吧。程序都是偽代碼,因為是考研復習期間寫的,數據結構參考了嚴蔚敏的《數據結構》。

《數據結構 C++ 語言描述》(Data Structures C++ ) PDF+源碼 劉衛東,沈官林 譯 http://www.linuxidc.com/Linux/2014-09/107319.htm

先看遞歸實現:

void Traverse(BiTree T){
    if(T){
    //visit,先序遍歷
    Traverse(T->lchild);
    //visit,中序遍歷
    Traverse(T->rchild);
    //visit,後序遍歷
    }
}

可以看到三種遍歷方法的遞歸實現形式完全一樣,只需改變visit的位置,就得到不同遍歷序列。因此從情感上覺得非遞歸實現應該形式也完全一樣,這是課本給的中序非遞歸實現:

void InOrderTraverse(BiTree T, status(* visit)(TElemType e)){
    InitStack(s); p=T;
    while(p || !StackEmpty(s)){
        if(p){
        Push(s,p); p=p->lchild;
        }else{
        Pop(s,p);visit(p->data);p=p->rchild;
        }
    }
}

只需將visit(p->data);移動到Push(s,p); 後,就能得到先序遍歷的非遞歸實現。然後在考慮後序遍歷時,發現這種形式不適用後序遍歷,所以後來不得不自己寫了一個後序遍歷的非遞歸程序。然而心裡始終覺得不舒服,為什麼遞歸實現上明明如此統一,到了非遞歸實現後序遍歷就與眾不同了呢?由於復習時間很緊張,對於這個問題基本都是零零散散的,走路蹲點發呆無聊的時候,漫無邊際地胡思亂想~直到某天蹲點的時候,想明白了。

課本的非遞歸實現對棧的使用並不和遞歸棧相同,因此結點的進出棧順序也和遞歸棧明顯不同,基於這個道理,寫了一個完全仿照遞歸棧工作的非遞歸實現,關鍵是出棧的條件發生了變化,而且從直覺上,這個程序的出棧和進棧語句(Push,Pop),賦值左孩子和右孩子(p=p->lchild或rchild)都應只出現一次,如果出現了多次,應該是功能重復了,可以再進行縮減。

status Traverse(BiTree T, status(* visit)(TElemType e)){
    IniTStack(s); p=T; p1=NULL;
    while(p || !StackEmpty(s)){
        if(p){
            Push(s,p);
            //visit,先序
            p=p->lchild;
        }else{
            GetTop(s,p);
            //visit,中序
            if(p->rchild==p1 || p->rchild==NULL){
                Pop(s,p1);p=NULL;
                //visit,後序
            }else{
                p=p->rchild;p1=NULL;
            }
        }
    }
}

在這種形式下,只需改變visit的位置就能得到三種遍歷的非遞歸實現,結點的進出棧順序完全和遞歸棧一樣,判斷結點是否出棧的條件是:上一次出棧的結點是棧頂元素的右孩子。

對幾棵二叉樹進行了試驗,結果是對的,但不知道有沒有疏忽的地方。

二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm

在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm

Copyright © Linux教程網 All Rights Reserved