二叉樹之非遞歸遍歷

1、二叉樹的遍歷

  為什么要有遍歷操作：將線性結構-------->非線性結構；

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

2、二叉樹的三種遞歸遍歷：

  先序遍歷：先訪問根(父)結點，在訪問左分支，最后訪問右分支；

  中序遍歷：先訪問左分支，在根結點，最后右分支；

  后序遍歷：先訪問左分支，在訪問右分支，最后訪問根節點；

所有程序皆正確測試過，后面將給完整程序和測試程序，測試結果。

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

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

//先序遍歷
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、二叉樹的4種非遞歸遍歷

  (1)、深度優先用棧

  先序的非遞歸遍歷：棧先入后出，根結點入棧，棧不空，出棧訪問，此時將右孩子入棧，在將左孩子入棧，棧不空，出棧訪問，就是循環了；

  代碼如下：

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

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

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

  代碼如下：

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

  后序的非遞歸遍歷：思想就是要有一個標志，當為右邊回來的時候才能訪問根節點?。?！

  代碼如下：

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

            switch(n.tag){  //根據L和R選擇
            case L:
                p = n.ptr; 
                n.tag = R;  //更改為R
                st.push(n);  //壓入棧
                p = p->rightChild;  //看有沒有右孩子，有的話，結束循環，要入棧的；
                isRun = false;  //特別重要，保證了右孩子的入棧！
                break;
            case R:
                cout<<n.ptr->data<<" ";
                break;
            }
        }
    }while(!st.empty());//不用p1=NULL,因為當?？諘r，最后一個節點剛好被訪問完成。
}

畫圖跟蹤后序如下：

  (2)、廣度優先用隊列

  層次遍歷：根結點入隊列，隊列非空，出隊訪問，在將左右孩子入隊，非空，訪問，構成循環；

  代碼如下：

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

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