《《算法與數(shù)據(jù)結(jié)構(gòu)》教學(xué)課件第5章 二叉樹(shù)與樹(shù)C語(yǔ)言描述（第2版）張乃孝編著》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》教學(xué)課件第5章 二叉樹(shù)與樹(shù)C語(yǔ)言描述（第2版）張乃孝編著（116頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、5.1二叉樹(shù)及其抽象數(shù)據(jù)類(lèi)型 5.2二叉樹(shù)的周游5.3二叉樹(shù)的實(shí)現(xiàn)5.4二叉樹(shù)的應(yīng)用5.5樹(shù)及其抽象數(shù)據(jù)類(lèi)型 5.6 樹(shù)的實(shí)現(xiàn)5.7 樹(shù)林線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)。 樹(shù)形結(jié)構(gòu)是以分支關(guān)系定義的層次結(jié)構(gòu)，在現(xiàn)實(shí)世界中廣泛存在，在計(jì)算機(jī)領(lǐng)域中也有廣泛應(yīng)用。 本章重點(diǎn)討論二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及其各種操作，并研究樹(shù)和森林與二叉樹(shù)之間的轉(zhuǎn)換關(guān)系。 5.1.1 5.1.1 基本概念基本概念 5.1.2 5.1.2 主要性質(zhì)主要性質(zhì) 5.1.3 5.1.3 抽象數(shù)據(jù)類(lèi)型抽象數(shù)據(jù)類(lèi)型二叉樹(shù)： 它是結(jié)點(diǎn)的有限集合，這個(gè)集合或者為空集或者由一個(gè)根及兩棵不相交的分別稱(chēng)作這個(gè)根的“左子樹(shù)”和“右子樹(shù)”的二叉樹(shù)組成。 它的每一

2、個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)，并且子樹(shù)有左右之分，不能隨意顛倒。5.1.1 5.1.1 基本概念基本概念二叉樹(shù)的基本形態(tài)：左子樹(shù)右子樹(shù)右子樹(shù)左子樹(shù)（1）空二叉樹(shù)（2）只有一個(gè)根結(jié)點(diǎn)（3）有根結(jié)點(diǎn) 和左子樹(shù)（4）有根結(jié)點(diǎn) 和右子樹(shù)（5）有根結(jié)點(diǎn) 和左，右子樹(shù) 父結(jié)點(diǎn)父結(jié)點(diǎn)，左（右）子結(jié)點(diǎn)，子結(jié)點(diǎn)，邊邊 若結(jié)點(diǎn)x是二叉樹(shù)中某一棵子樹(shù)的根結(jié)點(diǎn)，結(jié)點(diǎn)y是x的左（右）子樹(shù)的根，則稱(chēng)x是y的父結(jié)點(diǎn)父結(jié)點(diǎn)；y是x的左（右）子結(jié)點(diǎn)子結(jié)點(diǎn)；有序?qū)ΨQ(chēng)作從x到y(tǒng)的邊邊。例如樹(shù)t中，C是E的父結(jié)點(diǎn)，E是C的子結(jié)點(diǎn)，是從C到E的邊 兄弟結(jié)點(diǎn)兄弟結(jié)點(diǎn)具有同一父結(jié)點(diǎn)彼此稱(chēng)作兄弟兄弟。樹(shù)t中B，C互為兄弟，D，E互為兄弟。 圖5.2

3、二叉樹(shù)tA AB BC CD DE EF F 圖5.2二叉樹(shù)tA AB BC CD DE EF F 祖先祖先，子孫子孫若結(jié)點(diǎn)y在以結(jié)點(diǎn)x為根的一個(gè)子樹(shù)中，且yx，則稱(chēng)x是y的祖先祖先，y是x的子孫子孫。例如樹(shù)t中，A是其它各結(jié)點(diǎn)的祖先；C是D,E,F的祖先。 路徑路徑，路徑長(zhǎng)度路徑長(zhǎng)度如果x是y的一個(gè)祖先，又有xx0，x1，xny，滿(mǎn)足xi（i0，1，n-1）為xi+1的父結(jié)點(diǎn)，則稱(chēng)x0，x1，xn為從x到y(tǒng)的一條路徑路徑。n稱(chēng)為這條路路徑的長(zhǎng)度徑的長(zhǎng)度。例如樹(shù)t中A，C，D，F(xiàn)是從A到F的一條路徑，其長(zhǎng)度為3。 圖5.2二叉樹(shù)tA AB BC CD DE EF F 圖5.2二叉樹(shù)tA AB

4、BC CD DE EF F 結(jié)點(diǎn)的層數(shù)結(jié)點(diǎn)的層數(shù)規(guī)定根的層數(shù)根的層數(shù)為0，其余結(jié)點(diǎn)的層數(shù)結(jié)點(diǎn)的層數(shù)等于其父母結(jié)點(diǎn)的層數(shù)加1。如t中，0層的結(jié)點(diǎn)是A，1層的結(jié)點(diǎn)有B，C，3層的結(jié)點(diǎn)是F。 二叉樹(shù)的高度二叉樹(shù)的高度樹(shù)中結(jié)點(diǎn)的最大層數(shù)稱(chēng)為二叉樹(shù)的高度二叉樹(shù)的高度。 例如樹(shù)t中，樹(shù)的深度為3。 圖5.2二叉樹(shù)tA AB BC CD DE EF F 圖5.2二叉樹(shù)tA AB BC CD DE EF F 結(jié)點(diǎn)的度數(shù)結(jié)點(diǎn)的度數(shù)結(jié)點(diǎn)的非空子樹(shù)個(gè)數(shù)叫作結(jié)點(diǎn)的度數(shù)度數(shù)。例如t中A,B,C,D,E,F的度數(shù)分別為2,0,2,1,0,0 樹(shù)葉樹(shù)葉、分支結(jié)點(diǎn)分支結(jié)點(diǎn)左（右）子樹(shù)均為空的結(jié)點(diǎn)稱(chēng)作樹(shù)葉樹(shù)葉；否則稱(chēng)作分分支結(jié)

