遍歷是對(duì)樹的一種最基本的運(yùn)算，所謂遍歷二叉樹，就是按一定的規(guī)則和順序走遍二叉樹的所有結(jié)點(diǎn)，使每一個(gè)結(jié)點(diǎn)都被訪問(wèn)一次，而且只被訪問(wèn)一次。我們都知道二叉樹的遍歷方式有先序、中序和后序遍歷，本文我們主要來(lái)介紹二叉樹先序遍歷。

首先，我們要知道二叉樹先序遍歷的實(shí)現(xiàn)思想：

1.訪問(wèn)根節(jié)點(diǎn)；

2.訪問(wèn)當(dāng)前節(jié)點(diǎn)的左子樹；

3.若當(dāng)前節(jié)點(diǎn)無(wú)左子樹，則訪問(wèn)當(dāng)前節(jié)點(diǎn)的右子樹；

如下圖表示一顆二叉樹，對(duì)它進(jìn)行先序遍歷操作，采用兩種方法，遞歸和非遞歸操作。

采用先序遍歷的思想遍歷該二叉樹的過(guò)程為：

1.訪問(wèn)該二叉樹的根節(jié)點(diǎn)，找到 1；

2.訪問(wèn)節(jié)點(diǎn) 1 的左子樹，找到節(jié)點(diǎn) 2；

3.訪問(wèn)節(jié)點(diǎn) 2 的左子樹，找到節(jié)點(diǎn) 4；

4.由于訪問(wèn)節(jié)點(diǎn) 4 左子樹失敗，且也沒(méi)有右子樹，因此以節(jié)點(diǎn) 4 為根節(jié)點(diǎn)的子樹遍歷完成。但節(jié)點(diǎn) 2 還沒(méi)有遍歷其右子樹，因此現(xiàn)在開始遍歷，即訪問(wèn)節(jié)5；

5.由于節(jié)點(diǎn) 5 無(wú)左右子樹，因此節(jié)點(diǎn) 5 遍歷完成，并且由此以節(jié)點(diǎn) 2 為根節(jié)點(diǎn)的子樹也遍歷完成。現(xiàn)在回到節(jié)點(diǎn) 1 ，并開始遍歷該節(jié)點(diǎn)的右子樹，即訪問(wèn)節(jié)點(diǎn) 3；

6.訪問(wèn)節(jié)點(diǎn) 3 左子樹，找到節(jié)點(diǎn)6；

7.由于節(jié)點(diǎn) 6無(wú)左右子樹，因此以節(jié)點(diǎn)6為根節(jié)點(diǎn)的子樹遍歷完成。但節(jié)點(diǎn) 3還沒(méi)有遍歷其右子樹，因此現(xiàn)在開始遍歷，即訪問(wèn)節(jié)7；到這里，整個(gè)先序遍歷完成。

1、遞歸操作：

思想：若二叉樹為空，返回。否則

1)遍歷根節(jié)點(diǎn)；

2)先序遍歷左子樹；

3）先序遍歷右子樹

代碼：

void PreOrder(BiTree root) ?

{ ?

????if(root==NULL) ?

????????return ; ?

????printf("%c ", root->data); //輸出數(shù)據(jù) ?

????PreOrder(root->lchild); //遞歸調(diào)用，先序遍歷左子樹 ?

????PreOrder(root->rchild); //遞歸調(diào)用，先序遍歷右子樹 ?

} ?

2、非遞歸操作

思想：二叉樹的非遞歸先序遍歷，先序遍歷思想：先讓根進(jìn)棧，只要棧不為空，就可以做彈出操作， 每次彈出一個(gè)結(jié)點(diǎn)，記得把它的左右結(jié)點(diǎn)都進(jìn)棧，記得右子樹先進(jìn)棧，這樣可以保證右子樹在棧中總處于左子樹的下面。

代碼：

void PreOrder_Nonrecursive(BiTree T)     //先序遍歷的非遞歸    

{  

    if(!T) return ;    

    stack s;  

    s.push(T);  

    while(!s.empty())  

    {  

        BiTree temp = s.top();  

        cout<data<<" ";  

        s.pop();  

        if(temp->rchild)  

            s.push(temp->rchild);  

        if(temp->lchild)  

            s.push(temp->lchild);  

    }  

}  

或者：

void PreOrder_Nonrecursive(BiTree T)     //先序遍歷的非遞歸  

{  

    if(!T) return ;  

    stack s;  

    while(T)          // 左子樹上的節(jié)點(diǎn)全部壓入到棧中  

    {  

        s.push(T);  

        cout<data<<"  ";  

        T = T->lchild;  

    }        

    while(!s.empty())  

    {          

        BiTree temp = s.top()->rchild;  // 棧頂元素的右子樹  

        s.pop();                        // 彈出棧頂元素  

        while(temp)          // 棧頂元素存在右子樹，則對(duì)右子樹同樣遍歷到最下方  

        {  

            cout<data<<"  ";  

            s.push(temp);  

            temp = temp->lchild;  

        }  

    }  

}  

以上就是二叉樹先序遍歷，經(jīng)過(guò)我們圖文并茂的描述，相信大多數(shù)小伙伴都能夠理解二叉樹先序遍歷的步驟，其實(shí)，二叉樹其他遍歷方式和先序遍歷也是大同小異的，我們只要能夠熟練掌握二叉樹先序遍歷，就能舉一反三，學(xué)會(huì)二叉樹其他遍歷方式，當(dāng)然，本站的數(shù)據(jù)結(jié)構(gòu)和算法教程對(duì)二叉樹遍歷方式有非常詳細(xì)的講解，不需要我們過(guò)多的推導(dǎo)，但我們學(xué)習(xí)的時(shí)候應(yīng)該更注重理解，這樣才能夠?qū)W有所思。