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

一、二叉樹(shù)的遞歸遍歷

二叉樹(shù)的遞歸遍歷相對(duì)于非遞歸遍歷比較簡(jiǎn)單，具體實(shí)現(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ù)的非遞歸遍歷

首先我們要清楚，任何算法的遞歸版本都可以改成非遞歸版本，因?yàn)楹瘮?shù)遞歸調(diào)用其實(shí)質(zhì)就是壓棧的過(guò)程，那么我們完全可以使用堆棧來(lái)模擬這個(gè)過(guò)程！

1.先序遍歷

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

// 迭代版

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

            }

        }

    }

    cout << endl;

}

2.中序遍歷

中序時(shí)，我們首先去遍歷二叉樹(shù)的左分支，并將節(jié)點(diǎn)壓入棧中，只到找到最左邊的葉節(jié)點(diǎn)，接著彈出（并打印節(jié)點(diǎn)），并看其有沒(méi)右分支，如果沒(méi)有，棧再?gòu)棾鲆粋€(gè)節(jié)點(diǎn)（根節(jié)點(diǎn)），看其有沒(méi)有右分支。每次彈出，都要觀察其是否有右分支，也就是說(shuō)每個(gè)節(jié)點(diǎn)都遍歷了兩次！

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

后序遍歷在意思上和前序遍歷相近，而前序遍歷的壓棧順序?yàn)椋焊⒂摇⒆蟆Ｄ敲慈绻覀兪褂脙蓚€(gè)堆棧，第一個(gè)壓棧順序?yàn)椋焊⒆蟆⒂遥窃冢ㄏ刃虮闅v時(shí)）彈出根節(jié)點(diǎn)時(shí)將根節(jié)點(diǎn)壓入第二個(gè)堆棧，為什么這里壓棧順序要為左右呢？很簡(jiǎn)單，在第一個(gè)堆棧中最后壓入右子樹(shù)，那么右子樹(shù)會(huì)最先壓入第二個(gè)堆棧，相應(yīng)的，當(dāng)?shù)诙€(gè)堆棧彈出時(shí)，右子樹(shù)會(huì)在左子樹(shù)的后面彈出（先進(jìn)后出）。注意：根節(jié)點(diǎn)是最先被壓入第一個(gè)棧中的，同時(shí)也是最先被壓入第二個(gè)棧中的！

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)于二二叉樹(shù)遞歸遍歷和非遞歸遍歷，總的來(lái)說(shuō)，二叉樹(shù)的遞歸遍歷中，先序遍歷、中序遍歷、后序遍歷的模式都是相同的，而在二叉樹(shù)非遞歸遍歷中則有所區(qū)別。想要深入學(xué)習(xí)二叉樹(shù)的小伙伴，可以收藏本站的數(shù)據(jù)結(jié)構(gòu)和算法教程，里面對(duì)二叉樹(shù)的講解十分透徹，讓我們 學(xué)起二叉樹(shù)來(lái)可以事半功倍。