5、點(diǎn)支結(jié)點(diǎn)。例如樹(shù)t中B，E，F(xiàn)都是樹(shù)葉，其余結(jié)點(diǎn)都是分支結(jié)點(diǎn)。 圖5.2二叉樹(shù)tA AB BC CD DE EF F 圖5.2二叉樹(shù)tA AB BC CD DE EF F 滿(mǎn)二叉樹(shù)滿(mǎn)二叉樹(shù)：如果一棵二叉樹(shù)的任何結(jié)點(diǎn)或者是樹(shù)葉，或者有兩棵非空子樹(shù)，則此二叉樹(shù)稱(chēng)作滿(mǎn)二叉樹(shù)。 完全二叉樹(shù)完全二叉樹(shù)：如果一棵二叉樹(shù)只有最下面的兩層結(jié)點(diǎn)度數(shù)可以小于2，并且最下面一層的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則此二叉樹(shù)稱(chēng)為完全二叉樹(shù)。完全二叉樹(shù)不一定是滿(mǎn)二叉樹(shù)。滿(mǎn)二叉樹(shù)完全二叉樹(shù)擴(kuò)充二叉樹(shù)擴(kuò)充二叉樹(shù) ： 把原二叉樹(shù)的結(jié)點(diǎn)都變?yōu)槎葦?shù)為2的分支結(jié)點(diǎn)，也就是說(shuō)，如果原結(jié)點(diǎn)的度數(shù)為2，則不變，度數(shù)為1，則增加一個(gè)分支

6、，度數(shù)為0（樹(shù)葉）增加兩個(gè)分支。 新增加的結(jié)點(diǎn)用小方框表示，稱(chēng)為外部結(jié)點(diǎn),原來(lái)的結(jié)點(diǎn)稱(chēng)為內(nèi)部結(jié)點(diǎn)。外部路徑長(zhǎng)度E：在擴(kuò)充的二叉樹(shù)里從根到每個(gè)外部結(jié)點(diǎn)的路徑長(zhǎng)度之和。內(nèi)部路徑長(zhǎng)度I：在擴(kuò)充的二叉樹(shù)里從根到每個(gè)內(nèi)部結(jié)點(diǎn)的路徑長(zhǎng)度之和。 性質(zhì)性質(zhì)1. 在非空二叉樹(shù)的第i層上至多有2i個(gè)結(jié)點(diǎn)（i0）。歸納： i=0, 結(jié)點(diǎn)數(shù)=1=20 . 假設(shè)對(duì)于j(0j i), 結(jié)點(diǎn)數(shù)至多有2j . 對(duì)于i=j+1, 結(jié)點(diǎn)數(shù)至多為 2* 2j=2j+1 .性質(zhì)性質(zhì)2. 深度為k的二叉樹(shù)至多有2k+1-1個(gè)結(jié)點(diǎn)（k 0）。 K k M= mi = 2i = 2k+1-1 i=0 i=0 20 + 21 + 22 +

7、2k5.1.2 5.1.2 主要性質(zhì)主要性質(zhì)性質(zhì)性質(zhì)3. 對(duì)任何一棵非空二叉樹(shù)T，如果葉結(jié)點(diǎn)數(shù) 為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。 n0+n1+n2 = 所有 結(jié)點(diǎn)的度數(shù)和+1 = n1+ 2*n2 +1 性質(zhì)性質(zhì)4. 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度k為log2n . n=20+21+22+2k-1+mk =2k-1+mk 2k-1n 2k+1-1 2k n 2k+1 k log2n k+1 k= log2n 性質(zhì)性質(zhì)5. 對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，如果按從上到下和從左到右的順序?qū)Χ鏄?shù)中的所有結(jié)點(diǎn)從0開(kāi)始到n-1進(jìn)行編號(hào)，則對(duì)任意的下標(biāo)為i的結(jié)點(diǎn)，有： 1）如果i=0，則它

8、是根結(jié)點(diǎn)，它沒(méi)有父結(jié)點(diǎn)；如果i0, 則它的父結(jié)點(diǎn)的下標(biāo)為 (i-1)/2 ; 2）2i+1 n-1，則下標(biāo)為i的結(jié)點(diǎn)的左子結(jié)點(diǎn)的下標(biāo)為2i1；否則下標(biāo)為i的結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)。 3）2i+2 n-1，則下標(biāo)為i的結(jié)點(diǎn)的右子結(jié)點(diǎn)的下標(biāo)為2i2；否則下標(biāo)為i的結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)。性質(zhì)6 在滿(mǎn)二叉樹(shù)中，葉子結(jié)點(diǎn)的個(gè)數(shù)比分支結(jié)點(diǎn)的個(gè)數(shù)多1。 由于滿(mǎn)二叉樹(shù)中，分支結(jié)點(diǎn)度數(shù)全部為2；其他結(jié)點(diǎn)都是葉子結(jié)點(diǎn)。根據(jù)性質(zhì)3， n0=n2+1，可以得到此性質(zhì)。性質(zhì)7 在擴(kuò)充二叉樹(shù)中，外部結(jié)點(diǎn)的個(gè)數(shù)比內(nèi)部結(jié)點(diǎn)的個(gè)數(shù)多1。 由于擴(kuò)充二叉樹(shù)都是滿(mǎn)二叉樹(shù)，根據(jù)性質(zhì)6可以得到此性質(zhì)。性質(zhì)8 對(duì)任意擴(kuò)充二叉樹(shù)，外部路徑長(zhǎng)度E和內(nèi)部路徑

9、長(zhǎng)度I之間滿(mǎn)足以下關(guān)系：E = I + 2n其中，n是內(nèi)部結(jié)點(diǎn)的個(gè)數(shù)。證明：當(dāng)n=1時(shí)，I=0, E=2, 此等式成立。 設(shè)有n個(gè)內(nèi)部結(jié)點(diǎn)的擴(kuò)充二叉樹(shù)，下式成立。 En=In+2n (1) 對(duì)于 n+1 個(gè)內(nèi)部結(jié)點(diǎn)的擴(kuò)充二叉樹(shù)，去掉一個(gè) 作為原來(lái)二叉樹(shù)路徑長(zhǎng)度為K的內(nèi)部結(jié)點(diǎn)，內(nèi)部路徑長(zhǎng)度變?yōu)椋?In=In+1-K (2) 外部路徑長(zhǎng)度變?yōu)椋篍n=En+1-2(K+1)+K= En+1 -K-2 即： En+1= En+K+2 En+1= (In+2n) +K+2= (In+1-K) +2n+K+2= In+1+2(n+1) 代入（1） 代入（2）abceef5.1.3 抽象數(shù)據(jù)類(lèi)型ADT Bi

10、nTree isoperations BinTree createEmptyBinTree(void) 創(chuàng)建一棵空的二叉樹(shù) BinTree consBinTree(BinTreeNode root,BinTree left,BinTree right) 返回一棵二叉樹(shù)，其根結(jié)點(diǎn)是root，左右二叉樹(shù)分別為left和rightint isNULL(BinTree t)判斷二叉樹(shù)t是否為空。BinTreeNode root(BinTree t)返回二叉樹(shù)t的根結(jié)點(diǎn)；若為空二叉樹(shù)，則返回一個(gè)特殊值。BinTreeNode parent(BinTree t,BinTreeNode p)返回結(jié)點(diǎn)p的父結(jié)

