所謂遍歷(Traversal)是指沿著某條搜索路線，依次對樹中每個結點均做一次且僅做一次訪問。訪問結點所做的操作依賴于具體的應用問 題。 遍歷是二叉樹上最重要的運算之一，是二叉樹上進行其它運算之基礎。從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。二叉樹的遍歷也分為遞歸遍歷和非遞歸遍歷。

一、二叉樹的遞歸遍歷

二叉樹的遞歸遍歷相對于非遞歸遍歷比較簡單，具體實現如下：

// 遞歸版

// 先序遍歷

void printPreorder1(TreeNode* head){

    if (head == nullptr){

        return;

    }

    cout << head->value << " ";

    printPreorder1(head->left);

    printPreorder1(head->right);

}

// 中序遍歷

void printInorder1(TreeNode* head){

    if (head == nullptr){

        return;

    }

    printInorder1(head->left);

    cout << head->value << " ";

    printInorder1(head->right);

}

// 后序遍歷

void printPostorder1(TreeNode* head){

    if (head == nullptr){

        return;

    }

    printPostorder1(head->left);

    printPostorder1(head->right);

    cout << head->value << " ";

}

二、二叉樹的非遞歸遍歷

首先我們要清楚，任何算法的遞歸版本都可以改成非遞歸版本，因為函數遞歸調用其實質就是壓棧的過程，那么我們完全可以使用堆棧來模擬這個過程！

1.先序遍歷

我們將數的每個節點壓入棧中，由于是先序遍歷，首先壓入的是根節點，然后彈出（彈出節點時打印信息，且一個循環彈出一個節點），接著是壓入右子樹節點，最后壓入左子樹節點。為什么要這樣呢？由于堆棧是“先進后出”結構，我們想要先打印左子樹，因此最后壓入左子樹，循環這個過程，就達到了我們的目的。

// 迭代版

void printPreorder2(TreeNode* head){

    cout << "Pre Order:" << endl;

    if (head != nullptr){

        stack<TreeNode*> *sta = new stack<TreeNode*>;

        sta->push(head);

        TreeNode* cur = head;

        while(!sta->empty()){

            cur = sta->top();

            sta->pop();

            cout << cur->value << " ";

            if (cur->right != nullptr){

                sta->push(cur->right);

            }

            if (cur->left != nullptr){

                sta->push(cur->left);     // 先壓右邊節點，再壓左邊節點，這與棧的特性有關

            }

        }

    }

    cout << endl;

}

2.中序遍歷

中序時，我們首先去遍歷二叉樹的左分支，并將節點壓入棧中，只到找到最左邊的葉節點，接著彈出（并打印節點），并看其有沒右分支，如果沒有，棧再彈出一個節點（根節點），看其有沒有右分支。每次彈出，都要觀察其是否有右分支，也就是說每個節點都遍歷了兩次！

void printInorder2(TreeNode* head){

     cout << "In Order:" << endl;

     if(head != nullptr){

         stack<TreeNode*>* sta = new stack<TreeNode*>;

         TreeNode* cur = head;

         while(!sta->empty() || cur != nullptr){

             if(cur != nullptr){

                sta->push(cur);

                cur = cur->left;

             }else{

                cur = sta->top();

                sta->pop();

                cout << cur->value << " ";

                cur = cur->right;

             }

         }

     }

     cout << endl;

}

3.后序遍歷

后序遍歷在意思上和前序遍歷相近，而前序遍歷的壓棧順序為：根、右、左。那么如果我們使用兩個堆棧，第一個壓棧順序為：根、左、右，但是在（先序遍歷時）彈出根節點時將根節點壓入第二個堆棧，為什么這里壓棧順序要為左右呢？很簡單，在第一個堆棧中最后壓入右子樹，那么右子樹會最先壓入第二個堆棧，相應的，當第二個堆棧彈出時，右子樹會在左子樹的后面彈出（先進后出）。注意：根節點是最先被壓入第一個棧中的，同時也是最先被壓入第二個棧中的！

void printPostorder2(TreeNode* head){

    cout << "Post Order:" << endl;

    if (head != nullptr){

        stack<TreeNode*>* sta1 = new stack<TreeNode*>;

        stack<TreeNode*>* sta2 = new stack<TreeNode*>;

        TreeNode* cur = head;

        sta1->push(cur);

        while(!sta1->empty()){

            cur = sta1->top();

            sta1->pop();      // 彈出的是最晚被壓入棧的數據

            sta2->push(cur);

            if(cur->left != nullptr){

                sta1->push(cur->left);

            }

            if(cur->right != nullptr){

                sta1->push(cur->right);

            }

        }

        while(!sta2->empty()){

            cur = sta2->top();

            sta2->pop();

            cout << cur->value << " ";

        }

    }

    cout << endl;

}

以上的內容就是關于二二叉樹遞歸遍歷和非遞歸遍歷，總的來說，二叉樹的遞歸遍歷中，先序遍歷、中序遍歷、后序遍歷的模式都是相同的，而在二叉樹非遞歸遍歷中則有所區別。想要深入學習二叉樹的小伙伴，可以收藏本站的數據結構和算法教程，里面對二叉樹的講解十分透徹，讓我們 學起二叉樹來可以事半功倍。