二叉樹的前中后和層序遍歷詳細圖解（遞歸和非遞歸寫法）
Monster_ii 2018-08-27 17:01:53 37239 收藏 251
分類專欄： 數(shù)據(jù)結(jié)構(gòu)拾遺
版權(quán)
我家門前有兩棵樹，一棵是二叉樹，另一棵也是二叉樹。
遍歷一棵二叉樹常用的有四種方法，前序（PreOrder）、中序（InOrder）、后序（PastOrder）還有層序（LevelOrder）。
前中后序三種遍歷方式都是以根節(jié)點相對于它的左右孩子的訪問順序定義的。例如根->左->右便是前序遍歷，左->根->右便是中序遍歷，左->右->根便是后序遍歷。
而層序遍歷是一層一層來遍歷的。
樹的前中后序遍歷是個遞歸的定義，在遍歷到根節(jié)點的左/右子樹時，也要遵循前/中/后序遍歷的順序，例如下面這棵樹：
前序遍歷：ABDECFG
中序遍歷：DBEAFCG
后序遍歷：DEBFGCA
層序遍歷：ABCDEFG
樹的結(jié)點結(jié)構(gòu)體聲明如下：
語言：C語言（為了省事用到了C++的棧，因為C語言要用棧的話要自己重新寫一個出來，就偷了個懶）
編譯器：VS
typedef char DataType;
typedef struct TreeNode{
DataType data;
struct TreeNode *left;
struct TreeNode *right;
}TreeNode;
1
2
3
4
5
6
7
前序遍歷（先序遍歷）
對于一棵樹的前序遍歷，遞歸的寫法是最簡單的（寫起來），就是將一個大的問題轉(zhuǎn)化為幾個小的子問題，直到子問題可以很容易求解，最后將子問題的解組合起來就是大問題的解。
前序訪問的遞歸寫法
先放代碼，如果看完覺得不太清楚可以看看下面的詳細步驟圖解。
void PreOrder(const TreeNode *root)
{
if (root == NULL) //若結(jié)點為空
{
printf("# ");
return;
}
printf("%c ", root->data); //輸出根節(jié)點的值
PreOrder(root->left); //前序訪問左子樹
PreOrder(root->right); //前序訪問右子樹
}
1
2
3
4
5
6
7
8
9
10
11
比如說還是上面的這顆樹：
訪問根節(jié)點
訪問左子樹
走到這里之后發(fā)現(xiàn)根節(jié)點的左孩子還是一棵子樹，那就將訪問這棵子樹看作是遍歷整顆樹的一個子問題，遍歷這棵子樹的方法和遍歷整顆樹的方法是一樣的。
然后繼續(xù)訪問它的左子樹：
為了理解起來方便一點，我在這里加上了它的兩個為空的左右孩子
然后發(fā)現(xiàn)這（可能）還是一棵子樹，就繼續(xù)用這種方法來對待這顆子樹，就是繼續(xù)訪問它的左子樹：
發(fā)現(xiàn)這是一個空節(jié)點，那就直接返回，去訪問它的右子樹：
發(fā)現(xiàn)還是一個空節(jié)點，那么繼續(xù)返回，這時候D和它的左右孩子結(jié)點都訪問過了，繼續(xù)返回，應(yīng)該訪問B的右子樹了。
然后就和D結(jié)點一樣的處理方法，->左孩子，發(fā)現(xiàn)是空，返回->右孩子，發(fā)現(xiàn)還是空，繼續(xù)返回，發(fā)現(xiàn)這時候B的左右孩子都訪問過了，繼續(xù)返回。
訪問右子樹
然后和處理A的左子樹的方法一樣，最后訪問到G結(jié)點的右子樹時，發(fā)現(xiàn)是空，就返回，這時候樹的所有節(jié)點都已經(jīng)訪問過了，所以可以一路返回到A結(jié)點的右子樹完的地方，整個遞歸就結(jié)束了。
最后輸出的前序訪問序列便是：ABDECFG
前序訪問的非遞歸寫法
還是先上代碼：
void PreOrderLoop(TreeNode *root)
{
std::stack<TreeNode *> s;
TreeNode *cur, *top;
cur = root;
while (cur != NULL || !s.empty())
{
while (cur != NULL)
{
printf("%c ", cur->data);
s.push(cur);
cur = cur->left;
}
top = s.top();
s.pop();
cur = top->right;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
非遞歸的寫法比遞歸寫法要麻煩一點，要用到棧來存儲樹的結(jié)點，在理解非遞歸方法的時候要重點理解棧中保存的元素的共同點是什么，在前序訪問中，棧中元素都是自己和自己的左孩子都訪問過了，而右孩子還沒有訪問到的節(jié)點，如果不太懂可以看下面的詳細步驟圖解。
首先我們要用一個指針（cur）來指向當前訪問的結(jié)點
發(fā)現(xiàn)這個節(jié)點不為空，就將它的數(shù)據(jù)輸出，然后將這個節(jié)點的地址（圖上的棧中寫了節(jié)點的值是為了便于理解，實際上棧中保存的是節(jié)點地址）壓棧。
再去訪問它的左子樹，發(fā)現(xiàn)左孩子結(jié)點依舊不為空，繼續(xù)輸出并壓棧。
同理壓棧D節(jié)點
然后訪問D的左孩子，發(fā)現(xiàn)為空，便從棧中拿出棧頂結(jié)點top，讓cur = top->right,便訪問到了D的右孩子。
發(fā)現(xiàn)D的右孩子還是為空，這個看一下棧，發(fā)現(xiàn)棧不為空，說明還存在右孩子沒被訪問過的節(jié)點，就繼續(xù)從棧中拿出棧頂結(jié)點top，讓cur = top->right，便訪問到了B的右孩子。
B的右孩子處理方法和D一樣，然后再從棧中拿出A節(jié)點，去訪問A的右孩子C，在訪問到G節(jié)點的右孩子之后，發(fā)現(xiàn)當前節(jié)點cur為空，棧中也沒有元素可以取出來了，這時候就代表整棵樹都被訪問過了，便結(jié)束循環(huán)。
最后輸出的前序訪問序列便是：ABDECFG
中序遍歷
對于一棵樹的中序遍歷，和前序一樣，可以分為遞歸遍歷和非遞歸遍歷，遞歸遍歷是相對簡單的，還是子問題思想，將一個大問題分解，直到可以解決，最后解決整個大問題。
中序遍歷的遞歸寫法
還是先上代碼：
void InOrder(const TreeNode *root)
{
if (root == NULL) //判斷節(jié)點是否為空
{
printf("# ");
return;
}
InOrder(root->left); //中序遍歷左子樹
printf("%c ", root->data); //訪問節(jié)點值
InOrder(root->right); //中序遍歷右子樹
}
1
2
3
4
5
6
7
8
9
10
11
12
從根節(jié)點進入
發(fā)現(xiàn)根節(jié)點不為空，訪問左子樹
發(fā)現(xiàn)不為空，繼續(xù)訪問左子樹
發(fā)現(xiàn)不為空，繼續(xù)訪問左子樹
這時root為空了，就返回去訪問它的根節(jié)點，剛才的訪問只是路過，并沒有真正地遍歷節(jié)點的信息，在返回途中才是真正地遍歷到了節(jié)點的信息。
訪問到了D節(jié)點，下來要訪問的是D的右孩子，因為D的左孩子已經(jīng)訪問過了。
發(fā)現(xiàn)還是空，就返回，而它的根節(jié)點D也訪問過了，那么就繼續(xù)返回，該訪問D節(jié)點的父節(jié)點B了。
B訪問過后下來要訪問的是B的右孩子，因為是從B的左子樹回來的路，B的左孩子已經(jīng)訪問過了。
然后和訪問D一樣，->左孩子，為空，返回訪問根節(jié)點E，->右孩子，為空（這部分就不畫了，和D節(jié)點的訪問是一樣的），最后返回，B已經(jīng)訪問過了，就繼續(xù)返回，至此，整顆樹的左子樹訪問完了。
訪問B的根節(jié)點A
遍歷A的右子樹
遍歷右子樹的過程和左子樹一樣，還是左->根->右的中序遍歷下去，直到遍歷到G的右孩子，發(fā)現(xiàn)為空，就返回，因為右子樹都遍歷過了，所以可以一直返回到root為A節(jié)點的那一層遞歸，整個遍歷結(jié)束。
最后輸出的中序訪問序列為：DBEAFCG
非遞歸寫法
中序訪問的非遞歸寫法和前序一樣，都要用到一個棧來輔助存儲，不一樣的地方在于前序訪問時，棧中保存的元素是右子樹還沒有被訪問到的節(jié)點的地址，而中序訪問時棧中保存的元素是節(jié)點自身和它的右子樹都沒有被訪問到的節(jié)點地址。
先上代碼：
void InOrderLoop(TreeNode *root)
{
std::stack<TreeNode *> s;
TreeNode *cur;
cur = root;
while (cur != NULL || !s.empty())
{
while (cur != NULL)
{
s.push(cur);
cur = cur->left;
}
cur = s.top();
s.pop();
printf("%c ", cur->data);
cur = cur->right;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
cur指針一路沿著最左邊往下訪問，路過的節(jié)點全部壓棧，直到遇到空節(jié)點
從棧中取出棧頂節(jié)點top，輸出棧頂結(jié)點的值并使cur = top->right，從第一步開始去遍歷top的右子樹。
遍歷完之后，cur走到了D節(jié)點的右孩子，發(fā)現(xiàn)cur 為空，但棧中還有元素，就重復第二步
這時候，cur走到了E節(jié)點的右孩子，發(fā)現(xiàn)cur 為空，但棧中還有元素，就繼續(xù)重復第二步，之后cur = top->right，cur指針繼續(xù)去遍歷A節(jié)點的右子樹，從第一步開始
訪問到F的左孩子節(jié)點發(fā)現(xiàn)是空，這時候棧中還有元素，就重復第二步
照這個規(guī)則依次訪問下去，最后會訪問到G節(jié)點的右孩子，這時候cur為空，棧也空了，就代表所有節(jié)點已經(jīng)遍歷完了，就結(jié)束循環(huán)，遍歷完成。
最后輸出的中序訪問序列為:DBEAFCG
后序遍歷
后序遍歷還是分遞歸版本和非遞歸版本，后序遍歷的遞歸版本和前序中序很相似，就是輸出根節(jié)點值的時機不同，而后序遍歷的非遞歸版本則要比前序和中序的要難一些，因為在返回根節(jié)點時要分從左子樹返回和右子樹返回兩種情況，從左子樹返回時不輸出，從右子樹返回時才需要輸出根節(jié)點的值。
遞歸寫法
先上代碼：
void PostOrder(TreeNode *root)
{
if (root == NULL)
{
printf("# ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%c ", root->data);
}
1
2
3
4
5
6
7
8
9
10
11
后序遍歷的遞歸版本和前中序非常相似，就是輸出根節(jié)點值的時機不同，詳細圖解這里就不畫了，可以聯(lián)系前中序的遞歸版本來理解。
后序遍歷的非遞歸寫法
后序遍歷的非遞歸同樣要借助一個棧來保存元素，棧中保存的元素是它的右子樹和自身都沒有被遍歷到的節(jié)點，與中序遍歷不同的是先訪問右子樹，在回來的時候再輸出根節(jié)點的值。需要多一個last指針指向上一次訪問到的節(jié)點，用來確認是從根節(jié)點的左子樹返回的還是從右子樹返回的。
先上代碼：
void PostOrderLoop(TreeNode *root)
{
std::stack<TreeNode *> s;
TreeNode *cur, *top, *last = NULL;
cur = root;
while (cur != NULL || !s.empty())
{
while (cur != NULL)
{
s.push(cur);
cur = cur->left;
}
top = s.top();
if (top->right == NULL || top->right == last){
s.pop();
printf("%c ", top->data);
last = top;
}
else {
cur = top->right;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
還是沿著左子樹一路往下走，將路過的節(jié)點都壓棧，直到走到空節(jié)點。
然后從棧中看一下棧頂元素（只看一眼，用top指針記下，先不出棧），如果top節(jié)點沒有右子樹，或者last等于top的右孩子，說明top的右子樹不存在或者遍歷過了，就輸出top節(jié)點的值，并將棧頂元素pop掉（出棧），反之則是從左子樹回到根節(jié)點的，接下來要去右子樹。
如圖，top的右孩子為空，說明右子樹不存在，就可以輸出top的值并pop掉棧頂了，這時候用last指針記下top指向的節(jié)點，代表上一次處理的節(jié)點。（這一過程cur始終沒有動，一直指向空）
繼續(xù)從棧頂看一個元素記為top，然后發(fā)現(xiàn)top的右孩子不為空，而且last也不等于top->right，就使cur = top->right，回到第一步，用同樣的方法來處理top的右子樹，下一次回來的時候，last指針指向的是E節(jié)點。
這時候發(fā)現(xiàn)top的右孩子不為空，但是last等于top->right，說明top的右子樹遍歷完成，下一步就要輸出top的值并且將這個節(jié)點出棧，下一次再從棧中看一個棧頂元素A即為top。
這時候再比較，發(fā)現(xiàn)top的right不為空，而且last也不等于top->right，說明top有右子樹并且還沒有遍歷過，就讓cur = top->right，回到第一步用同樣的方法來遍歷A的右子樹。
到最后，cur訪問到了G的左孩子，而top也一路出棧到了A節(jié)點，發(fā)現(xiàn)cur為空，并且棧中也為空，這時候便代表整個樹已經(jīng)遍歷完成，結(jié)束循環(huán)。
最后輸出的中序訪問序列為:DEBFGCA
層序遍歷
層序遍歷是比較接近人的思維方式的一種遍歷方法，將二叉樹的每一層分別遍歷，直到最后的葉子節(jié)點被全部遍歷完，這里要用到的輔助數(shù)據(jù)結(jié)構(gòu)是隊列，隊列具有先進先出的性質(zhì)。
上代碼：
void LevelOrder(TreeNode *root)
{
std::queue<TreeNode *> q;
TreeNode *front;
if (root == NULL)return;
q.push(root);
while (!q.empty())
{
front = q.front();
q.pop();
if (front->left)
q.push(front->left);
if (front->right)
q.push(front->right);
printf("%c ", front->data);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
層序遍歷的思路是，創(chuàng)建一個隊列，先將根節(jié)點（A）入隊，然后用front指針將根節(jié)點記下來，再將根節(jié)點出隊，接下來看front節(jié)點（也就是剛才的根節(jié)點）有沒有左孩子或右孩子，如果有，先左（B）后右（C）入隊，最后輸出front節(jié)點的值，只要隊列還不為空，就說明還沒有遍歷完，就進行下一次循環(huán)，這時的隊頭元素（front）則為剛才入隊的左孩子（B），然后front出隊，再把它的左右孩子拉進來（如果有），因為隊列的先進先出性質(zhì)，B的左右孩子DE是排在C后面的，然后輸出B，下一次循環(huán)將會拉人C的左右孩子FG，最后因為FG沒有左右孩子，一直出隊，沒有入隊元素，隊列遲早會變?yōu)榭?，當隊列為空時，整顆樹就層序遍歷完成了，結(jié)束循環(huán)。
根節(jié)點入隊，并用front指針標記
隊頭出隊，并將左右孩子拉進隊列
重復1，2
直到隊列為空
這時候便代表整個樹遍歷完成，結(jié)束循環(huán)。
最后輸出的層序訪問序列為:ABCDEF
————————————————
版權(quán)聲明：本文為CSDN博主「Monster_ii」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/Monster_ii/article/details/82115772
