二叉樹的遍歷——遞迴和非遞迴

二 叉樹是一種非常重要的資料結構，很多其它資料結構都是基於二叉樹的基礎演變而來的。對於二叉樹，有前序、中序以及後序三種遍歷方法。因為樹的定義本身就是 遞迴定義，因此採用遞迴的方法去實現樹的三種遍歷不僅容易理解而且程式碼很簡潔。而對於樹的遍歷若採用非遞迴的方法，就要採用棧去模擬實現。在三種遍歷中， 前序和中序遍歷的非遞迴演算法都很容易實現，非遞迴後序遍歷實現起來相對來說要難一點。

一.前序遍歷

前序遍歷按照“根結點-左孩子-右孩子”的順序進行訪問。

1.遞迴實現

[cpp] view plaincopyvoid pre_order(BTree *root) { if(root != NULL)//必不可少的條件,遞迴的出口 { printf("%2c",root->key); //訪問根結點 pre_order(root->lchild); //前序遍歷左子樹 pre_order(root->rchild); //前序遍歷右子樹 } }

2.非遞迴實現

根據前序遍歷訪問的順序，優先訪問根結點，然後再分別訪問左孩子和右孩子。即對於任一結點，其可看做是根結點，因此可以直接訪問，訪問完之後，若其左孩子不為空，按相同規則訪問它的左子樹；當訪問其左子樹時，再訪問它的右子樹。因此其處理過程如下：

對於任一結點P：

1)訪問結點P，並將結點P入棧;

2)判斷結點P的左孩子是否為空，若為空，則取棧頂結點並進行出棧操作，並將棧頂結點的右孩子置為當前的結點P，迴圈至1);若不為空，則將P的左孩子置為當前的結點P;

3)直到P為NULL並且棧為空，則遍歷結束。

12345678910111213141516171819

二.中序遍歷

中序遍歷按照“左孩子-根結點-右孩子”的順序進行訪問。

1.遞迴實現

[cpp] view plaincopyvoid in_order(BTree* root) { //必不可少的條件,遞迴的出口 if(root != NULL) { in_order(root->lchild); printf("%2c",root->data); in_order(root->rchild); } }

2.非遞迴實現

根據中序遍歷的順序，對於任一結點，優先訪問其左孩子，而左孩子結點又可以看做一根結點，然後繼續訪問其左孩子結點，直到遇到左孩子結點為空的結點才進行訪問，然後按相同的規則訪問其右子樹。因此其處理過程如下：

對於任一結點P，

1)若其左孩子不為空，則將P入棧並將P的左孩子置為當前的P，然後對當前結點P再進行相同的處理；

2)若其左孩子為空，則取棧頂元素並進行出棧操作，訪問該棧頂結點，然後將當前的P置為棧頂結點的右孩子；

3)直到P為NULL並且棧為空則遍歷結束

[cpp] view plaincopy//非遞迴中序遍歷 void in_order(BTree *root) { stack<BTree*> s; BTree *p = root; while (p != NULL || !s.empty()) { while(p != NULL) { s.push(p); p = p->lchild; } if (!s.empty()) { p = s.top(); cout<<p->data<<" "; s.pop(); p = p->rchild; } } }

三.後序遍歷

後序遍歷按照“左孩子-右孩子-根結點”的順序進行訪問。

1.遞迴實現

[cpp] view plaincopyvoid post_order(BTree* root) { //必不可少的條件,遞迴的出口 if(root != NULL) { post_order(root->lchild); post_order(root->rchild); printf("%2c",root->data); } }

2.非遞迴實現

後序遍歷的非遞迴實現是三種遍歷方式中最難的一種。因為在後序遍歷中，要保證左孩子和右孩子都已被訪問並且左孩子在右孩子前訪問才能訪問根結點，這就為流程的控制帶來了難題。下面介紹兩種思路。

第一種思路：對於任一結點P，將其入棧，然後沿其左子樹一直往下搜尋，直到搜尋到沒有左孩子的結點，此時該結點出現在棧頂，但是此時不能將其出棧並訪問， 因此其右孩子還未被訪問。所以接下來按照相同的規則對其右子樹進行相同的處理，當訪問完其右孩子時，該結點又出現在棧頂，此時可以將其出棧並訪問。這樣就 保證了正確的訪問順序。可以看出，在這個過程中，每個結點都兩次出現在棧頂，只有在第二次出現在棧頂時，才能訪問它。因此需要多設定一個變數標識該結點是 否是第一次出現在棧頂。

方 法：要保證根結點在左孩子和右孩子訪問之後才能訪問，因此對於任一結點P，先將其入棧。如果P不存在左孩子和右孩子，則可以直接訪問它；或者P存在左孩子 或者右孩子，但是其左孩子和右孩子都已被訪問過了，則同樣可以直接訪問該結點。若非上述兩種情況，則將P的右孩子和左孩子依次入棧，這樣就保證了每次取棧 頂元素的時候，左孩子在右孩子前面被訪問，左孩子和右孩子都在根結點前面被訪問。

[cpp] view plaincopy//非遞迴後序遍歷 void post_order(BTree* root) { stack<BTree*> s; //當前結點 BTree *cur = NULL; //前一次訪問的結點 BTree *pre = NULL; s.push(root); while(!s.empty()) { cur = s.top(); if( (cur->lchild == NULL && cur->rchild == NULL) || (pre != NULL && (pre == cur->lchild || pre == cur->rchild))) { //如果當前結點沒有孩子結點或者孩子節點都已被訪問過 cout<<cur->data<<" "; s.pop(); pre = cur; } else { if(cur->rchild != NULL) s.push(cur->rchild); if(cur->lchild!=NULL) s.push(cur->lchild); } } }

四、層次遍歷

//採用STL中的queue處理

[cpp] view plaincopy#include <queue> void layerOrder(BTree *tree) { if (tree == NULL) return; queue<BTree *> q; q.push(tree); BTree *p = NULL; while (!q.empty()) { p = q.front(); visit(p); q.pop(); if (p->lchild != NULL) q.push(p->lchild); if (p->rchild != NULL) q.push(p->rchild); } }

五.二叉樹的其他一些應用

1.求二叉樹的深度

若一棵二叉樹為空，則它的深度為0，否則它的深度等於左子樹和右子樹中的最大深度加1. 設nLeft為左子樹的深度，nRight為右子樹的深度，

則二叉樹的深度為：max(nLeft , nRight)+1.

12345678910

2.從二叉樹中查詢值為x的結點。若存在，則由x帶回完整值並返回真，否則返回假

該演算法類似於前序遍歷，若樹為空則返回false結束遞迴，若樹根結點的值就等於x的值，則把結點值賦給x後返回true結束遞迴，否則先向左子樹查詢，若找到則返回true結束遞迴，否則再向右子樹查詢，若找到則返回true結束遞迴，若左，右子樹均未找到則返回false結束遞迴。

123456789101112131415161718192021

3.統計出二叉樹中等於給定值x的結點個數，結果由函式返回。

此演算法也是一個遞迴過程，若樹為空則返回0結束遞迴，若樹根結點的值等於x的值則返回左、右兩棵子樹中等於x結點的個數加1，否則只應返回左、右兩棵子樹中等於x結點的個數。

123456789

4.返回x結點所處的層號，若不存在值為x的結點則返回0.

1234567891011121314151617181920212223

5.從二叉樹中找出所有結點的最大值並返回，若為空樹則返回0.

123456789101112131415

6.求二叉樹中所有結點數。

1234567

7.求二叉樹中所有葉子結點數

12345678910