ch62遍歷二叉樹和線索二叉樹

1、1第第6 6章章 樹和二叉樹樹和二叉樹（Tree & Binary TreeTree & Binary Tree）6.1 樹的基本概念樹的基本概念6.2 二叉樹二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 樹和森林樹和森林6.5 赫夫曼樹及其應(yīng)用赫夫曼樹及其應(yīng)用二叉樹的運算二叉樹的運算26.3 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹一、一、 遍歷二叉樹遍歷二叉樹遍歷定義：遍歷定義：遍歷用途：遍歷用途：遍歷方法：遍歷方法：指按某條搜索路線遍訪每個結(jié)點且指按某條搜索路線遍訪每個結(jié)點且不重復(fù)（又稱周游）。不重復(fù)（又稱周游）。它是樹結(jié)構(gòu)插入、刪除、修改、查找它是樹結(jié)構(gòu)

2、插入、刪除、修改、查找和排序運算的前提，是二叉樹一切運和排序運算的前提，是二叉樹一切運算的基礎(chǔ)和核心。算的基礎(chǔ)和核心。對每個結(jié)點的查看通常都是對每個結(jié)點的查看通常都是“先左先左后右后右”。Traversing Binary Tree廣度優(yōu)先和深度優(yōu)先廣度優(yōu)先和深度優(yōu)先3遍歷規(guī)則：遍歷規(guī)則：v 二叉樹由根、左子樹、右子樹構(gòu)成，定義為二叉樹由根、左子樹、右子樹構(gòu)成，定義為D、 L、R注：注：“先、中、后先、中、后”的意思是指的意思是指訪問的根結(jié)點訪問的根結(jié)點D D是先于子樹出現(xiàn)是先于子樹出現(xiàn)還是后于子樹出現(xiàn)。還是后于子樹出現(xiàn)。v D、 L、R的組合定義了六種可能的遍歷方案：的組合定義了六種可能的遍

3、歷方案：DLR, LDR, LRD, DRL, RDL, RLDv 若限定若限定先左后右先左后右，則有三種實現(xiàn)方案：，則有三種實現(xiàn)方案： DLR LDR LRD先先序遍歷序遍歷 中中序遍歷序遍歷 后后序遍歷序遍歷 4例例1 1：先序遍歷的結(jié)果是：先序遍歷的結(jié)果是：中序遍歷的結(jié)果是：中序遍歷的結(jié)果是：后序遍歷的結(jié)果是：后序遍歷的結(jié)果是： A B CD E口訣：口訣：DLR先序遍歷，即先根再左、右先序遍歷，即先根再左、右LDR中序遍歷，即先左再根后右中序遍歷，即先左再根后右LRD后序遍歷，即先左、右再根后序遍歷，即先左、右再根層次遍歷：層次遍歷：ABCDE5+*A*/EDCB先序遍歷結(jié)果：先序遍歷

4、結(jié)果：+ * * / A B C D E前綴表示法前綴表示法中序遍歷結(jié)果：中序遍歷結(jié)果：A / B * C * D + E后序遍歷結(jié)果：后序遍歷結(jié)果：A B / C * D * E +后綴表示法后綴表示法例例2 2：用二叉樹表示算術(shù)表達式用二叉樹表示算術(shù)表達式層次遍歷結(jié)果：層次遍歷結(jié)果：+*E*D/CAB6abadefgff n個結(jié)點個結(jié)點. . . . . 例例3 3：畫出所有中序遍歷序列和后序遍歷序列一致的：畫出所有中序遍歷序列和后序遍歷序列一致的 二叉樹的所有形態(tài)二叉樹的所有形態(tài). .分析：中序遍歷分析：中序遍歷: LDR-LD: LDR-LD 后序遍歷后序遍歷: LRD-LD . :

