遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規則和順序走遍二叉樹的所有結點，使每一個結點都被訪問一次，而且只被訪問一次。我們都知道二叉樹的遍歷方式有先序、中序和后序遍歷，本文我們主要來介紹二叉樹先序遍歷。

首先，我們要知道二叉樹先序遍歷的實現思想：

1.訪問根節點；

2.訪問當前節點的左子樹；

3.若當前節點無左子樹，則訪問當前節點的右子樹；

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

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

1.訪問該二叉樹的根節點，找到 1；

2.訪問節點 1 的左子樹，找到節點 2；

3.訪問節點 2 的左子樹，找到節點 4；

4.由于訪問節點 4 左子樹失敗，且也沒有右子樹，因此以節點 4 為根節點的子樹遍歷完成。但節點 2 還沒有遍歷其右子樹，因此現在開始遍歷，即訪問節5；

5.由于節點 5 無左右子樹，因此節點 5 遍歷完成，并且由此以節點 2 為根節點的子樹也遍歷完成。現在回到節點 1 ，并開始遍歷該節點的右子樹，即訪問節點 3；

6.訪問節點 3 左子樹，找到節點6；

7.由于節點 6無左右子樹，因此以節點6為根節點的子樹遍歷完成。但節點 3還沒有遍歷其右子樹，因此現在開始遍歷，即訪問節7；到這里，整個先序遍歷完成。

1、遞歸操作：

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

1)遍歷根節點；

2)先序遍歷左子樹；

3）先序遍歷右子樹

代碼：

void PreOrder(BiTree root) ?

{ ?

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

????????return ; ?

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

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

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

} ?

2、非遞歸操作

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

代碼：

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)          // 左子樹上的節點全部壓入到棧中  

    {  

        s.push(T);  

        cout<data<<"  ";  

        T = T->lchild;  

    }        

    while(!s.empty())  

    {          

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

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

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

        {  

            cout<data<<"  ";  

            s.push(temp);  

            temp = temp->lchild;  

        }  

    }  

}  

以上就是二叉樹先序遍歷，經過我們圖文并茂的描述，相信大多數小伙伴都能夠理解二叉樹先序遍歷的步驟，其實，二叉樹其他遍歷方式和先序遍歷也是大同小異的，我們只要能夠熟練掌握二叉樹先序遍歷，就能舉一反三，學會二叉樹其他遍歷方式，當然，本站的數據結構和算法教程對二叉樹遍歷方式有非常詳細的講解，不需要我們過多的推導，但我們學習的時候應該更注重理解，這樣才能夠學有所思。