目錄
3.3.1 遍歷（先中后）
二叉樹的遍歷
先序遍歷：
中序遍歷
后序遍歷
tips:
3.3.2 中序非遞歸遍歷
非遞歸算法實(shí)現(xiàn)的基本思路：使用堆棧
中序遍歷的非遞歸算法具體實(shí)現(xiàn)方法為：
3.3.3 層序遍歷
難點(diǎn)
解決方法：
隊(duì)列實(shí)現(xiàn)
思路
有如下二叉樹作為例子：
遍歷過程：（出隊(duì)即printf）
思考：
3.3.4 遍歷應(yīng)用例子
1. 輸出二叉樹中的葉子結(jié)點(diǎn)
2. 求二叉樹高度
3. 二元運(yùn)算表達(dá)式樹及其遍歷
4. 由兩種遍歷序列確定二叉樹
3.3.1 遍歷（先中后）
二叉樹的遍歷
先序遍歷：
遍歷過程：
- 訪問根結(jié)點(diǎn)
- 先序遍歷其左子樹（遞歸遍歷，根結(jié)點(diǎn)左子樹如果也有左右子樹也要遍歷）
- 先序遍歷其右子樹
既然需要遞歸遍歷左右子樹，我們?cè)O(shè)想以下如果直接用遞歸實(shí)現(xiàn)這個(gè)算法（偽碼）：
void PreOrderTraversal( BinTree BT )
{
if( BT ) {
printf(“%d”, BT->Data);
PreOrderTraversal( BT->Left );
PreOrderTraversal( BT->Right );
}
}若有二叉樹為A(B(DF(E))C(G(H)I))，其先序遍歷訪問順序?yàn)椤狝-B-D-F-E-C-G-H-I
中序遍歷
遍歷過程：
- 先序遍歷其左子樹
- 訪問根結(jié)點(diǎn)
- 先序遍歷其右子樹
代碼就直接將Printf放到兩次遞歸中間即可
void PreOrderTraversal( BinTree BT )
{
if( BT ) {
PreOrderTraversal( BT->Left );
printf(“%d”, BT->Data);
PreOrderTraversal( BT->Right );
}
}
后序遍歷
遍歷過程：
- 先序遍歷其右子樹
- 訪問根結(jié)點(diǎn)
- 先序遍歷其左子樹
void PostOrderTraversal( BinTree BT )
{
if( BT ) {
PostOrderTraversal( BT->Left );
PostOrderTraversal( BT->Right);
printf(“%d”, BT->Data);
}
}?
tips:
先序、中序和后序遍歷過程：遍歷過程中經(jīng)過結(jié)點(diǎn)的路線一 樣，只是訪問各結(jié)點(diǎn)的時(shí)機(jī)不同。
3.3.2 中序非遞歸遍歷
非遞歸算法實(shí)現(xiàn)的基本思路：使用堆棧
中序遍歷是按左、根、右的順序，所以以上一節(jié)的樹為例：
- 在一開始遇到A，A有左子樹，所以將A放入堆棧
- 下一個(gè)要處理的是A的左子樹B，B也有左子樹，所以再把B放到堆棧里
- 下一個(gè)是B的左子樹D，D沒有孩子，D放入堆棧后就要出棧了，隨后B出棧。
- 此時(shí)B這棵樹左、根都遍歷完了，接下來處理右子樹F。
- F有左子樹，所以先把F放入堆棧
- F的左子樹E沒有孩子，E入棧然后出棧，F再出棧，最后A的左子樹處理完畢，A也出棧
- 此時(shí)遍歷順序?yàn)镈BEFA，接著處理A的右子樹
- A的右子樹C，C有左子樹，存入棧，處理其左子樹
- G沒有左子樹，所以先入棧后出棧
- G有右子樹H（中序遍歷順序），H沒有左子樹，入棧后緊接著出棧
- 處理完C的左子樹，C可以出棧
- C有右子樹I，I沒有左子樹，入棧后緊接著出棧
- 最后遍歷順序即為：DBEFAGHCI
中序遍歷的非遞歸算法具體實(shí)現(xiàn)方法為：
- 遇到一個(gè)結(jié)點(diǎn)就將其壓入棧，并遍歷其左子樹（若有左子樹的話），
- 當(dāng)左子樹遍歷完畢，就從棧頂彈出這個(gè)結(jié)點(diǎn)并訪問它
- 按結(jié)點(diǎn)右指針去遍歷這個(gè)結(jié)點(diǎn)的右子樹
void InOrderTraversal( BinTree BT )
{
BinTree T=BT;
Stack S = CreatStack( MaxSize ); /*創(chuàng)建并初始化堆棧S*/
while( T || !IsEmpty(S) ){
while(T){
/*一直向左并將沿途結(jié)點(diǎn)壓入堆棧*/
Push(S,T);
T = T->Left;
}
if(!IsEmpty(S)){
T = Pop(S); /*結(jié)點(diǎn)彈出堆棧*/
printf(“%5d”, T->Data); /*（訪問）打印結(jié)點(diǎn)*/
T = T->Right; /*轉(zhuǎn)向右子樹*/
}
}
}也可推知，先序遍歷也能用非遞歸實(shí)現(xiàn)，修改printf位置即可
void PreOrderTraversal( BinTree BT )
{
BinTree T=BT;
Stack S = CreatStack( MaxSize ); /*創(chuàng)建并初始化堆棧S*/
while( T || !IsEmpty(S) ){
while(T){
/*一直向左并將沿途結(jié)點(diǎn)壓入堆棧*/
Push(S,T);
printf(“%5d”, T->Data); /*第一次碰到就打印*/
T = T->Left;
}
if(!IsEmpty(S)){
T = Pop(S); /*結(jié)點(diǎn)彈出堆棧*/
T = T->Right; /*轉(zhuǎn)向右子樹*/
}
}
}但后序遍歷不能簡(jiǎn)單挪動(dòng)位置實(shí)現(xiàn)，因?yàn)楹笮虮闅v在操作完左右子樹后需要返回到根結(jié)點(diǎn)，而且是在第三次經(jīng)過根結(jié)點(diǎn)時(shí)將其pop出去，所以實(shí)現(xiàn)它需要用到兩個(gè)堆棧
1. 初始化兩個(gè)堆棧s1和s2，將根節(jié)點(diǎn)壓入s1中。
2. 從s1中彈出棧頂節(jié)點(diǎn)，將其壓入s2中。
3. 如果該節(jié)點(diǎn)有左子節(jié)點(diǎn)，則將左子節(jié)點(diǎn)壓入s1中。
4. 如果該節(jié)點(diǎn)有右子節(jié)點(diǎn)，則將右子節(jié)點(diǎn)壓入s1中。
5. 重復(fù)步驟2到步驟4，直到s1為空。
6. 從s2中依次彈出節(jié)點(diǎn)并輸出，即可得到后序遍歷序列。
void PostOrder(BinTree BT)
{
BinTree T = BT;
stack S = createstack();
while(T || IsEmpty(S)){
while(T){
push(S, T);
T = T->Left;
}
if(top(S)->Right != NULL){
T = top(S)->Right;
continue;
}
T = pop(S);
printf("%5d", T->data);
while(top(S)->Right == T){
T = pop(S);
printf("%5d", T->data);
}
T = top(S)->Right;
}3.3.3 層序遍歷
難點(diǎn)
除了先中后序，我們還有一種遍歷方式是層序遍歷。二叉樹是一個(gè)二維結(jié)構(gòu)，而遍歷的序列是一個(gè)線性結(jié)構(gòu)，遍歷二叉樹的本質(zhì)是將一個(gè)二維結(jié)構(gòu)變成一維線性結(jié)構(gòu)。
而難點(diǎn)在于，只有通過父結(jié)點(diǎn)才能訪問到左右孩子結(jié)點(diǎn)，再通過子結(jié)點(diǎn)來訪問子結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)，因此如果變成線性結(jié)構(gòu)，線性就意味著一個(gè)點(diǎn)只與另一個(gè)點(diǎn)有關(guān)，而子結(jié)點(diǎn)會(huì)有兩個(gè)，當(dāng)訪問了一個(gè)子結(jié)點(diǎn)之后另一個(gè)子結(jié)點(diǎn)該怎么處理？
解決方法：
用一個(gè)存儲(chǔ)結(jié)構(gòu)來保存暫時(shí)不訪問的結(jié)點(diǎn)。如堆棧、隊(duì)列
隊(duì)列實(shí)現(xiàn)
思路
遍歷從根結(jié)點(diǎn)開始，首先將根結(jié)點(diǎn)入隊(duì)，然后開始執(zhí)行循環(huán)：
- 從隊(duì)列中取出一個(gè)元素
- 訪問該元素所指結(jié)點(diǎn)
- 若該元素所指結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)非空， 則將其左、右孩子的指針順序入隊(duì)。
有如下二叉樹作為例子：
遍歷過程：（出隊(duì)即printf）
A入隊(duì)，第一個(gè)元素為A，隊(duì)列為A
A出隊(duì)，將A的左右兒子BC入隊(duì)，此時(shí)第一個(gè)元素為B，隊(duì)列為BC
B出隊(duì)，將B的左右兒子DF入隊(duì)，此時(shí)第一個(gè)元素為C，隊(duì)列為CDF
C出隊(duì)，將C的左右兒子GI入隊(duì)，此時(shí)第一個(gè)元素是D，隊(duì)列為DFGI
D出隊(duì)，D沒有左右兒子，此時(shí)第一個(gè)元素是F，隊(duì)列為FGI
F出隊(duì)，將F的左兒子E入隊(duì)，此時(shí)第一個(gè)元素是G，隊(duì)列為GIE
G出隊(duì)，將G的右兒子H入隊(duì)，此時(shí)第一個(gè)元素是I，隊(duì)列為IEH
I出隊(duì)，EH都沒有子結(jié)點(diǎn)，依次出隊(duì)
出隊(duì)順序?yàn)椋篈 B C D F G I E H，序列恰好是每一層的結(jié)點(diǎn)順序
void LevelOrderTraversal ( BinTree BT )
{
Queue Q;
BinTree T;
if ( !BT ) return; /* 若是空樹則直接返回 */
Q = CreatQueue( MaxSize ); /*創(chuàng)建并初始化隊(duì)列Q*/
AddQ( Q, BT );
while ( !IsEmptyQ( Q ) ) {
//Step1
T = DeleteQ( Q );
//step2
printf(“%d\n”, T->Data); /*訪問取出隊(duì)列的結(jié)點(diǎn)*/
//Step3
if ( T->Left ) AddQ( Q, T->Left );
if ( T->Right ) AddQ( Q, T->Right );
}
}
思考：
若將層序遍歷中的隊(duì)列實(shí)現(xiàn)修改為堆棧實(shí)現(xiàn)，是否也是一種遍歷方法？
是的，改為堆棧后一般稱其為深度優(yōu)先遍歷，簡(jiǎn)單來說就是訪問根結(jié)點(diǎn)，再依次訪問其左右子樹直到遍歷完整棵樹。
3.3.4 遍歷應(yīng)用例子
1. 輸出二叉樹中的葉子結(jié)點(diǎn)
思路：在遍歷算法中加入一個(gè)“檢測(cè)該結(jié)點(diǎn)左右子樹是否都為空”，即可得知是否為葉子結(jié)點(diǎn)
//以前序遍歷為例
void PreOrderPrintLeaves( BinTree BT )
{
if( BT ) {
//若左右子樹為空，則打印結(jié)點(diǎn)
if ( !BT-Left && !BT->Right )
{
printf(“%d”, BT->Data );
}
PreOrderPrintLeaves ( BT->Left );
PreOrderPrintLeaves ( BT->Right );
}
}
2. 求二叉樹高度
二叉樹的總高度=左右子樹的最大高度+1，因此要求二叉樹總高度，需要先知道左右子樹的高度。后序遍歷的遍歷順序顯然很符合這樣的算法
int PostOrderGetHeight( BinTree BT )
{
int HL, HR, MaxH;
if( BT ) {
HL = PostOrderGetHeight(BT->Left); /*求左子樹的深度*/
HR = PostOrderGetHeight(BT->Right); /*求右子樹的深度*/
MaxH = （HL > HR）? HL : HR; /*取左右子樹較大的深度*/
return ( MaxH + 1 ); /*返回樹的深度*/
}
else return 0; /* 空樹深度為0 */
}
3. 二元運(yùn)算表達(dá)式樹及其遍歷
如下表達(dá)式樹，其作用是對(duì)左右兩顆樹做根結(jié)點(diǎn)運(yùn)算
4. 由兩種遍歷序列確定二叉樹
若已知三種遍歷中的任意兩種遍歷序列，能否唯一確定一顆二叉樹呢？
答案是不能，必須要知道中序遍歷+其他任意遍歷序列才行
若已知先序和中序遍歷序列，如何確定一顆二叉樹？
思路：已知先序第一個(gè)結(jié)點(diǎn)是根結(jié)點(diǎn)，只要在中序中找到一樣的結(jié)點(diǎn)，就能在中序遍歷序列中分割開左子樹和右子樹，再遞歸使用這個(gè)方法分解全部結(jié)點(diǎn)。文章來源：http://www.zghlxwxcb.cn/news/detail-464017.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-464017.html
到了這里，關(guān)于（浙大陳越版）數(shù)據(jù)結(jié)構(gòu) 第三章 樹(上) 3.3 二叉樹的遍歷的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
