【正文】 2. 二叉樹還原為森林 將一棵由森林轉(zhuǎn)換得到的二叉樹還原為森林的步驟是： (1) 抹線：將二叉樹的根結(jié)點(diǎn)與其右孩子的連線以及當(dāng)且僅當(dāng)連續(xù)地沿著右鏈不斷地搜索到的所有右孩子的連線全部抹去 ，這樣就得到包含有若干棵二叉樹的森林 。 (3) 整理：把虛線改為實(shí)線，把結(jié)點(diǎn)按層次排列。 并非任意一棵二叉樹都能還原成一般樹 。 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） 由于二叉樹中各結(jié)點(diǎn)的右孩子都是原一般樹中該結(jié)點(diǎn)的兄弟，而一般樹的根結(jié)點(diǎn)又沒(méi)有兄弟結(jié)點(diǎn)，因此所生成的二叉樹的根結(jié)點(diǎn)沒(méi)有右子樹。 (3) 旋轉(zhuǎn)：把虛線改為實(shí)線從水平方向向下旋轉(zhuǎn) 45176。 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） 1. 一般樹轉(zhuǎn)化為二叉樹 將一般樹轉(zhuǎn)化為二叉樹的思路 ， 主要根據(jù)樹的孩子 － 兄弟存儲(chǔ)方式而來(lái) ， 步驟是： (1) 加線：在各兄弟結(jié)點(diǎn)之間用虛線相連 。孩子 － 兄弟鏈表如圖 (b)所示。常用的有結(jié)點(diǎn)定長(zhǎng)的雙親鏈表發(fā)、多叉鏈表和孩子 － 兄弟二叉鏈表。 } 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） 二叉樹、樹和森林 樹的存儲(chǔ)結(jié)構(gòu) 樹的存儲(chǔ)結(jié)構(gòu)有順序結(jié)構(gòu)和鏈表結(jié)構(gòu)。 else { r=qlch。由中根遍歷的規(guī)律可知，作為根 q的前驅(qū)結(jié)點(diǎn) (或者說(shuō)以根結(jié)點(diǎn)為后繼的結(jié)點(diǎn) )，它應(yīng)是中根遍歷 q的左子樹時(shí)訪問(wèn)的最后一個(gè)結(jié)點(diǎn)，即左子樹的最右尾結(jié)點(diǎn)。而在從深度遞歸返回時(shí)，每返回一次就讓 prrch置一次空，這顯然是錯(cuò)誤的。 /*全局變量 */ t=creat()。 在閱讀此算法時(shí) ， 將inthread(plch )和 inthread(prch)之間的一組語(yǔ)句看成一個(gè)整體 ， 把這段語(yǔ)句理解為 “ 訪問(wèn) ” ， 很明顯這里應(yīng)用了典型的中根遍歷算法思路 。 /*pr跟上 p，以便 p向后移動(dòng) */ inthread(prch)。 } /*建 p結(jié)點(diǎn)的左線索，指向前驅(qū)結(jié)點(diǎn) pr*/ if(pr!=NULL) { if(prrch!=NULL) prrtag=0。 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） printf (%6c\t,pdata)。對(duì)圖(a)所示的二叉樹進(jìn)行線索化，可得到圖 (b)、 (c)、 (d)所示的三種線索二叉樹的邏輯表示。 (2) ?p無(wú)左孩子時(shí) ， 令 pltag = 1, 并且 plch指向 p的前驅(qū)結(jié)點(diǎn) 。 /*左、右標(biāo)志域 */ } 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） 通常把指向前驅(qū)或后繼的指針?lè)Q做線索 。為了嚴(yán)格區(qū)分結(jié)點(diǎn)的孩子指針域究竟指向孩子結(jié)點(diǎn)還是指向前驅(qū)或后繼結(jié)點(diǎn)，需在原結(jié)點(diǎn)結(jié)構(gòu)中增加兩個(gè)標(biāo)志域。(*T)lchild)； //構(gòu)造左子樹 CreateBinTree(amp。 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） 思考 已知一棵二叉樹的前序跟中序遍歷序列，是否能求得這棵二叉樹？ 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） 二叉樹的應(yīng)用 二叉樹的初始化 ? void CreateBinTree (BinTree *T) { //構(gòu)造二叉鏈表。 后根遍歷遞歸算法如下： 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） /*算法描述 后序遍歷的遞歸算法 */ void postorder (BTlink* p ) { if ( p!= NULL ) { postorder ( plch)。 假定我們以 D、 L、 R分別表示訪問(wèn)根結(jié)點(diǎn) 、 遍歷左子樹和遍歷右子樹 ， 則可以有六種遍歷形式： DLR、 LDR、LRD、 DRL、 RDL、 RLD， 若依習(xí)慣規(guī)定先左后右 ， 則上述六種形式可歸并為三種形式 ， 即： DLR 先序遍歷 LDR 中序遍歷 LRD 后序遍歷 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） 先序遍歷 先序遍歷可以遞歸地描述如下： 如果二叉樹為空 ， 則空操作 ， 否則： ① 訪問(wèn)根結(jié)點(diǎn)； ② 按先序次序遍歷左子樹； ③ 按先序次序遍歷右子樹 。 對(duì)于線性結(jié)構(gòu)來(lái)說(shuō) ， 遍歷很容易實(shí)現(xiàn) ， 順序掃描結(jié)構(gòu)中的每個(gè)數(shù)據(jù)元素即可 。 遍歷二叉樹是指以一定的次序訪問(wèn)二叉樹中的每個(gè)結(jié)點(diǎn) ， 并且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次 。 typedef BinTNode *BinTree； //BinTree為指向 BinTNode類型結(jié)點(diǎn)的指針類型 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） 三叉鏈表的結(jié)點(diǎn)比二叉鏈表多了一個(gè)指向雙親的指針域 。 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） 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 圖 二叉樹的順序存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） (2) 鏈表存儲(chǔ)結(jié)構(gòu)通常用于二叉樹存儲(chǔ) ?？梢园l(fā)現(xiàn)圖 (a)中結(jié)點(diǎn)的編號(hào)恰好與數(shù)組元素的下標(biāo)相對(duì)應(yīng)，見圖 。 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） 二叉樹的存儲(chǔ)結(jié)構(gòu) 二叉樹常用的存儲(chǔ)結(jié)構(gòu)有兩種 ， 即順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 。 由性質(zhì) 1可知，各層結(jié)點(diǎn)最多數(shù)目之和為 20+21+22+…+2 k1；由二進(jìn)制換算關(guān)系可知： 20+21+22+…+2 k1=2k－ 1，因此二叉樹中結(jié)點(diǎn)的最大數(shù)目為 2k－ 1。而圖 (c)則不是完全二叉樹。 (e) 有根結(jié)點(diǎn)和左、右子樹 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） 有兩種特殊形態(tài)的二叉樹 ， 它們是滿二叉樹和完全二叉樹 。 ( a ) ( b ) ( c ) ( d ) ( e )圖 二叉樹的五種基本形態(tài) (a) 空二叉樹 。 它或?yàn)榭諛?(n＝ 0)， 或?yàn)榉强諛?；?duì)于非空樹有： (1) 有一個(gè)特定的稱之為根的結(jié)點(diǎn)； (2) 根結(jié)點(diǎn)以外的其余結(jié)點(diǎn)分別由兩棵互不相交的稱之為左子樹和右子樹的二叉樹組成 。 在有序樹中最左邊的子樹的根稱為第一個(gè)孩子 ， 最右邊的稱為最后一個(gè)孩子 。 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） 4. 結(jié)點(diǎn)的層次和樹的高度 結(jié)點(diǎn)的層次 (Level)從根結(jié)點(diǎn)開始定義，根為第一層，根結(jié)點(diǎn)的孩子為第二層，依次類推，其余結(jié)點(diǎn)的層次值為雙親結(jié)點(diǎn)層次值加 1。同一個(gè)雙親的孩子之間互稱兄弟 (Sibling)。 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） 2. 分支結(jié)點(diǎn)和葉子結(jié)點(diǎn) 稱度不為 0的結(jié)點(diǎn)為分支結(jié)點(diǎn) ， 也叫非終端結(jié)點(diǎn) 。結(jié)點(diǎn)擁有的子樹數(shù)稱為結(jié)點(diǎn)的度 (Degree)。 樹的樹形圖表示中：結(jié)點(diǎn)用圓圈表示，結(jié)點(diǎn)的名字寫在圓圈旁邊（有時(shí)亦可寫在圓圈內(nèi)）。 T T T3都是樹根 A的子樹，這三棵子樹的根結(jié)點(diǎn)分別是 B、 C、 D。它道出了樹的固有特性。數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） 第 6章 樹 樹的應(yīng)用實(shí)例 樹的基本概念和術(shù)語(yǔ) 二叉樹 遍歷二叉樹 線索二叉樹 二叉樹、樹和森林 樹的應(yīng)用 實(shí)習(xí) : 二叉樹的建立和遍歷 習(xí)題 6 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） 樹的應(yīng)用實(shí)例 例 如圖 。 這是一個(gè)遞歸的定義，即在定義中又用到了樹這個(gè)術(shù)語(yǔ)。其中 A是根結(jié)點(diǎn)，其余結(jié)點(diǎn)分為三個(gè)互不相交的子集： T1={B,H,I}， T2={C}，T3={D,E,F,G}。 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） ADCBH I ETT1T2T3T31T32FG圖 樹 T 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） 樹的表示 （ 1）樹形圖表示 樹形圖表示是樹結(jié)構(gòu)的主要表示方法。上圖 (a)樹的廣義表表示法如圖 (d) （ A（ B（ E， F（ I， J））， C， D（ G， H））） 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） 樹的常用術(shù)語(yǔ) 1. 結(jié)點(diǎn)的度和樹的度 樹的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支。在樹 T中， A結(jié)點(diǎn)的度最大，值為 3，也就是說(shuō)，樹 T的度為 3。 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） 3. 孩子 、 雙親 、 兄弟 、 子孫 、 祖先 結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子 (Child)，相應(yīng)地，該結(jié)點(diǎn)稱為孩子的雙親 (Parent)。對(duì)于樹中某結(jié)點(diǎn)，從根結(jié)點(diǎn)開始到該結(jié)點(diǎn)的雙親是該結(jié)點(diǎn)的祖先。 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） 5. 無(wú)序樹 、 有序樹 、 森林 若樹中結(jié)點(diǎn)的各子樹看成從左至右是有次序的 (即不能互換 )，則稱該樹為有序樹 ， 否則稱為無(wú)序樹 。 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） 二 叉 樹 二叉樹的定義 二叉樹 (Bin