【文章內(nèi)容簡介】 { if ( p rchild == NULL ) p = p lchild。 else p = p rchild。 } cout pdata。 } 合肥工業(yè)大學 計算機與信息學院 32 二叉樹的遍歷及其應(yīng)用 （ 2）設(shè)計算法將二叉鏈表存儲的二叉樹轉(zhuǎn)換為順序存儲形式。 存儲在 A[]中，并將對應(yīng)空結(jié)點的元素的值設(shè)置為“ ^”。 例如，下面是一棵二叉樹及其對應(yīng)的存儲結(jié)構(gòu) A[]的示例。 A B C D E F G H ^ I ^ J M 0 1 2 3 4 5 6 7 8 9 10 11 12 13 A B C G F E H D I K J 1 2 3 4 5 6 7 8 9 10 12 13 合肥工業(yè)大學 計算機與信息學院 33 二叉樹的遍歷及其應(yīng)用 void trans( bnode *t, int i ) { if ( t != NULL ) { A[i] = t data。 trans( t lchild,2 * i )。 trans( t rchild,2 * i + 1 )。 } } 調(diào)用該算法前，將數(shù)組所有元素先設(shè)置為 “ ^”。 (2) 設(shè)計算法輸出二叉樹先序遍歷的前 k個結(jié)點 判斷題 ： 先序和中序相同的二叉樹，所有結(jié)點左孩子為空。（ ） 先序和中序相反的二叉樹，所有結(jié)點右孩子為空。（ ） 先序序列中最后一個結(jié)點是葉子結(jié)點。 （ ） 后序序列中第一個結(jié)點是葉子結(jié)點。 （ ） 中序序列中第一個結(jié)點是葉子結(jié)點。 （ ） 合肥工業(yè)大學 計算機與信息學院 34 線索二叉樹 1?；靖拍? 問題 ： 對給定二叉樹（二叉鏈表）， 求某結(jié)點在給定次序（先、中、后序） 中的前驅(qū)或后繼。 例如 ，右圖中的結(jié)點 E，在先序、 中序、后序前驅(qū)、后繼結(jié)點。 求解方法 （ 1）從頭開始遍歷 費時； （ 2）給每個結(jié)點增設(shè)前驅(qū) /后繼指針 —— 費空間； （ 3）利用二叉鏈表中 n+1個為空的指針域 可行的一種考慮 D E I A G F C B H 合肥工業(yè)大學 計算機與信息學院 35 線索二叉樹 將二叉鏈表中空的指針修改為指向前驅(qū)或后繼，即 將其中的值為空的 左孩子 指針改為指向 前驅(qū)， 將其中的值為空的 右孩子 指針改為指向 后繼。 線索。 線索二叉樹。 例如， 右圖就是一個 先序 線索二叉樹。 其中線索用 虛線 表示。 線索化 —— 將二叉樹修改為線索二叉樹的過程。 A B C D E F H G I J 合肥工業(yè)大學 計算機與信息學院 36 線索二叉樹 為了區(qū)分孩子指針和線索（雖然由圖中可以“直觀地”區(qū)分出來，但在算法中卻不行）。 在每個結(jié)點中需再引入兩個區(qū)分標志 ltag和 rtag， 并且約定如下： ltag=0： lchild指示該結(jié)點的左孩子。 ltag=1： lchild指示該結(jié)點的前驅(qū)。 rtag=0： rchild指示該結(jié)點的右孩子。 rtag=1： rchild指示該結(jié)點的后繼。 0A0 0B0 1C1 0D0 1E1 1F1 0G1 1H0 0I1 1J1 合肥工業(yè)大學 計算機與信息學院 37 線索二叉樹 為簡便起見，通常將線索二叉樹畫成如下的形式。 A B C D G F E H I 先序線索二叉樹 E I H D C G B A F 中序線索二叉樹 合肥工業(yè)大學 計算機與信息學院 38 線索二叉樹 2。 線索二叉樹的結(jié)構(gòu)描述 如前所述，為區(qū)分結(jié)點中的孩子指針和線索，結(jié)點中增設(shè)了兩個標志 ltag和 rtag，并約定： 0 結(jié)點中的 lchild字段指向 左孩子； ltag= 1 結(jié)點中的 lchild字段指向 前驅(qū) ； 0 結(jié)點中的 rchild字段指向 右孩子 ； rtag= 1 結(jié)點中的 rchild字段指向 后繼 ； 由此可知，結(jié)點的類型描述 typedef struct tbnode{ elementtype data。 tbnode *lchild, *rchild。 int ltag, rtag。 }tbnode。 合肥工業(yè)大學 計算機與信息學院 39 線索二叉樹 (1) 先序線索二叉樹中 先序后繼 的求解 先序后繼 對先序線索二叉樹中任意結(jié)點 P，求其先序后繼 .。 討論： (a) 若 *p有左孩子 —— 按照遍歷的過程描述（ PPlPr）可知， 其后繼應(yīng)為：左子樹 Pl中的第一個結(jié)點， 即 *p的左孩子結(jié)點， 因此， plchild為其后繼； (b) 否則， *p有右孩子 —— 類似地，可知 prchild為其后繼； (c) 否則， prchild為其后繼線索； 由此得 算法 如下： tbnode *presuc(bnode *p) { if ( p ltag == 0 ) return ( p lchild )。 else return ( p rchild )。 } P PL PR (a) P PR (b) (c) P 合肥工業(yè)大學 計算機與信息學院 40 線索二叉樹 (2) 先序線索二叉樹中 先序前驅(qū) 的求解 先序前驅(qū) 對二叉樹先序中任意的結(jié)點 P，求其前驅(qū) .。 討論： (a) 若 *P是根結(jié)點 —— 無前驅(qū) (b) 若 *P是其父結(jié)點的左孩子 —— 前驅(qū)是其父結(jié)點； (c) 否則，若 *P是其父結(jié)點的右孩子 —— 無左兄弟結(jié)點 —— 前驅(qū)是父結(jié)點； 有左兄弟結(jié)點 —— 前驅(qū)是左兄弟子樹中 最右下的葉子結(jié)點。 練習 ： (1) 設(shè)計一個非遞歸算法，以先序遍歷先序線索二叉樹（且不用棧） 合肥工業(yè)大學 計算機與信息學院 41 線索二叉樹 (3) 中序線索二叉樹中中序后繼的求解 中序后繼 分析：按照中序遍歷的過程描述（ PLPPR）可知， (a) 若 *P有右孩子 —— 其后繼應(yīng)在其右子樹中， 即右子樹的中序序列的 第一個結(jié)點為 *p的后繼。 如何求解此結(jié)點？ 從右孩子結(jié)點望左下“ 滑行 ”到 。？ (b) 若 *P無右孩子 —— 則 p rchild 就是其后繼線索。 P PR (a) (b) P P P1 P2 Pk 合肥工業(yè)大學 計算機與信息學院 42 N Y 線索二叉樹 tbnode * insuc ( tbnode *p ) { if ( p rtag == 1 ) return ( p rchild )。 else{ q = p rchild。 while ( q ltag == 0 ) q = q lchild。 return(q)。 } } P有右孩子 Y q=prchild q有左孩子 q=qlchild N Return prchild Return q 由討論得流程圖如下： 合肥工業(yè)大學 計算機與信息學院 43 線索二叉樹 (4) 中序前驅(qū)的求解 —— 與中序后繼對稱 分析 ： (a) 若有左孩子 —— 前驅(qū)是左子樹中序序列的最后一個結(jié)點； (b) 若無左孩子 —— 前驅(qū)線索 plchild。 tbnode * inpre ( tbnode *p ) { if (