【正文】 二叉樹、樹和森林 樹的存儲結(jié)構(gòu) 樹的存儲結(jié)構(gòu)有順序結(jié)構(gòu)和鏈表結(jié)構(gòu)。 p=r。 else { r=qlch。而 D的后繼指針指向了 A， A就是 D的后繼結(jié)點。由中根遍歷的規(guī)律可知，作為根 q的前驅(qū)結(jié)點 (或者說以根結(jié)點為后繼的結(jié)點 )，它應(yīng)是中根遍歷 q的左子樹時訪問的最后一個結(jié)點，即左子樹的最右尾結(jié)點。 數(shù)據(jù)結(jié)構(gòu)（ C語言版） 在中根線索樹上檢索某結(jié)點的前驅(qū)或后繼 1. 已知 q結(jié)點找出它的前驅(qū)結(jié)點 根據(jù)線索樹的基本概念，當(dāng) qltag=1時， qlch就指向 q的前驅(qū)。而在從深度遞歸返回時，每返回一次就讓 prrch置一次空，這顯然是錯誤的。 /*中根線索化二叉樹 */ prrch=NULL； /*善后處理 */ } 數(shù)據(jù)結(jié)構(gòu)（ C語言版） 初學(xué)者在這里往往易犯錯誤，常把預(yù)處理 pr=NULL和善后處理 prrch=NULL放在線索化子函數(shù) void inthread (struct xtreenode * p )中，一個放最前面，另一個放最后面。 /*全局變量 */ t=creat()。 所以在返回主程序后還要使 prrch=NULL， 至此整個線索化結(jié)束 。 在閱讀此算法時 ， 將inthread(plch )和 inthread(prch)之間的一組語句看成一個整體 ， 把這段語句理解為 “ 訪問 ” ， 很明顯這里應(yīng)用了典型的中根遍歷算法思路 。 在inthread函數(shù)中 pr 始終作為當(dāng)前結(jié)點 p的前驅(qū)結(jié)點的指針 。 /*pr跟上 p，以便 p向后移動 */ inthread(prch)。 prrch=p。 } /*建 p結(jié)點的左線索，指向前驅(qū)結(jié)點 pr*/ if(pr!=NULL) { if(prrch!=NULL) prrtag=0。 else{pltag=1。 數(shù)據(jù)結(jié)構(gòu)（ C語言版） printf (%6c\t,pdata)。 中根次序線索化是在已建立好的二叉鏈表之上 (每個結(jié)點有 5個域 )按中根遍歷的方法在訪問根結(jié)點時建立線索 。對圖(a)所示的二叉樹進(jìn)行線索化，可得到圖 (b)、 (c)、 (d)所示的三種線索二叉樹的邏輯表示。 (4) ?p無右孩子時，令 prtag = 1,并且讓 prch指向 p的后繼結(jié)點。 (2) ?p無左孩子時 ， 令 pltag = 1, 并且 plch指向 p的前驅(qū)結(jié)點 。 經(jīng)過線索化之后生成的二叉鏈表表示稱為線索二叉樹 。 /*左、右標(biāo)志域 */ } 數(shù)據(jù)結(jié)構(gòu)（ C語言版） 通常把指向前驅(qū)或后繼的指針稱做線索 。 struct xtreenode *lch,*rch。為了嚴(yán)格區(qū)分結(jié)點的孩子指針域究竟指向孩子結(jié)點還是指向前驅(qū)或后繼結(jié)點，需在原結(jié)點結(jié)構(gòu)中增加兩個標(biāo)志域。 我們可充分利用這些空指針來存放結(jié)點的線性前驅(qū)和后繼信息 。(*T)lchild)； //構(gòu)造左子樹 CreateBinTree(amp。39。 數(shù)據(jù)結(jié)構(gòu)（ C語言版） 思考 已知一棵二叉樹的前序跟中序遍歷序列，是否能求得這棵二叉樹？ 數(shù)據(jù)結(jié)構(gòu)（ C語言版） 二叉樹的應(yīng)用 二叉樹的初始化 ? void CreateBinTree (BinTree *T) { //構(gòu)造二叉鏈表。 /*后根遍歷右子樹 */ printf ( %c＼ n， pdata)。 后根遍歷遞歸算法如下： 數(shù)據(jù)結(jié)構(gòu)（ C語言版） /*算法描述 后序遍歷的遞歸算法 */ void postorder (BTlink* p ) { if ( p!= NULL ) { postorder ( plch)。 中序遍歷遞歸算法如下 : 數(shù)據(jù)結(jié)構(gòu)（ C語言版） /*算法描述 中序遍歷的遞歸算法 */ void inorder(BTlink *p) {if (p!=NULL) {inorder(plch)； /*中序遍歷左子樹 */ printf(%c\n， pdata)； /*訪問根結(jié)點 */ inorder(prch)； /*中序遍歷右子樹 */ } }/*inorder*/ 例如，圖 (a)所示二叉樹的中根遍歷序列為 BAC, 圖(b)所示二叉樹的中根遍歷序列為 BCAEDF。 假定我們以 D、 L、 R分別表示訪問根結(jié)點 、 遍歷左子樹和遍歷右子樹 ， 則可以有六種遍歷形式： DLR、 LDR、LRD、 DRL、 RDL、 RLD， 若依習(xí)慣規(guī)定先左后右 ， 則上述六種形式可歸并為三種形式 ， 即： DLR 先序遍歷 LDR 中序遍歷 LRD 后序遍歷 數(shù)據(jù)結(jié)構(gòu)（ C語言版） 先序遍歷 先序遍歷可以遞歸地描述如下： 如果二叉樹為空 ， 則空操作 ， 否則： ① 訪問根結(jié)點； ② 按先序次序遍歷左子樹； ③ 按先序次序遍歷右子樹 。 采用不同的遍歷規(guī)則會產(chǎn)生不同的遍歷結(jié)果 ， 因此必須人為設(shè)定遍歷規(guī)則 。 對于線性結(jié)構(gòu)來說 ， 遍歷很容易實現(xiàn) ， 順序掃描結(jié)構(gòu)中的每個數(shù)據(jù)元素即可 。 例如 ， 查詢結(jié)點數(shù)據(jù)域的內(nèi)容 ， 或輸出它的值 ， 或找出結(jié)點位置 ， 或執(zhí)行對結(jié)點的其他操作 。 遍歷二叉樹是指以一定的次序訪問二叉樹中的每個結(jié)點 ， 并且每個結(jié)點僅被訪問一次 。 數(shù)據(jù)結(jié)構(gòu)（ C語言版） lch data rch lch data parent rch (a) (b) 圖 二叉樹鏈表存儲結(jié)構(gòu)中的結(jié)點結(jié)構(gòu) (a) 二叉鏈表中的結(jié)點結(jié)構(gòu)； (b) 三叉鏈表中的結(jié)點結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)（ C語言版） DBAJ KCFAB CD FJ KAB CD FJ K( a ) ( b) ( c )圖 二叉樹的鏈表存儲結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)（ C語言版） 遍歷二叉樹 在二叉樹的應(yīng)用中 ， 常常需要在樹中搜索具有某種特征的結(jié)點 ， 或?qū)渲腥康慕Y(jié)點逐一進(jìn)行處理 。 typedef BinTNode *BinTree； //BinTree為指向 BinTNode類型結(jié)點的指針類型 數(shù)據(jù)結(jié)構(gòu)（ C語言版） 三叉鏈表的結(jié)點比二叉鏈表多了一個指向雙親的指針域 。 二叉鏈表的每個結(jié)點都有一個數(shù)據(jù)域和兩個指針域 ，一個指針指向左孩子 ， 另一個指針指向右孩子 。 數(shù)據(jù)結(jié)構(gòu)（ C語言版） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F G H J K L M N O 圖 二叉樹的順序存儲結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)（ C語言版） (2) 鏈表存儲結(jié)構(gòu)通常用于二叉樹存儲 。在哈夫曼樹構(gòu)造算法中也用到順序存儲結(jié)構(gòu)。可以發(fā)現(xiàn)圖 (a)中結(jié)點的編號恰好與數(shù)組元素的下標(biāo)相對應(yīng)，見圖 。這種存儲結(jié)構(gòu)適用于完全二叉樹和滿二叉樹。 數(shù)據(jù)結(jié)構(gòu)（ C語言版） 二叉樹的存儲結(jié)構(gòu) 二叉樹常用的存儲結(jié)構(gòu)有兩種 ， 即順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu) 。 證明 ：設(shè) n代表二叉樹結(jié)點總數(shù) ， 那么 n=n0+n1+n2 (1) 由于有 n個結(jié)點的二叉樹總分支數(shù)為 n－ 1條 ， 于是得 n－ 1=0 n0+1 n1+2 n2 (2) 將式 (1)代入式 (2)得 n0=n2+1 數(shù)據(jù)結(jié)構(gòu)（ C語言版） 性質(zhì) 4 具有 n個結(jié)點的完全二叉樹深度為 [log2n]+1(其中 ?x?表示不大于 x的最大整數(shù) )。 由性質(zhì) 1可知，各層結(jié)點最多數(shù)目之和為 20+21+22+…+2 k1；由二進(jìn)制換算關(guān)系可知： 20+21+22+…+2 k1=2k－ 1，因此二叉樹中結(jié)點的最大數(shù)目為 2k－ 1。 根據(jù)二叉樹和結(jié)點層次的定義可知，根結(jié)點在第一層上，這層結(jié)點數(shù)至多為 1個，即 20個；顯然第二層上至多有 2個結(jié)點，即 21個 …… 假設(shè)第 i－ 1層的結(jié)點至多有 2i2個，且每個結(jié)點最多有兩個孩子，那么第 i層上結(jié)