二叉樹(shù)之非遞歸遍歷

1、二叉樹(shù)的遍歷

  為什么要有遍歷操作：將線性結(jié)構(gòu)-------->非線性結(jié)構(gòu)；

      將遞歸程序-------->非遞歸程序；

2、二叉樹(shù)的三種遞歸遍歷：

  先序遍歷：先訪問(wèn)根(父)結(jié)點(diǎn)，在訪問(wèn)左分支，最后訪問(wèn)右分支；

  中序遍歷：先訪問(wèn)左分支，在根結(jié)點(diǎn)，最后右分支；

  后序遍歷：先訪問(wèn)左分支，在訪問(wèn)右分支，最后訪問(wèn)根節(jié)點(diǎn)；

所有程序皆正確測(cè)試過(guò)，后面將給完整程序和測(cè)試程序，測(cè)試結(jié)果。

以下就是遞歸遍歷，先序，中序，后序：

下面的都是在類外定義的函數(shù)，所以為模板函數(shù)：

//先序遍歷
template<typename Type>
void BinTree<Type>::prevOrder(BinTreeNode<Type> *t)const{
    if(t == NULL){
        return;
    }else{
        cout<<t->data<<" ";
        prevOrder(t->leftChild);
        prevOrder(t->rightChild);
    }
}
//中序遍歷
template<typename Type>
void BinTree<Type>::inOrder(BinTreeNode<Type> *t)const{
    if(t == NULL){
        return;
    }else{
        inOrder(t->leftChild);
        cout<<t->data<<" ";
        inOrder(t->rightChild);
    }
}
//后序遍歷
template<typename Type>
void BinTree<Type>::endOrder(BinTreeNode<Type> *t)const{
    if(t == NULL){
        return;
    }else{
        endOrder(t->leftChild);
        endOrder(t->rightChild);
        cout<<t->data<<" ";
    }
}

3、二叉樹(shù)的4種非遞歸遍歷

  (1)、深度優(yōu)先用棧

  先序的非遞歸遍歷：棧先入后出，根結(jié)點(diǎn)入棧，棧不空，出棧訪問(wèn)，此時(shí)將右孩子入棧，在將左孩子入棧，棧不空，出棧訪問(wèn)，就是循環(huán)了；

  代碼如下：

template<typename Type>
void BinTree<Type>::prevOrder_1(BinTreeNode<Type>* t)const{
    stack<BinTreeNode<Type> *> st;  //棧里面放的是指向節(jié)點(diǎn)的指針
    BinTreeNode<Type> *tmp;

    if(t != NULL){   //根不為空
        st.push(t);  //根入棧
        while(!st.empty()){  //棧非空
            tmp = st.top();  //讀棧頂元素
            st.pop();        //出棧
            cout<<tmp->data<<" ";  //訪問(wèn)
            if(tmp->rightChild){    //右孩子存在
                st.push(tmp->rightChild);  //入棧
            }
            if(tmp->leftChild){     //左孩子存在
                st.push(tmp->leftChild);  //入棧
            }
        }
    }
}

  中序的非遞歸遍歷：就是先把根及左分支一直壓棧，棧不空，出棧訪問(wèn)，再看右孩子，有的話，壓棧，結(jié)束條件想清楚就行。

  代碼如下：

template<typename Type>
void BinTree<Type>::inOrder_1(BinTreeNode<Type>* t)const{
    stack<BinTreeNode<Type> *> st;  //棧里面放的是指向節(jié)點(diǎn)的指針
    BinTreeNode<Type> *p = t;
                     //用的是do while()循環(huán)
    do{
        while(p != NULL){  //將根和左子樹(shù)一直入棧
            st.push(p);
            p = p->leftChild;
        }
        if(!st.empty()){  //棧不空，
            p = st.top();  //讀棧頂元素
            st.pop();      //出棧
            cout<<p->data<<" ";  //訪問(wèn)
            p = p->rightChild;   //此時(shí)往剛才棧頂元素的右孩子走；
        }             //中序遍歷時(shí)，當(dāng)root出棧時(shí)，此時(shí)?？眨瑳](méi)有p!=NULL的話，將出錯(cuò)。
    }while(p != NULL || !st.empty()); //為根的時(shí)候右邊還要入棧。
}

  后序的非遞歸遍歷：思想就是要有一個(gè)標(biāo)志，當(dāng)為右邊回來(lái)的時(shí)候才能訪問(wèn)根節(jié)點(diǎn)！??！

  代碼如下：

typedef enum{L, R}Tag;   //枚舉定義新的類型
template<typename Type>  //定義一個(gè)類，為的是做標(biāo)志
class stkNode{
public:
    stkNode(BinTreeNode<Type> *p = NULL) : ptr(p), tag(L){}
public:                  //數(shù)據(jù)成員為公有，便于訪問(wèn)
    BinTreeNode<Type> *ptr;  
    Tag                   tag; //L R
};
template<typename Type>
void BinTree<Type>::endOrder_1(BinTreeNode<Type>* t)const{
    stkNode<Type> n;
    stack<stkNode<Type>> st;  //此時(shí)棧中存放的是對(duì)象！
    BinTreeNode<Type> *p = t;
    
    do{
        while(p != NULL){  //不為空，一路向左入棧
            n.ptr = p;    //將指針給過(guò)去
            n.tar = L;    //記為左邊入棧
            st.push(n);
            p = p->leftChild;
        }
        bool isRun = true;  //是否繼續(xù)的標(biāo)志
        while(isRun && !st.empty()){  
            n = st.top();  //讀棧頂
            st.pop();     //出棧

            switch(n.tag){  //根據(jù)L和R選擇
            case L:
                p = n.ptr; 
                n.tag = R;  //更改為R
                st.push(n);  //壓入棧
                p = p->rightChild;  //看有沒(méi)有右孩子，有的話，結(jié)束循環(huán)，要入棧的；
                isRun = false;  //特別重要，保證了右孩子的入棧！
                break;
            case R:
                cout<<n.ptr->data<<" ";
                break;
            }
        }
    }while(!st.empty());//不用p1=NULL,因?yàn)楫?dāng)棧空時(shí)，最后一個(gè)節(jié)點(diǎn)剛好被訪問(wèn)完成。
}

畫(huà)圖跟蹤后序如下：

  (2)、廣度優(yōu)先用隊(duì)列

  層次遍歷：根結(jié)點(diǎn)入隊(duì)列，隊(duì)列非空，出隊(duì)訪問(wèn)，在將左右孩子入隊(duì)，非空，訪問(wèn)，構(gòu)成循環(huán)；

  代碼如下：

template<typename Type>
void BinTree<Type>::levelOrder(BinTreeNode<Type>* t)const{
    queue<BinTreeNode<Type> *> qu;  //隊(duì)列里面放的是指向節(jié)點(diǎn)的指針
    BinTreeNode<Type> *p;

    if(t != NULL){ //根非空
        qu.push(t);  //根入隊(duì)
        while(!qu.empty()){  //隊(duì)列非空
            p = qu.front();  //讀隊(duì)首
            qu.pop();        //出隊(duì)
            cout<<p->data<<" "; //訪問(wèn)
            if(p->leftChild){  //左孩子存在
                qu.push(p->leftChild); //入隊(duì)
            }
            if(p->rightChild){   //右孩子存在
                qu.push(p->rightChild);  //入隊(duì)
            }
        }
    }
}