5、LRD-LD . 結(jié)論：如果中序和后序結(jié)論：如果中序和后序（前序）遍歷一致，（前序）遍歷一致，則二叉樹沒則二叉樹沒有右（左）子樹有右（左）子樹7由此可以看出：由此可以看出：（1 1）遍歷操作實際上是將非線性結(jié)構(gòu)線性化的過程，）遍歷操作實際上是將非線性結(jié)構(gòu)線性化的過程，其結(jié)果為線性序列；其結(jié)果為線性序列；（2 2）遍歷操作是一個遞歸的過程，因此，這三種遍歷）遍歷操作是一個遞歸的過程，因此，這三種遍歷操作的算法可以用遞歸函數(shù)實現(xiàn)。操作的算法可以用遞歸函數(shù)實現(xiàn)。 DLR ( BiTree T ) if (T) /非空二叉樹非空二叉樹 printf(“%d”,T-data); /訪問根結(jié)點訪問根結(jié)點D

6、 D DLR(T-lchild); /遞歸遍歷左子樹遞歸遍歷左子樹 DLR(T-rchild); /遞歸遍歷右子樹遞歸遍歷右子樹 return(0); 8 LDR(BiTree T) if(T) LDR(T-lchild); printf(“%d”,T-data); LDR(T-rchild); return(0); （1） 從前面的三種遍歷算法可以知道：如果將從前面的三種遍歷算法可以知道：如果將printf語句抹去，從遞歸的角度看，這三種算法是完全相同語句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的的，或者說這三種遍歷算法的訪問路徑是相同的，只訪問路徑是相同的，只是訪

7、問結(jié)點的時機不同是訪問結(jié)點的時機不同。對遍歷的分析：對遍歷的分析：LRD (BiTree T) if(T) LRD(T-lchild); LRD(T-rchild); printf(“%d”,T-data); return(0);DLR輸出序列：輸出序列：LDR輸出序列：輸出序列：LRD輸出序列：輸出序列：例例4 寫出該樹三種遍歷的輸出序列：寫出該樹三種遍歷的輸出序列：A B D E G HI J C FD B G EI H J A C FD G I JH E B F C A10分析：分析：由先序遍歷特征，根結(jié)點必在先序序列頭部；由先序遍歷特征，根結(jié)點必在先序序列頭部；由中序遍歷特征，根結(jié)點必

8、在其中間，而且其左部由中序遍歷特征，根結(jié)點必在其中間，而且其左部必全部是左子樹的子孫，其右部必全部是右子樹的子必全部是左子樹的子孫，其右部必全部是右子樹的子孫；孫；例：僅知二叉樹的先序序列例：僅知二叉樹的先序序列“abcdefg” abcdefg” 不能唯不能唯一確定一棵二叉樹，如果同時已知二叉樹的中序一確定一棵二叉樹，如果同時已知二叉樹的中序序列序列“cbdaegf”,cbdaegf”,則會如何？則會如何？11a b c d e f gc b d a e g f例如例如: :aab bccddeeffggabcdefg先序序列先序序列中序序列中序序列12已知中序遍歷：已知中序遍歷：B D C

9、 E A F H G已知后序遍歷：已知后序遍歷：D E C B H G F A（B D C E）（ F H G）A （D C E）BFGHCD EABBACCD C E例例5：試畫出該樹。試畫出該樹。13從虛線的出發(fā)點到終點的路從虛線的出發(fā)點到終點的路徑徑上，每個結(jié)點經(jīng)過上，每個結(jié)點經(jīng)過3 3次次。AFEDCBG第第1 1次次經(jīng)過時訪問，是經(jīng)過時訪問，是先序先序遍歷遍歷第第2 2次次經(jīng)過時訪問，是經(jīng)過時訪問，是中序中序遍歷遍歷第第3 3次次經(jīng)過時訪問，是經(jīng)過時訪問，是后序后序遍歷遍歷 任何一棵二叉樹都可以將它的外部輪廓用一條線任何一棵二叉樹都可以將它的外部輪廓用一條線繪制出來，我們將它稱為二叉

10、樹的包線。如圖：繪制出來，我們將它稱為二叉樹的包線。如圖：14（2 2） 二叉樹遍歷的時間效率和空間效率二叉樹遍歷的時間效率和空間效率 時間效率時間效率: : /每個結(jié)點只訪問一次每個結(jié)點只訪問一次 空間效率空間效率: : /棧占用的最大輔助空間棧占用的最大輔助空間精確值：樹深為精確值：樹深為k k的遞歸遍歷需要的遞歸遍歷需要k+1k+1個輔助單元個輔助單元遞歸遍歷算法的應(yīng)用舉例遞歸遍歷算法的應(yīng)用舉例2 2、統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)、統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)3 3、求二叉樹的深度、求二叉樹的深度1 1、建立二叉樹的二叉鏈表、建立二叉樹的二叉鏈表15例例1 1：建立二叉樹的二叉鏈表。即：如何

