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

一、二叉樹的遞歸遍歷

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

// 遞歸版

// 先序遍歷

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 << " ";

}

二、二叉樹的非遞歸遍歷

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

1.先序遍歷

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

// 迭代版

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);     // 先壓右邊節(jié)點，再壓左邊節(jié)點，這與棧的特性有關(guān)

            }

        }

    }

    cout << endl;

}

2.中序遍歷

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

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.后序遍歷

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

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();      // 彈出的是最晚被壓入棧的數(shù)據(jù)

            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;

}

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