1、二叉樹的遍歷

目前創(chuàng)新互聯(lián)已為上千的企業(yè)提供了網(wǎng)站建設(shè)、域名、雅安服務(wù)器托管、綿陽(yáng)服務(wù)器托管、企業(yè)網(wǎng)站設(shè)計(jì)、紹興網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長(zhǎng)，共同發(fā)展。

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

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

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

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

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

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

所有程序皆正確測(cè)試過，后面將給完整程序和測(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、二叉樹的4種非遞歸遍歷

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

  先序的非遞歸遍歷：棧先入后出，根結(jié)點(diǎn)入棧，棧不空，出棧訪問，此時(shí)將右孩子入棧，在將左孩子入棧，棧不空，出棧訪問，就是循環(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<<" ";  //訪問
            if(tmp->rightChild){    //右孩子存在
                st.push(tmp->rightChild);  //入棧
            }
            if(tmp->leftChild){     //左孩子存在
                st.push(tmp->leftChild);  //入棧
            }
        }
    }
}

  中序的非遞歸遍歷：就是先把根及左分支一直壓棧，棧不空，出棧訪問，再看右孩子，有的話，壓棧，結(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){  //將根和左子樹一直入棧
            st.push(p);
            p = p->leftChild;
        }
        if(!st.empty()){  //棧不空，
            p = st.top();  //讀棧頂元素
            st.pop();      //出棧
            cout<<p->data<<" ";  //訪問
            p = p->rightChild;   //此時(shí)往剛才棧頂元素的右孩子走；
        }             //中序遍歷時(shí)，當(dāng)root出棧時(shí)，此時(shí)?？?，沒有p!=NULL的話，將出錯(cuò)。
    }while(p != NULL || !st.empty()); //為根的時(shí)候右邊還要入棧。
}

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

  代碼如下：

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ù)成員為公有，便于訪問
    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;    //將指針給過去
            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;  //看有沒有右孩子，有的話，結(jié)束循環(huán)，要入棧的；
                isRun = false;  //特別重要，保證了右孩子的入棧！
                break;
            case R:
                cout<<n.ptr->data<<" ";
                break;
            }
        }
    }while(!st.empty());//不用p1=NULL,因?yàn)楫?dāng)?？諘r(shí)，最后一個(gè)節(jié)點(diǎn)剛好被訪問完成。
}

畫圖跟蹤后序如下：

  

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

  層次遍歷：根結(jié)點(diǎn)入隊(duì)列，隊(duì)列非空，出隊(duì)訪問，在將左右孩子入隊(duì)，非空，訪問，構(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<<" "; //訪問
            if(p->leftChild){  //左孩子存在
                qu.push(p->leftChild); //入隊(duì)
            }
            if(p->rightChild){   //右孩子存在
                qu.push(p->rightChild);  //入隊(duì)
            }
        }
    }
}

新聞標(biāo)題：二叉樹之非遞歸遍歷
轉(zhuǎn)載來于：http://jinyejixie.com/article40/jjhjeo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站制作、手機(jī)網(wǎng)站建設(shè)、網(wǎng)站建設(shè)、網(wǎng)站收錄、App開發(fā)、企業(yè)網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)