11、把二叉樹存入建立二叉樹的二叉鏈表。即：如何把二叉樹存入 電腦內(nèi)？電腦內(nèi)？怎樣建樹怎樣建樹？（教材（教材P131P131算法算法6.46.4）考慮考慮2 2：輸入結(jié)點時怎樣表示：輸入結(jié)點時怎樣表示“無孩子無孩子”？ 用空格字符表示用空格字符表示無孩子無孩子或指針為空或指針為空考慮考慮1 1：以何種遍歷方式來輸入和建樹？：以何種遍歷方式來輸入和建樹？ 采用完全先序遍歷，以字符串的形式輸入。采用完全先序遍歷，以字符串的形式輸入。例：將左圖所示二叉樹按完全先序例：將左圖所示二叉樹按完全先序遍歷次序輸入：遍歷次序輸入：A B C D E G F (/n)16Status CreateBiTree(BiT

12、ree &T) scanf( “c%”, &ch); if (ch= ) T = NULL; else if ( !(T = new BiTNode) exit(OVERFLOW); T-data = ch; / 生成根結(jié)點 CreateBiTree(T-lchild); / 構(gòu)造左子樹 CreateBiTree(T-rchild); / 構(gòu)造右子樹 return OK; / CreateBiTree17例例2 2：【嚴(yán)題集嚴(yán)題集6.426.42】編寫遞歸算法，計算二叉樹中編寫遞歸算法，計算二叉樹中葉子結(jié)點的數(shù)目。葉子結(jié)點的數(shù)目。 思路：思路：這個操作可以使用三種遍歷順序中的任何一種，這個操作

13、可以使用三種遍歷順序中的任何一種，只是需要只是需要將訪問操作變成判斷該結(jié)點是否為葉子結(jié)點將訪問操作變成判斷該結(jié)點是否為葉子結(jié)點，如果是葉子結(jié)點將計數(shù)器如果是葉子結(jié)點將計數(shù)器countcount加加1 1即可。下面這個算法即可。下面這個算法是利用先序遍歷實現(xiàn)的。是利用先序遍歷實現(xiàn)的。void CountLeaf (BiTree T, int &count) if ( T ) if (!T-lchild)& (!T-rchild) count+; / / 對葉子結(jié)點計數(shù)對葉子結(jié)點計數(shù) CountLeaf( T-lchild, count); CountLeaf( T-rchild, count);

14、 /if / CountLeaf18例例3 3：求二叉樹的深度求二叉樹的深度 思路：思路：二叉樹的深度應(yīng)為其左、右子樹深度的最大值二叉樹的深度應(yīng)為其左、右子樹深度的最大值加加1 1。由此，需先分別求得左、右子樹的深度，由此，需先分別求得左、右子樹的深度，算法中算法中“訪問結(jié)點訪問結(jié)點”的操作為的操作為: :求得左、右子樹深度的最大值，求得左、右子樹深度的最大值，然后加然后加 1 1 。相當(dāng)于采用后序遍歷。相當(dāng)于采用后序遍歷。int Depth (BiTree T ) if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); dept

15、hRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight)? depthLeft : depthRight; return depthval; 19 算法思路：算法思路：既然要求從上到下，從左到右，則既然要求從上到下，從左到右，則存放各子樹結(jié)點的指針是個好辦法，此時存放各子樹結(jié)點的指針是個好辦法，此時絕不能用絕不能用遞歸遞歸算法。算法。技巧：技巧：當(dāng)根結(jié)點入隊后，令其左、右孩子結(jié)點入隊，而當(dāng)根結(jié)點入隊后，令其左、右孩子結(jié)點入隊，而左孩子出隊時又令它的左右孩子結(jié)點入隊，左孩子出隊時又令它的左右孩子結(jié)點入隊，由此便由此便可產(chǎn)生按

