二叉樹是一種最簡單的樹結構，通常由根節點、左子樹和右子樹組成，常見的二叉樹由平衡二叉樹、二叉搜索樹等，下面筆者將重點介紹一下普通二叉樹的前序、中序、后序及層次遍歷的原理及代碼實作，

二叉樹的前序、中序及后序遍歷

二叉樹的前序、中序及后序遍歷中的序指的是訪問根節點的順序，顧名思義，前序遍歷的意思就是首先訪問根節點并以根節點、左子樹、右子樹的順序遍歷該二叉樹，需強調的一點是在對子樹（無論是左子樹還是右子樹）遍歷時其遍歷順序同樣為子樹的根節點、子樹的左子樹、子樹的右子樹，因此，二叉樹的遍歷利用的就是分治的思想常使用深度優先搜索演算法實作，下面筆者將使用C++利用遞回和迭代的方法來實作二叉樹的前序遍歷：

前序遍歷（遞回）：

使用遞回的方法重要的是確定遞回終止的條件，而在二叉樹的遍歷中遞回條件通常為該二叉樹指標為空指標，

class Solution {
public:
    void preorder_traversal(TreeNode *root){
        if(root==null) return;
        cout<<root->val<<endl;        // 可用其他陳述句代替，具體看個人目的
        preorder_traversal(root->left);
        preorder_traversal(root->right);
    }

};

前序遍歷（迭代）：

迭代的方法難點在于迭代終止條件的設定以及實作遍歷順序，通常二叉樹的遍歷迭代方法軍用借助于堆疊來實作，

class Solution {
public:
    void preorder_traversal(TreeNode *root){
        stack<TreeNode*> stk;
        if(!root) return;
        stk.push(root);
        while(!stk.empty()){
            root=stk.top();
            cout<<root->val<<endl;
            stk.pop();
            //由于堆疊的先入后出的性質，因此需要將左節點后入堆疊從而可以優先訪問
            if(root->right) stk.push(root->right);
            if(root->left) stk.push(root->left);
        }
    }

};

中序遍歷（遞回）

中序遍歷的順序是左子樹、根節點及右子樹，下面是遞回實作：

class Solution {
public:
    void Inorder_traversal(TreeNode *root){
        if(root==null) return;
        Inorder_traversal(root->left);
        cout<<root->val<<endl;        // 可用其他陳述句代替，具體看個人目的
        Inorder_traversal(root->right);
    }

};

中序遍歷（迭代）

中序遍歷首先遍歷左子樹，因此需迭代至二叉樹左子樹的最高做子節點，然后進行回溯來遍歷二叉樹，下面為迭代實作：

class Solution {
public:
    void Inorder_traversal(TreeNode *root){
        stack<TreeNode*> stk;
        if(!root) return;  //為空樹則直接回傳
        while(true){
            if(root){
                stk.push(root); //根節點入堆疊
                root=root->left; //迭代至二叉樹最高左子節點
            }
            else if(!stk.empty()){
                root=stk.top()  //該節點為二叉樹最高左子節點，首先對其進行訪問
                cout<<root->val<<endl;
                stk.pop();
                root=root->right; //訪問完最高左子節點后需訪問該節點的右子樹（若存在）
            }
            else break;
        }
     
    }

};

后序遍歷（遞回）

后序遍歷的順序為左子樹、右子樹和根節點，遞回實作為：

class Solution {
public:
    void Postorder_traversal(TreeNode *root){
        if(root==null) return;
        Postorder_traversal(root->left);
        Postorder_traversal(root->right);
        cout<<root->val<<endl;        // 可用其他陳述句代替，具體看個人目的
    }

};

后序遍歷（迭代）

后序遍歷的順序是左右根，可借助前序遍歷根左右的結果得到后序遍歷，將前序遍歷改為根右左的遍歷方式再將結果倒序即得到后序遍歷的結果，代碼如下：

class Solution {
public:
    void postorder_traversal(TreeNode *root){
        stack<TreeNode*> stk;
        vecor<int> res; //存放根右左遍歷的結果
        if(!root) return;  //為空樹則直接回傳
        stk.push(root);
        while(!stk.empty()){
            root=stk.top();
            res.push_back(root->val);
            stk.pop();
            if(root->left) stk.push(root->left);
            if(root->right) stk.push(root->right);
        }
        reverse(res.begin(),res.end());//將結果倒序得到后序遍歷的結果
        for(int num:res) cout<<num<<endl;
    
     
    }

};

二叉樹的層次遍歷

前面介紹了二叉樹的前序、中序及后序的遍歷方法，下面將介紹二叉樹的層次遍歷，所謂層次遍歷就是對二叉樹進行逐層遍歷，該類遍歷使用廣度優先搜索通常需借助佇列來實作，代碼實作如下：

class Solution {
public:
    void Hierarchical_Traversal(TreeNode *root){
        queue<TreeNode*> que;
        if(!root) return;
        que.push(root);
        while(!que.empty()){
            root=que.front();
            cout<<root->val<<endl;
            que.pop();
            //從左向右列印，由于佇列先入先出的性質因此先讓左節點入佇列
            if(root->left) que.push(root->left);
            if(root->right) que.push(root->right);
        }    
    }
};

最后，感謝各位讀者耐心看完，筆者會不斷更新演算法、機器學習方面的知識，感興趣的同學可以點一份關注，大家一起學習哦，此外，有問題可以評論區評論或者私聊我，很高興能幫助到大家，