11、點(diǎn)；當(dāng)p為根時(shí)，返回一個(gè)特殊值。 BinTree leftChild (BinTree t,BinTreeNode p) 返回p結(jié)點(diǎn)的左子樹(shù)，當(dāng)p結(jié)點(diǎn)沒(méi)有左子樹(shù)時(shí)， 返回一個(gè)特殊值。 BinTree rightChild (BinTree t,BinTreeNode p) 返回p結(jié)點(diǎn)的y右子樹(shù)，當(dāng)p結(jié)點(diǎn)沒(méi)有右子樹(shù)時(shí)， 返回一個(gè)特殊值。end ADT BinTree5.2.1 什么是周游什么是周游二叉樹(shù)的周游二叉樹(shù)的周游(Traversing Binary Tree)： 按某條搜索路徑訪(fǎng)問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn) ，使得每個(gè)結(jié)點(diǎn)被訪(fǎng)問(wèn)一次且僅被訪(fǎng)問(wèn)一次。DLR5.2.2 周游的分類(lèi)深度優(yōu)先周游三種方式

12、： 先根次序 (DLR) 中 根 序 (LDR) 后根次序 (LRD)DLR先根次序：先根次序：若二叉樹(shù)不空，則若二叉樹(shù)不空，則（1 1）訪(fǎng)問(wèn)根結(jié)點(diǎn)；）訪(fǎng)問(wèn)根結(jié)點(diǎn)；（2 2）先根次序周游左子樹(shù)；）先根次序周游左子樹(shù)；（3 3）先根次序周游右子樹(shù)。）先根次序周游右子樹(shù)。A AB BD DC CE EF FI IH HG G訪(fǎng)問(wèn)訪(fǎng)問(wèn)A A先根次序周游先根次序周游A A的左子樹(shù)的左子樹(shù)先根次序周游先根次序周游A A的右子樹(shù)的右子樹(shù)A AB BD DC CE EF FI IH HG G訪(fǎng)問(wèn)訪(fǎng)問(wèn)A A先根次序周游先根次序周游A A的左子樹(shù)的左子樹(shù)訪(fǎng)問(wèn)訪(fǎng)問(wèn)B B先根次序周游先根次序周游B B的左子樹(shù)（的左

13、子樹(shù)（訪(fǎng)問(wèn)訪(fǎng)問(wèn)D D）先根次序周游先根次序周游B B的右子樹(shù)的右子樹(shù)( (空操作空操作) )先根次序周游先根次序周游A A的右子樹(shù)的右子樹(shù)訪(fǎng)問(wèn)訪(fǎng)問(wèn)C C先根次序周游先根次序周游C C的左子樹(shù)（的左子樹(shù)（訪(fǎng)問(wèn)訪(fǎng)問(wèn)E E、G G）先根次序周游先根次序周游C C的右子樹(shù)（的右子樹(shù)（訪(fǎng)問(wèn)訪(fǎng)問(wèn)F F、H H、I I）先序序列：先序序列：A B D C E G F H IA B D C E G F H I中根中根( (對(duì)稱(chēng)對(duì)稱(chēng)) )次序：次序：若二叉樹(shù)不空，則若二叉樹(shù)不空，則（1 1）中根次序周游左子樹(shù)；）中根次序周游左子樹(shù)；（2 2）訪(fǎng)問(wèn)根結(jié)點(diǎn)；）訪(fǎng)問(wèn)根結(jié)點(diǎn)；（3 3）中根次序周游右子樹(shù)。）中根次序周游

14、右子樹(shù)。中根次序周游中根次序周游A A的左子樹(shù)的左子樹(shù)訪(fǎng)問(wèn)訪(fǎng)問(wèn)A A中根次序周游中根次序周游A A的右子樹(shù)的右子樹(shù)A AB BD DC CE EF FI IH HG GA AB BD DC CE EF FI IH HG G中根次序周游中根次序周游A A的左子樹(shù)的左子樹(shù)中根次序周游中根次序周游B B的左子樹(shù)（的左子樹(shù)（訪(fǎng)問(wèn)訪(fǎng)問(wèn)D D）訪(fǎng)問(wèn)訪(fǎng)問(wèn)B B中根次序周游中根次序周游B B的右子樹(shù)的右子樹(shù)( (空操作空操作) )訪(fǎng)問(wèn)訪(fǎng)問(wèn)A A中根次序周游中根次序周游A A的右子樹(shù)的右子樹(shù)中根次序周游中根次序周游C C的左子樹(shù)（的左子樹(shù)（訪(fǎng)問(wèn)訪(fǎng)問(wèn)E E、G G）訪(fǎng)問(wèn)訪(fǎng)問(wèn)C C中根次序周游中根次序周游C C的右

15、子樹(shù)（的右子樹(shù)（訪(fǎng)問(wèn)訪(fǎng)問(wèn)H H、F F、I I）中序序列：中序序列：D B A E G C H F ID B A E G C H F I后根次序：后根次序：若二叉樹(shù)不空，則若二叉樹(shù)不空，則（1 1）后根次序周游左子樹(shù)；）后根次序周游左子樹(shù)；（2 2）后根次序周游右子樹(shù)；）后根次序周游右子樹(shù)；（3 3）訪(fǎng)問(wèn)根結(jié)點(diǎn)。）訪(fǎng)問(wèn)根結(jié)點(diǎn)。后根次序周游后根次序周游A A的左子樹(shù)的左子樹(shù)后根次序周游后根次序周游A A的右子樹(shù)的右子樹(shù)訪(fǎng)問(wèn)訪(fǎng)問(wèn)A AA AB BD DC CE EF FI IH HG GA AB BD DC CE EF FI IH HG G后根次序周游后根次序周游A A的左子樹(shù)的左子樹(shù)后根次序周游

16、后根次序周游B B的左子樹(shù)（的左子樹(shù)（訪(fǎng)問(wèn)訪(fǎng)問(wèn)D D）后根次序周游后根次序周游B B的右子樹(shù)的右子樹(shù)( (空操作空操作) )訪(fǎng)問(wèn)訪(fǎng)問(wèn)B B后根次序周游后根次序周游A A的右子樹(shù)的右子樹(shù)后根次序周游后根次序周游C C的左子樹(shù)（的左子樹(shù)（訪(fǎng)問(wèn)訪(fǎng)問(wèn)G G、E E）后根次序周游后根次序周游C C的右子樹(shù)（的右子樹(shù)（訪(fǎng)問(wèn)訪(fǎng)問(wèn)H H、I I、F F）訪(fǎng)問(wèn)訪(fǎng)問(wèn)C C訪(fǎng)問(wèn)訪(fǎng)問(wèn)A A后序序列：后序序列：D B G E H I F C AD B G E H I F C Al廣度優(yōu)先周游l若二叉樹(shù)的高度為h，則從0到h層逐層如下處理：從左到右逐個(gè)訪(fǎng)問(wèn)存在的結(jié)點(diǎn)。A AB BD DC CE EF FI IH HG G