16、層次輸出的效果?？僧a(chǎn)生按層次輸出的效果。ABFGHCD EA隊頭隊頭隊尾隊尾（1）A入隊，入隊，A為隊首元素，故為隊首元素，故A出隊；出隊； “出對出對”的意思就是該元素被訪問。的意思就是該元素被訪問。 A出隊后，馬上將出隊后，馬上將A的左右孩子的左右孩子BF都入隊；都入隊；BF(2)隊首元素為隊首元素為B，將它出隊（訪問）；，將它出隊（訪問）；B出對后，馬上將出對后，馬上將B的左右孩子的左右孩子C入隊；入隊；（3）隊首元素為）隊首元素為F，將它出隊；，將它出隊；F出隊后，出隊后，馬上將馬上將F的左右孩子的左右孩子G入隊；依次類推。入隊；依次類推。c出隊順序為：出隊順序為：A B F C G

17、D E HGD E21void void LayerOrderLayerOrder(Bitree T) (Bitree T) /層次遍歷二叉樹層次遍歷二叉樹 InitQueue(Q); InitQueue(Q); /建一個空隊（初始化隊列）建一個空隊（初始化隊列） EnQueue(Q,T); EnQueue(Q,T); /根結(jié)點入隊根結(jié)點入隊 while(while( !QueueEmpty(Q)!QueueEmpty(Q) ) ) DeQueue(Q, &p);DeQueue(Q, &p); /隊首結(jié)點出隊隊首結(jié)點出隊( (送入送入p)p) visit(p); visit(p); if(p-

18、lchild) if(p-lchild) EnQueue(Q,p-lchild);EnQueue(Q,p-lchild); /左孩子入隊左孩子入隊 if(p-rchild) if(p-rchild) EnQueue(Q,p-rchild);EnQueue(Q,p-rchild);/右孩子入隊右孩子入隊 /LayerOrder /LayerOrder 當(dāng)孩子為空時不要當(dāng)孩子為空時不要將空指針入隊將空指針入隊22算法思路：算法思路：完全二叉樹的特點是：完全二叉樹的特點是：沒有左子樹空而右沒有左子樹空而右子樹單獨存在的情況子樹單獨存在的情況( (前前k-1k-1層都是滿的，且第層都是滿的，且第k k

19、層左邊層左邊也滿）。也滿）。技巧技巧: :按按層次遍歷層次遍歷方式，先把所有結(jié)點（不管當(dāng)前結(jié)點方式，先把所有結(jié)點（不管當(dāng)前結(jié)點是否有左右孩子）是否有左右孩子）都入隊列都入隊列. .若為完全二叉樹若為完全二叉樹, ,則層次則層次遍歷時得到的肯定是一個連續(xù)的不包含空指針的序列遍歷時得到的肯定是一個連續(xù)的不包含空指針的序列. .如果序列中出現(xiàn)了空指針，則說明不是完全二叉樹。如果序列中出現(xiàn)了空指針，則說明不是完全二叉樹。int IsFull_Bitree(BiTree T /是完全二叉樹返回1,否則返0 InitQueue(Q); /建隊（初始化隊列） flag=0; /標(biāo)志初始化 23EnQueue

20、(Q,T); /根結(jié)點入隊（空指針也要入隊） while(!QueueEmpty(Q) while(!QueueEmpty(Q) /直到隊列空為止 DeQueue(Q,p);DeQueue(Q,p); /隊首結(jié)點出隊(送入p) if(!p) flag=1;if(!p) flag=1; /隊首結(jié)點為空則標(biāo)志變 else if (flag) return 0;else if (flag) return 0; /無左孩子有右孩子 elseelse EnQueue(Q,p-lchild);EnQueue(Q,p-lchild); /左孩子入隊列 EnQueue(Q,p-rchild);EnQueue(

21、Q,p-rchild); /右孩子入隊列 /while/while return 1; return 1; /執(zhí)行至此必為隊空且中間無空指針，完全二叉樹/IsFull_Bitree /IsFull_Bitree 例六：例六：復(fù)制二叉樹復(fù)制二叉樹其基本操作為其基本操作為:生成一個結(jié)點。生成一個結(jié)點。BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ) if (!(T = new BiTNode) exit(1); T- data = item; T- lchild = lptr; T- rchild = rptr

22、; return T; 生成一個二叉樹的結(jié)點生成一個二叉樹的結(jié)點:(其數(shù)據(jù)域為其數(shù)據(jù)域為item,左指針域為左指針域為lptr,右指針域為右指針域為rptr)BiTNode *CopyTree(BiTNode *T) if (!T ) return NULL; if (T-lchild ) newlptr = CopyTree(T-lchild);/復(fù)制左子樹 else newlptr = NULL; if (T-rchild ) newrptr = CopyTree(T-rchild);/復(fù)制右子樹 else newrptr = NULL; newT = GetTreeNode(T-data

23、, newlptr, newrptr); return newT; / CopyTreeABCDEFGHK D C B H K G F E A例如例如: :下列二叉樹下列二叉樹的復(fù)制過程如下的復(fù)制過程如下: :newT27二、 線索二叉樹線索二叉樹（ Threaded Binary Tree ）所以，所以， 空指針數(shù)目空指針數(shù)目2n(n-1)=n+1個。個。證明：證明：用二叉鏈表存儲包含用二叉鏈表存儲包含n n個結(jié)點的二叉樹，結(jié)點個結(jié)點的二叉樹，結(jié)點必有必有2n個鏈域。除根結(jié)點外，二叉樹中每一個鏈域。除根結(jié)點外，二叉樹中每一個結(jié)點個結(jié)點有且僅有一個雙親有且僅有一個雙親，意即每個結(jié)點地，意即每個

24、結(jié)點地址占用了雙親的一個鏈域，址占用了雙親的一個鏈域，n n個結(jié)點地址共占個結(jié)點地址共占用了用了n-1n-1個指針域個指針域。也就是說，只會有。也就是說，只會有n n1 1個個鏈域存放指針。鏈域存放指針。討論討論1 1：用二叉鏈表法（用二叉鏈表法（l_child, r_childl_child, r_child）存儲）存儲 包含包含n n個結(jié)點的二叉樹，結(jié)點的指針區(qū)域中個結(jié)點的二叉樹，結(jié)點的指針區(qū)域中 會有多少個會有多少個空空指針？指針？28結(jié)論：結(jié)論：用二叉鏈表存儲包含用二叉鏈表存儲包含n n個結(jié)點的二叉樹，結(jié)點個結(jié)點的二叉樹，結(jié)點的指針區(qū)域中會有的指針區(qū)域中會有n+1n+1個空指針。個空指

25、針。討論討論2 2：二叉樹是非線性結(jié)構(gòu)，如何定義其直接后繼？二叉樹是非線性結(jié)構(gòu)，如何定義其直接后繼？ 對二叉樹進行某種遍歷之后，將得到一個線性對二叉樹進行某種遍歷之后，將得到一個線性 有序的序列。有序的序列。 例如對某二叉樹的例如對某二叉樹的中序遍歷中序遍歷結(jié)果是結(jié)果是B D C E A B D C E A F H GF H G，意味著已將該樹轉(zhuǎn)為線性排列，顯然其中結(jié)，意味著已將該樹轉(zhuǎn)為線性排列，顯然其中結(jié)點點具有唯一前驅(qū)和唯一后繼具有唯一前驅(qū)和唯一后繼。 討論討論3 3：如何獲得這種如何獲得這種“直接前驅(qū)直接前驅(qū)”或或“直接后繼直接后繼”？有何意義？有何意義？29這就是這就是（Threade

26、d Binary Tree）二叉樹中容易找到結(jié)點的二叉樹中容易找到結(jié)點的左右孩子左右孩子信息，但該結(jié)信息，但該結(jié)點的直接前驅(qū)和直接后繼只能在某種遍歷過程中點的直接前驅(qū)和直接后繼只能在某種遍歷過程中動態(tài)動態(tài)獲得。獲得。先依先依遍歷規(guī)則遍歷規(guī)則把每個結(jié)點對應(yīng)的把每個結(jié)點對應(yīng)的前驅(qū)前驅(qū)和和后繼線索后繼線索預(yù)存起來，這叫做預(yù)存起來，這叫做“線索化線索化”。意義：意義：從從任一結(jié)點任一結(jié)點出發(fā)都能快速找到其前驅(qū)和后出發(fā)都能快速找到其前驅(qū)和后繼，且繼，且不必借助堆棧。不必借助堆棧。30 每個結(jié)點增加兩個域：每個結(jié)點增加兩個域：fwd和和bwd；如何預(yù)存這類信息？有兩種解決方法：如何預(yù)存這類信息？有兩種解決

27、方法： 與原有的左右孩子指針域與原有的左右孩子指針域“復(fù)用復(fù)用”，充分利用那，充分利用那n+1n+1個空鏈域。個空鏈域。規(guī)規(guī) 定：定：1 1）若結(jié)點有左子樹，則）若結(jié)點有左子樹，則lchildlchild指向其左指向其左孩子；否則，孩子；否則，lchildlchild指向其直接前驅(qū)指向其直接前驅(qū)( (即即線索線索) )；2 2）若結(jié)點有右子樹，則）若結(jié)點有右子樹，則rchildrchild指向其右指向其右孩子；否則，孩子；否則，rchildrchild指向其直接后繼指向其直接后繼( (即線索即線索) ) 。datalchildrchildfwdbwddatalchildrchild缺點：空間效

28、缺點：空間效率太低！率太低！如何判斷是孩如何判斷是孩子指針還是線子指針還是線索指針？索指針？如何區(qū)如何區(qū)別？別？31lchild LTagdataRTagrchild約定約定: 當(dāng)當(dāng)Tag域為域為0時時,表示孩子情況表示孩子情況;當(dāng)當(dāng)Tag域為域為1時時,表示表示線索線索情況情況.前驅(qū)前驅(qū)(后繼后繼)左左(右右)孩子孩子為區(qū)別兩種不同情況，特增加兩個標(biāo)志域：為區(qū)別兩種不同情況，特增加兩個標(biāo)志域：問：問：增加了前驅(qū)和后繼等線索有什么好處？增加了前驅(qū)和后繼等線索有什么好處？能方便找出當(dāng)前結(jié)點的前驅(qū)和后繼，不用能方便找出當(dāng)前結(jié)點的前驅(qū)和后繼，不用堆棧（遞歸）也能遍歷整棵樹。堆棧（遞歸）也能遍歷整棵樹

29、。各各1bit1bit321. 1. 有關(guān)線索二叉樹的幾個術(shù)語：有關(guān)線索二叉樹的幾個術(shù)語：線索鏈表：線索鏈表：線線 索：索：線索二叉樹：線索二叉樹：線線 索索 化：化：用用含含TagTag的結(jié)點樣式所構(gòu)成的二叉鏈表。的結(jié)點樣式所構(gòu)成的二叉鏈表。指向結(jié)點前驅(qū)和后繼的指針。指向結(jié)點前驅(qū)和后繼的指針。加上線索的二叉樹。加上線索的二叉樹。對二叉樹以對二叉樹以某種次序遍歷某種次序遍歷使其變?yōu)榫€索二使其變?yōu)榫€索二叉樹的過程。叉樹的過程。線索化過程線索化過程就是在遍歷過程中修改空指針的過程：就是在遍歷過程中修改空指針的過程： 將空的將空的lchildlchild改為結(jié)點的直接前驅(qū)；改為結(jié)點的直接前驅(qū)； 將空

30、的將空的rchildrchild改為結(jié)點的直接后繼。改為結(jié)點的直接后繼。 非空指針呢？仍然指向孩子結(jié)點（稱為非空指針呢？仍然指向孩子結(jié)點（稱為“正常情況正常情況”）33dataAGEIDJHCFBLtag0011110101Rtag0001010111AGEIDJHCFB例例1：帶了兩個標(biāo)志的某：帶了兩個標(biāo)志的某先序遍歷結(jié)果先序遍歷結(jié)果如下表所示，如下表所示，請畫出對應(yīng)的二叉樹。請畫出對應(yīng)的二叉樹。ATag=1表示線索表示線索:Ltag=1表示前驅(qū)表示前驅(qū)Rtag=1表示后繼表示后繼34ABCGEIDHFroot懸空？懸空？ NILNIL懸空？懸空？ NILNIL解：對該二叉樹解：對該二叉樹中

31、序中序遍歷的結(jié)果為遍歷的結(jié)果為: : H, D, I, B, E, H, D, I, B, E, A, F, C, G A, F, C, G 所以添加線索應(yīng)當(dāng)按如下路徑進行：所以添加線索應(yīng)當(dāng)按如下路徑進行：為避免懸空為避免懸空態(tài)，應(yīng)增設(shè)態(tài)，應(yīng)增設(shè)一個頭結(jié)點一個頭結(jié)點例例2 2：畫出以下二叉樹對應(yīng)的：畫出以下二叉樹對應(yīng)的中序中序線索二叉樹。線索二叉樹。2. 2. 線索二叉樹的生成線索二叉樹的生成線索化（線索二叉樹的重點）線索化（線索二叉樹的重點）3500A00C00B11E11F11G00D11I11H注：此圖中序遍歷結(jié)果為注：此圖中序遍歷結(jié)果為: : H, D, I, B, E, A, F,

32、C, G對應(yīng)的中序線索二叉樹存儲結(jié)構(gòu)如圖所示：對應(yīng)的中序線索二叉樹存儲結(jié)構(gòu)如圖所示：root36例例3 3：已知一棵二叉樹的中序序列為：已知一棵二叉樹的中序序列為cbedahgijf,cbedahgijf,后序序后序序列為列為cedbhjigfa,cedbhjigfa,畫出該二叉樹的先序線索二叉樹。畫出該二叉樹的先序線索二叉樹。線索二叉樹的生成算法（遞歸算法見教材線索二叉樹的生成算法（遞歸算法見教材P134-135，自，自學(xué)學(xué)）目的：目的：在遍歷二叉樹的過程中修改空指針，添加前在遍歷二叉樹的過程中修改空指針，添加前驅(qū)或后繼的線索，使之成為線索二叉樹。驅(qū)或后繼的線索，使之成為線索二叉樹。 為了記

33、下遍歷過程中訪問結(jié)點的先后次序，需要為了記下遍歷過程中訪問結(jié)點的先后次序，需要設(shè)置兩個指針：設(shè)置兩個指針： p p指針指針當(dāng)前結(jié)點之指針；當(dāng)前結(jié)點之指針； prepre指針指針當(dāng)前結(jié)點的前趨結(jié)點指針。當(dāng)前結(jié)點的前趨結(jié)點指針。37設(shè)計技巧：設(shè)計技巧：依某種順序遍歷二叉樹，對每個結(jié)點依某種順序遍歷二叉樹，對每個結(jié)點p，判，判斷其左指針是否為空，以及其斷其左指針是否為空，以及其前驅(qū)結(jié)點的前驅(qū)結(jié)點的右右指針是否為空。指針是否為空。每次只修改每次只修改前驅(qū)結(jié)點的右指針前驅(qū)結(jié)點的右指針（后繼）和（后繼）和本結(jié)點的左本結(jié)點的左指針指針（前驅(qū)）（前驅(qū)），參見，參見P135算法算法6.7。若若p-lchildN

34、ULL,則則 p-LTag=1; p-lchildpre; /p的前驅(qū)線索應(yīng)存的前驅(qū)線索應(yīng)存p結(jié)點的左邊結(jié)點的左邊若若pre-rchildNULL, 則則 pre-RTag1; pre-rchild=p; /pre的后繼線索應(yīng)存的后繼線索應(yīng)存pre結(jié)點的右邊結(jié)點的右邊38難點：難點：在線索化二叉樹中，并不是每個結(jié)點都能在線索化二叉樹中，并不是每個結(jié)點都能直接找到其后繼的，直接找到其后繼的，當(dāng)標(biāo)志為當(dāng)標(biāo)志為0 0時，則需要通過一時，則需要通過一定運算才能找到它的后繼。定運算才能找到它的后繼。以以中序線索二叉樹中序線索二叉樹為例：為例：當(dāng)當(dāng)RTag=1時，直接后繼指針就在其時，直接后繼指針就在其rchild域內(nèi)；域內(nèi)