17、對(duì)右圖所示二叉樹(shù)進(jìn)行廣度優(yōu)先搜索，得到：A,B,C,D,E,F,G,H,I如圖所示的二叉樹(shù)如圖所示的二叉樹(shù)先序序列為：先序序列為：A B D E H K M N C F GA B D E H K M N C F G中序序列為：中序序列為：D B H E M K N A F C GD B H E M K N A F C G后序序列為：后序序列為：D H M N K E B F G C AD H M N K E B F G C A A AB BE ED DC CH HK KN NM MG GF F5.2.3 5.2.3 一個(gè)例子一個(gè)例子如圖所示的二叉樹(shù)是表達(dá)式如圖所示的二叉樹(shù)是表達(dá)式(a-b)(a

18、-b)(c+d)(c+d)的語(yǔ)法結(jié)構(gòu)圖。的語(yǔ)法結(jié)構(gòu)圖。先序序列為：先序序列為： -ab+cd-ab+cd中序序列為：中序序列為： a-ba-bc+dc+d后序序列為：后序序列為： ab-cdab-cd+ + b ba ad dc c遞歸算法先根次序中根次序后根次序非遞歸算法 *先根次序中根次序后根次序 1 2算法算法5.15.1void preOrder( BinTree t) if (t=NULL) return; visit(root(t); preOrder(leftChild(t); preOrder(rightChild(t);理解遞歸算法：理解遞歸算法：大事化小大事化小小事化了小事

19、化了根據(jù)是數(shù)學(xué)歸納法根據(jù)是數(shù)學(xué)歸納法算法證明：算法證明：設(shè)二叉樹(shù)結(jié)點(diǎn)個(gè)設(shè)二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)為數(shù)為n，則：，則：算法算法5.15.1void preOrder( BinTree t) if (t=NULL) return; visit(root(t); preOrder(leftChild(t); preOrder(rightChild(t);算法證明：算法證明：設(shè)二叉樹(shù)結(jié)點(diǎn)個(gè)設(shè)二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)為數(shù)為n，則：，則：當(dāng)當(dāng)n=0時(shí)，時(shí)，t=NULL，算法，算法做空操作，算法做空操作，算法功能成立。功能成立。算法算法5.15.1void preOrder( BinTree t) if (t=NULL) re

20、turn; visit(root(t); preOrder(leftChild(t); preOrder(rightChild(t);算法證明：算法證明：設(shè)二叉樹(shù)結(jié)點(diǎn)個(gè)設(shè)二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)為數(shù)為n，則：，則：當(dāng)當(dāng)n=0時(shí)，時(shí)，t=NULL，算法，算法做空操作，算法做空操作，算法功能成立。功能成立。假設(shè)假設(shè)ni時(shí)時(shí), 算法算法功能成立，則當(dāng)功能成立，則當(dāng)n=i時(shí)：時(shí)：訪(fǎng)問(wèn)根訪(fǎng)問(wèn)根算法算法5.15.1void preOrder( BinTree t) if (t=NULL) return; visit(root(t); preOrder(leftChild(t); preOrder(rightChil

21、d(t);算法證明：算法證明：設(shè)二叉樹(shù)結(jié)點(diǎn)個(gè)設(shè)二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)為數(shù)為n，則：，則：當(dāng)當(dāng)n=0時(shí)，時(shí)，p=NULL，算法，算法做空操作，算法做空操作，算法功能成立。功能成立。假設(shè)假設(shè)ni時(shí)時(shí), 算法算法功能成立，則當(dāng)功能成立，則當(dāng)n=i時(shí)：時(shí)：訪(fǎng)問(wèn)根訪(fǎng)問(wèn)根周游根的左子樹(shù)周游根的左子樹(shù)左子樹(shù)中結(jié)點(diǎn)個(gè)數(shù)左子樹(shù)中結(jié)點(diǎn)個(gè)數(shù)i，根據(jù)歸納假，根據(jù)歸納假設(shè)算法功能成立設(shè)算法功能成立算法算法5.15.1void preOrder( BinTree t) if (t=NULL) return; visit(root(t); preOrder(leftChild(t); preOrder(rightChild(t);

22、算法證明：算法證明：設(shè)二叉樹(shù)結(jié)點(diǎn)個(gè)設(shè)二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)為數(shù)為n，則：，則：當(dāng)當(dāng)n=0時(shí)，時(shí)，p=NULL，算法，算法做空操作，算法做空操作，算法功能成立。功能成立。假設(shè)假設(shè)ni時(shí)時(shí), 算法算法功能成立，則當(dāng)功能成立，則當(dāng)n=i時(shí)：時(shí)：訪(fǎng)問(wèn)根訪(fǎng)問(wèn)根周游根的左子樹(shù)周游根的左子樹(shù)周游根的右子樹(shù)周游根的右子樹(shù)右子樹(shù)中結(jié)點(diǎn)個(gè)數(shù)右子樹(shù)中結(jié)點(diǎn)個(gè)數(shù)i，根據(jù)歸納假，根據(jù)歸納假設(shè)算法功能成立設(shè)算法功能成立算法算法5.15.1void preOrder( BinTree t) if (t=NULL) return; visit(root(t); preOrder(leftChild(t); preOrder(right

23、Child(t);算法算法5.2 5.2 二叉樹(shù)中序周游的遞歸算法二叉樹(shù)中序周游的遞歸算法void inOrder(BinTree t) if (t=NULL) return; inOrder(leftChild(t); visit(root(t); inOrder(rightChild(t);算法算法5.3 5.3 二叉樹(shù)后根次序周游的遞歸算法二叉樹(shù)后根次序周游的遞歸算法void postOrder(BinTree t) if (t=NULL) return; postOrder(leftChild(t); postOrder(rightChild(t); visit(root(t);廣度優(yōu)

24、先周游算法5.8 廣度優(yōu)先周游二叉樹(shù)void levelOrder(BinTree t) BinTree c,cc; Queue q=createEmptyQueue(); if(t=NULL) return; c=t; enqueue(q,c); while(!isEmptyQueue(q) c=frontQueue(q);dequeue(q); visit(c); cc=leftChild(c); if(cc!=NULL)enqueue(q,cc); cc=rightChild(c); if(cc!=NULL)enqueue(q,cc); 二叉樹(shù)的實(shí)現(xiàn) 5.3.1 5.3.1 順序表示順序

25、表示 5.3.2 5.3.2 鏈接表示鏈接表示 5.3.3 5.3.3 線(xiàn)索二叉樹(shù)線(xiàn)索二叉樹(shù)* * 用一組地址連續(xù)的存儲(chǔ)單元按層次次序依次存儲(chǔ)完全二叉樹(shù)的結(jié)點(diǎn)。ABCGFEDHIJ A B C D E F G H I J 下標(biāo) 0 1 2 3 4 5 6 7 8 9 對(duì)于一般二叉樹(shù)，則應(yīng)將其每個(gè)結(jié)點(diǎn)與完全二叉樹(shù)上的結(jié)點(diǎn)相對(duì)照，存儲(chǔ)在一維數(shù)組的相應(yīng)分量中。圖5.11 一般二叉樹(shù)及其順序表示采用順序表示，類(lèi)型聲明如下： struct SeqBinTree /* 順序樹(shù)類(lèi)型定義順序樹(shù)類(lèi)型定義 */ int MAXNUM; int n;DataType *nodelist;；typedef struc

26、t SeqBINTree *PSeqBINTree;運(yùn)算的實(shí)現(xiàn)算法5.9 返回下標(biāo)為p的結(jié)點(diǎn)的父結(jié)點(diǎn)的下標(biāo)int parent_seq(PSeqBinTree t,intint parent_seq(PSeqBinTree t,int p) p) if(p=t-n) return 1; if(p=t-n) return 1; return (p-1)/2; return (p-1)/2; 算法5.10 返回下標(biāo)為p的結(jié)點(diǎn)的左子結(jié)點(diǎn)的下標(biāo)int leftChild_seq(PSeqBinTree t,intint leftChild_seq(PSeqBinTree t,int p) p) if(

27、p=t-n) return 1; if(p=t-n) return 1; return 2 return 2* *p+1;p+1; 算法5.11 返回下標(biāo)為p的結(jié)點(diǎn)的右子結(jié)點(diǎn)的下標(biāo)int rightChild_seq(PSeqBinTree t,intint rightChild_seq(PSeqBinTree t,int p) p) if(p=t-n) return 1; if(p=t-n) return 1; return 2 return 2* *(p+1);(p+1); 二叉樹(shù)的鏈接表示是指用一個(gè)鏈表來(lái)存儲(chǔ)一棵二叉樹(shù)，二叉樹(shù)中的每一個(gè)結(jié)點(diǎn)用鏈表中的一個(gè)鏈結(jié)點(diǎn)來(lái)存儲(chǔ)，最常用的鏈接表示方式

28、是左-右指針表示法（llink-rlink表示法，也稱(chēng)做二叉鏈表），這種表示法在每個(gè)鏈結(jié)點(diǎn)中除存儲(chǔ)結(jié)點(diǎn)本身的數(shù)據(jù)外，再設(shè)置兩個(gè)指針字段：llink和rlink，分別存放結(jié)點(diǎn)的左子女和右子女所在鏈結(jié)點(diǎn)的存儲(chǔ)地址，當(dāng)結(jié)點(diǎn)的某個(gè)子女為空時(shí)，則相應(yīng)的指針為空指針。 struct BinTreeNodestruct BinTreeNode; ; / /* * 二叉樹(shù)中結(jié)點(diǎn)二叉樹(shù)中結(jié)點(diǎn) * */ /typedef struct BinTreeNodetypedef struct BinTreeNode * *PBinTreeNodePBinTreeNode; ;struct BinTreeNodestru

29、ct BinTreeNode DataTypeDataType info; info;/ /* * 數(shù)據(jù)域數(shù)據(jù)域 * */ /PBinTreeNode llinkPBinTreeNode llink; ;/ /* * 指向左子女指向左子女 * */ /PBinTreeNode rlinkPBinTreeNode rlink; ;/ /* * 指向右子女指向右子女 * */ /;typedef struct BinTreeNode typedef struct BinTreeNode * *BinTreeBinTree; ; 算法5.12 返回結(jié)點(diǎn)p的左子結(jié)點(diǎn)的地址PBinTreeNode le

30、ftChild_link(PBinTreeNodePBinTreeNode leftChild_link(PBinTreeNode p) p) if(p=NULL) return NULL; if(p=NULL) return NULL; return p-llink return p-llink; ; 算法5.13 返回結(jié)點(diǎn)p的右子結(jié)點(diǎn)的地址PBinTreeNode rightChild_link(PBinTreeNodePBinTreeNode rightChild_link(PBinTreeNode p) p) if(p=NULL) return NULL; if(p=NULL) ret

31、urn NULL; return p-rlink return p-rlink; ; ABDCEFIHGt A B C E F I H G D 圖5.12(a) 二叉樹(shù)的二叉鏈表表示A B D C E F I H G 圖5.12(b) 三叉鏈表表示t 周游是二叉樹(shù)各種操作的基礎(chǔ)，可以在周游過(guò)程中進(jìn)行各種操作，如可以在周游過(guò)程中生成結(jié)點(diǎn)，從而建立一棵二叉樹(shù)。ABDCEFIHG 例：輸入字符序列： ABDCEGFHI建立如圖所示的二叉樹(shù)，其中，表示空結(jié)點(diǎn)。算法 按先根序列創(chuàng)建二叉樹(shù)ABDCEFIHG算法算法 根據(jù)先根序列創(chuàng)建二叉樹(shù)根據(jù)先根序列創(chuàng)建二叉樹(shù)intint i=0; i=0;BinTree

32、 createRest_BTree(charBinTree createRest_BTree(char * *string)string)/ /* * 遞歸創(chuàng)建從根開(kāi)始的二叉樹(shù)遞歸創(chuàng)建從根開(kāi)始的二叉樹(shù) * */ / PBinTreeNode pbnode PBinTreeNode pbnode; ; char ch char ch; ; ch=stringi ch=stringi+;+; if(ch=) pbnode if(ch=) pbnode=NULL;=NULL; else else pbnode =new struct BinTreeNode pbnode =new struct Bi

33、nTreeNode; ; pbnode-info=ch pbnode-info=ch; ; pbnode-llink=createRest_BTree(string pbnode-llink=createRest_BTree(string);/);/構(gòu)造左子樹(shù)構(gòu)造左子樹(shù) pbnode-rlink=createRest_BTree(stringpbnode-rlink=createRest_BTree(string);/);/構(gòu)造右子樹(shù)構(gòu)造右子樹(shù) return pbnode return pbnode; ; 算法算法5.1void preOrder( BinTreevoid preOrder(

34、BinTree t) t) if (t=NULL) return; if (t=NULL) return; visit(root(t); visit(root(t); preOrder(leftChild(t preOrder(leftChild(t);); preOrder(rightChild(t preOrder(rightChild(t);); 算法算法5.1void preOrdervoid preOrder( BinTree( BinTree t) t) if (t=NULL) return; if (t=NULL) return; cout coutinfo;info; preO

35、rder(t preOrder(t-llink-llink);); preOrder(t preOrder(t-rlink-rlink);); /輸出二叉樹(shù)輸出二叉樹(shù)void disptree1( BinTreevoid disptree1( BinTree p) p) / /先序輸出先序輸出p p為根的二叉樹(shù)為根的二叉樹(shù) if (p=NULL) coutif (p=NULL) cout; return; return; cout coutinfo;info; disptree1(p-llink disptree1(p-llink);); disptree1(p-rlink disptree1

36、(p-rlink);); 算法算法5.1void preOrdervoid preOrder( BinTree( BinTree t) t) if (t=NULL) return; if (t=NULL) return; cout coutinfo;info; preOrder(t preOrder(t-llink-llink);); preOrder(t preOrder(t-rlink-rlink);); void dispTree2( BinTreevoid dispTree2( BinTree t) t) / /以括號(hào)表示法以括號(hào)表示法D(L,R)D(L,R)輸出二叉樹(shù)輸出二叉樹(shù)t t

37、 if (t=NULL) return; if (t=NULL) return; cout coutinfo;info; if(t-llink!=NULL|t-rlink if(t-llink!=NULL|t-rlink!=NULL)!=NULL) coutllink coutllink); ); coutrlink);cout coutrlink);cout);); 作業(yè) ：p.166 復(fù)習(xí)題 1、2、8p.168 算法題 1補(bǔ)充題：1.證明算法5.2二叉樹(shù)中序周游的遞歸算二叉樹(shù)中序周游的遞歸算法的正確性。法的正確性。網(wǎng)絡(luò)課堂測(cè)試：網(wǎng)絡(luò)課堂測(cè)試：5 5 二叉樹(shù)與樹(shù)（二叉樹(shù)與樹(shù)（1 1）二叉樹(shù)

38、的應(yīng)用 5.4.1 5.4.1 堆與優(yōu)先隊(duì)列堆與優(yōu)先隊(duì)列* * 5.4.2 5.4.2 哈夫曼樹(shù)及其應(yīng)用哈夫曼樹(shù)及其應(yīng)用5.4.2 5.4.2 哈夫曼樹(shù)及其應(yīng)用哈夫曼樹(shù)及其應(yīng)用擴(kuò)充二叉樹(shù)的外部路徑長(zhǎng)度：其中：li為從根到第i個(gè)外部結(jié)點(diǎn)的路徑長(zhǎng)度，m為外部結(jié)點(diǎn)的個(gè)數(shù) 1miiEl擴(kuò)充二叉樹(shù)的帶權(quán)的外部路徑長(zhǎng)度 其中：wi是第i個(gè)外部結(jié)點(diǎn)的權(quán)值，li為從根到第i個(gè)外部結(jié)點(diǎn)的路徑長(zhǎng)度，m為外部結(jié)點(diǎn)的個(gè)數(shù)。 1mi iiWPLwl哈夫曼樹(shù) 假設(shè)有一組（無(wú)序）實(shí)數(shù)w1 , w2 , w3 , wm，現(xiàn)要構(gòu)造一棵以wi（i = 1,2,，m）為權(quán)的m個(gè)外部結(jié)點(diǎn)的擴(kuò)充的二叉樹(shù)，使得帶權(quán)的外部路徑長(zhǎng)度WPL最

39、小。滿(mǎn)足這一要求的擴(kuò)充二叉樹(shù)就稱(chēng)為哈夫曼樹(shù)哈夫曼樹(shù)或最優(yōu)二叉樹(shù)最優(yōu)二叉樹(shù)。l例如以下是帶有相同權(quán)值例如以下是帶有相同權(quán)值5,4,7,2,5的四棵二叉樹(shù)。的四棵二叉樹(shù)。24575(a)24575(b)27545(c)24575(d)它們的帶權(quán)路徑長(zhǎng)度分別為：它們的帶權(quán)路徑長(zhǎng)度分別為：(a)WPL=2 1+7 4+5 4+5 3+4 2=73(b)WPL=7 3+ 4 3+5 3+5 3+2 1=65(c)WPL=5 2+ 5 2+2 3+4 3+7 2=52(d)WPL=4 3+ 2 3+7 2+5 2+5 2=52其中其中(c)和和(d)樹(shù)的帶權(quán)路徑長(zhǎng)度為最小。樹(shù)的帶權(quán)路徑長(zhǎng)度為最小?？梢则?yàn)證

40、它們恰為最優(yōu)二叉樹(shù)?？梢则?yàn)證它們恰為最優(yōu)二叉樹(shù)。在解某些判定問(wèn)題時(shí)，利用赫夫曼樹(shù)可以得到最在解某些判定問(wèn)題時(shí)，利用赫夫曼樹(shù)可以得到最佳判定算法。佳判定算法。例如，編制一個(gè)將百分制轉(zhuǎn)換成五級(jí)分制的程序。例如，編制一個(gè)將百分制轉(zhuǎn)換成五級(jí)分制的程序。通常的算法是：通常的算法是：If(a60) b=E;If(a60) b=E;else if(a70) b=D;else if(a70) b=D; else if(a80) b=C; else if(a80) b=C; else if(a90) b=B; else if(a90) b=B; else b=A else b=A；l在實(shí)際生活中，學(xué)生的成績(jī)?cè)谖?/p>

41、個(gè)等級(jí)上的分布是不在實(shí)際生活中，學(xué)生的成績(jī)?cè)谖鍌€(gè)等級(jí)上的分布是不均勻的。假設(shè)其分布規(guī)律如下表示：均勻的。假設(shè)其分布規(guī)律如下表示：分?jǐn)?shù)分?jǐn)?shù)0596069 7079 8089 90100比例數(shù)比例數(shù)0.050.150.400.300.10d60d90d80d70EDCABYYYYNNNN0.050.150.40.30.1WPL=3.15d60CBDAEYYYYNNNN0.40.30.150.050.1WPL=2.0570d 8080d 9060d 70d60d70d80CEDNNYYYYd=0)個(gè)結(jié)點(diǎn)結(jié)點(diǎn)的有限集T。當(dāng)T非空時(shí)，滿(mǎn)足：（1）有且僅有一個(gè)特別標(biāo)出的稱(chēng)為根根的 結(jié)點(diǎn)；（2）除除根結(jié)點(diǎn)根

42、結(jié)點(diǎn)外，其余結(jié)點(diǎn)可分為m（m=0） 個(gè)互不相交非空的有限集T1, T2, , Tm, 其中 每一個(gè)集合本身又是一棵樹(shù)，稱(chēng)為根的子樹(shù)子樹(shù) (Subtree)?？諛?shù)空樹(shù)：不包括任何結(jié)點(diǎn)的樹(shù)。l在樹(shù)中也可以定義父結(jié)點(diǎn)、子結(jié)點(diǎn)、路徑、路徑長(zhǎng)度、結(jié)點(diǎn)的度、樹(shù)的度等概念，與前面二叉樹(shù)中定義相同。 無(wú)序樹(shù)無(wú)序樹(shù)、有序樹(shù)有序樹(shù)對(duì)子樹(shù)的次序不加區(qū)別的樹(shù)叫作無(wú)序樹(shù)無(wú)序樹(shù)。對(duì)子樹(shù)之間的次序加以區(qū)別的樹(shù)叫作有序樹(shù)有序樹(shù)。例如在圖5.24中，按無(wú)序樹(shù)的概念t和t是同一棵樹(shù)，按有序樹(shù)的概念則是不同的樹(shù)，本章討論的樹(shù)一般是有序樹(shù)。 結(jié)點(diǎn)的次序結(jié)點(diǎn)的次序 在有序樹(shù)中可以從左到右地規(guī)定結(jié)點(diǎn)的次序次序。按從左到右的順序，我們可以

43、把一個(gè)結(jié)點(diǎn)的最左邊的子結(jié)點(diǎn)簡(jiǎn)稱(chēng)為最左子結(jié)點(diǎn)最左子結(jié)點(diǎn)，或直接稱(chēng)為長(zhǎng)子長(zhǎng)子，而把長(zhǎng)子右邊的結(jié)點(diǎn)稱(chēng)為次子次子。例如在t中結(jié)點(diǎn)B是結(jié)點(diǎn)A的長(zhǎng)子，結(jié)點(diǎn)C是結(jié)點(diǎn)A的次子，是結(jié)點(diǎn)B的兄弟。 5.5.2 抽象數(shù)據(jù)類(lèi)型ADT Tree isoperations Tree createEmptyTree(void) 創(chuàng)建一顆空樹(shù) Tree consTree(Node p, Tree t1,.,Tree ti) 以p為根，t1,.,ti為子樹(shù)創(chuàng)建一顆樹(shù) int isNull(Tree t) 判斷樹(shù)t是否為空樹(shù) Node root(Tree t) 返回樹(shù)t的根結(jié)點(diǎn)。 Node parent(Node p) 返回結(jié)點(diǎn)

44、p的父結(jié)點(diǎn)。 Tree leftChild(Tree t) 返回樹(shù)t的長(zhǎng)子樹(shù)。 Tree rightSibling(Tree t) 返回樹(shù)t的右兄弟樹(shù)。end ADT Tree5.5.3 5.5.3 樹(shù)的周游樹(shù)的周游周游的定義:按某一規(guī)律系統(tǒng)的訪(fǎng)問(wèn)樹(shù)中的所有 結(jié)點(diǎn)，并使每個(gè)結(jié)點(diǎn)恰好被訪(fǎng)問(wèn)一次。周游的方法：按深度方向和按寬度方向周游。按深度方向（以右圖為例） 先根次序 后根次序 先根次序 (1,2,3,5,8,9,6,10,4,7) （1） 訪(fǎng)問(wèn)根結(jié)點(diǎn)； （2）從左到右按先根次序周游根結(jié)點(diǎn)的每棵子樹(shù)。 后根次序 (2,8,9,5,10,6,3,7,4,1) （1）從左到右按后根次序周游根結(jié)點(diǎn)的每

45、棵子樹(shù); （2）訪(fǎng)問(wèn)根結(jié)點(diǎn)。按寬度方向周游 先訪(fǎng)問(wèn)層數(shù)為0的結(jié)點(diǎn)，然后從左到右逐個(gè)訪(fǎng) 問(wèn)層數(shù)為1的結(jié)點(diǎn)，依此類(lèi)推，直到訪(fǎng)問(wèn)完樹(shù)中 的全部結(jié)點(diǎn)。 層次序列（1，2，3，4，5，6，7，8，9，10）5.6 5.6 樹(shù)的實(shí)現(xiàn)樹(shù)的實(shí)現(xiàn)struct ParTreeNode/* 樹(shù)中結(jié)點(diǎn)結(jié)構(gòu) */ DataTypeinfo; /* 結(jié)點(diǎn)中的元素 */intparent; /* 結(jié)點(diǎn)的父結(jié)點(diǎn)位置 */;struct ParTree struct ParTreeNode nodelistMAXNUM; /* 存放樹(shù)中的結(jié)點(diǎn) */ int n; /* 樹(shù)中結(jié)點(diǎn)的個(gè)數(shù) */; typedef struct Pa

46、rTree *PParTree;5.6.1 父指針表示法用一組連續(xù)空間存儲(chǔ)樹(shù)的結(jié)點(diǎn)，并附設(shè)一個(gè)指示器指示其雙親結(jié)點(diǎn)的位置。結(jié)構(gòu)類(lèi)型如下： 優(yōu)點(diǎn)：a)容易找到父結(jié)點(diǎn)及其所有的祖先； b)能找到結(jié)點(diǎn)的子女和兄弟； 缺點(diǎn)：a)沒(méi)有表示出結(jié)點(diǎn)之間的左右次序； b)找結(jié)點(diǎn)的子女和兄弟比較費(fèi)事。改進(jìn)方法：按一種周游次序在數(shù)組中存放結(jié)點(diǎn),。常見(jiàn)的一種方法是依次存放樹(shù)的先根序列，如下圖：(a) (b) 圖5.5 一棵樹(shù)的父指針表示 算法5.6 5.75.6.2 樹(shù)的子表表示法 結(jié)點(diǎn)表中的每一元素又包含一個(gè)子表，存放該結(jié)點(diǎn)的所有子結(jié)點(diǎn)。結(jié)點(diǎn)表順序存放，子表用鏈接表示。struct EdgeNode /* 子表中

47、節(jié)點(diǎn)的結(jié)構(gòu) */intnodeposition;struct EdgeNode*link;struct ChiTreeNode /* 結(jié)點(diǎn)表中節(jié)點(diǎn)的結(jié)構(gòu) */DataTypeinfo;struct EdgeNode*children;子表表示的樹(shù)結(jié)構(gòu)定義如下：struct ChiTree /* 樹(shù)結(jié)構(gòu) */ struct ChiTreeNode nodelistMAXNUM; introot; /* 根結(jié)點(diǎn)的位置 */ intn; /* 結(jié)點(diǎn)的個(gè)數(shù) */typedef struct ChiTree * PChiTree; 求某個(gè)結(jié)點(diǎn)的最左子女運(yùn)算很容易實(shí)現(xiàn)，找到結(jié)點(diǎn)的全部子女也很容易，但求某個(gè)

48、結(jié)點(diǎn)的父母和右兄弟實(shí)現(xiàn)起來(lái)比較費(fèi)事。另一個(gè)缺點(diǎn)是：合并若干個(gè)子樹(shù)構(gòu)成一個(gè)新樹(shù)時(shí)（createTree_chitree操作）也要考慮多個(gè)結(jié)點(diǎn)表的合并問(wèn)題，由于這些結(jié)點(diǎn)表通常用順序方式表示，所以合并起來(lái)比較麻煩。 1 7 2 3 4 6 8 9 5 圖5.6 樹(shù)的子表表示法children 在樹(shù)的每個(gè)結(jié)點(diǎn)中，除信息域外，增加指向其最左子女和右兄弟的指針。struct CSNode; /* 樹(shù)中結(jié)點(diǎn)結(jié)構(gòu) */typedef struct CSNode *PCSNode;/ 結(jié)點(diǎn)的指針類(lèi)型 struct CSNode /* 結(jié)點(diǎn)結(jié)構(gòu)定義 */ DataType info;/* 結(jié)點(diǎn)中的元素 */PCS

49、Node lchild; /* 結(jié)點(diǎn)的最左子女的指針 */PCSNode rsibling; /* 結(jié)點(diǎn)的右兄弟的指針 */; typedef struct CSNode *CSTree; /* 樹(shù)類(lèi)型定義 */ 5.6.3 樹(shù)的長(zhǎng)子-兄弟表示法 t a b d c e h i j f g 圖5.7 樹(shù)的長(zhǎng)子兄弟表法樹(shù)林樹(shù)林：是m（m=0）棵互不相交的樹(shù)所組成的集合。樹(shù)林中所有的樹(shù)都是有序的，彼此稱(chēng)為兄弟。 先根次序周游：首先訪(fǎng)問(wèn)樹(shù)林中第一棵樹(shù)的根結(jié)點(diǎn)；然后先根次序周游根結(jié)點(diǎn)的所有子樹(shù)構(gòu)成的樹(shù)林；最后先根周游除去第一棵樹(shù)后剩下的樹(shù)林。A, B, C, K, D, E, H, F, J, G 5

50、.7.1 5.7.1 樹(shù)林的周游樹(shù)林的周游 后根次序周游：首先后根次序周游第一棵樹(shù)根結(jié)點(diǎn)的所有子樹(shù)構(gòu)成的樹(shù)林；然后訪(fǎng)問(wèn)第一棵樹(shù)的根結(jié)點(diǎn)；最后后根周游除去第一棵樹(shù)后剩下的樹(shù)林。 B, K, C, A, H, E, J, F, G, D 5.7.2 5.7.2 樹(shù)林的存儲(chǔ)表示樹(shù)林的存儲(chǔ)表示 父指針表示法 子表表示法 長(zhǎng)子-兄弟表示法樹(shù)林的父結(jié)點(diǎn)表示方法 1 2 3 5 9 8 6 7 樹(shù)林的子表表示法 t A B D C E H J K F G 樹(shù)林的長(zhǎng)子兄弟表示法5.7.3 5.7.3 樹(shù)林與二叉樹(shù)的轉(zhuǎn)換樹(shù)林與二叉樹(shù)的轉(zhuǎn)換 1. 樹(shù)、樹(shù)林轉(zhuǎn)換為二叉樹(shù)執(zhí)行步驟：（1）在所有相鄰的兄弟結(jié)點(diǎn)之間連一條

51、線(xiàn)；（2）對(duì)每個(gè)非終端結(jié)點(diǎn)，只保留它到其最左子女的 連線(xiàn)，刪去它與其它子女的連線(xiàn)；（3）以根結(jié)點(diǎn)為軸心，將整棵樹(shù)進(jìn)行旋轉(zhuǎn)。樹(shù)、樹(shù)林樹(shù)、樹(shù)林 二叉樹(shù)二叉樹(shù)ABCKDEFGHJ圖5.20 樹(shù)林轉(zhuǎn)換為二叉樹(shù)ABCKDEFGHJl樹(shù)樹(shù)-二叉樹(shù)二叉樹(shù)ABDCEFHG兄弟連線(xiàn)兄弟連線(xiàn)保留父母到第一個(gè)保留父母到第一個(gè)(最左最左)孩子的連線(xiàn)孩子的連線(xiàn)去除父母與其它孩子的連線(xiàn)去除父母與其它孩子的連線(xiàn)第一個(gè)孩子作為左孩子，右兄弟降為右子女第一個(gè)孩子作為左孩子，右兄弟降為右子女ABDCEFHGABDCEFHG執(zhí)行步驟：（1）若某結(jié)點(diǎn)是其父母的左子女，則把該結(jié)點(diǎn) 的右子女，右子女的右子女， ,都與 該結(jié)點(diǎn)的父母用線(xiàn)連接起來(lái)； （2）去掉原二叉樹(shù)中所有父母到右子女的連線(xiàn)。ABDCEKHFJG圖 5.22 二叉樹(shù)轉(zhuǎn)換為樹(shù)林ABDCEKHFJG圖 5.22 二叉樹(shù)轉(zhuǎn)換為樹(shù)林lP.166 l復(fù)習(xí)題 6、11、12、13、14l網(wǎng)絡(luò)課堂測(cè)試：網(wǎng)絡(luò)課堂測(cè)試：5 5 二叉樹(shù)與樹(shù)（二叉樹(shù)與樹(shù)（2 2）l實(shí)驗(yàn)實(shí)驗(yàn)4.1-4.44.1-4.4l樹(shù)、樹(shù)林、二叉樹(shù)的一些基本概念和術(shù)語(yǔ)；l二叉鏈表存儲(chǔ)結(jié)構(gòu)l樹(shù)、二叉樹(shù)的周游l哈夫曼樹(shù)的構(gòu)造方法及應(yīng)用