《信息與通信樹》教學(xué)課件

1、第6章 樹 6.1 樹的應(yīng)用實(shí)例6.2 樹的基本概念和術(shù)語 6.3 二叉樹 6.4 遍歷二叉樹 6.5 線索二叉樹 6.6 二叉樹、樹和森林 6.7 樹的應(yīng)用 6.8 實(shí)習(xí): 二叉樹的建立和遍歷 習(xí)題6 第1頁，共91頁。6.1 樹的應(yīng)用實(shí)例 例6.1 如圖6.1為某校計(jì)算機(jī)系領(lǐng)導(dǎo)結(jié)構(gòu)圖。 例6.2 家族樹 第2頁，共91頁。圖6.1 某校計(jì)算機(jī)系領(lǐng)導(dǎo)結(jié)構(gòu)圖 第3頁，共91頁。圖6.2 家族樹 第4頁，共91頁。6.2 樹的基本概念和術(shù)語 6.2.1 樹的定義 樹(Tree)是由一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合T。其中： (1) 有一個(gè)特定的結(jié)點(diǎn)稱為該樹的根(Root)結(jié)點(diǎn)； (2) 除根結(jié)點(diǎn)之外

2、的其余結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的有限集合T1，T2，Tm，且其中每一個(gè)集合本身又是一棵樹，稱之為根的子樹(Subtree)。 這是一個(gè)遞歸的定義，即在定義中又用到了樹這個(gè)術(shù)語。它道出了樹的固有特性。僅有一個(gè)根結(jié)點(diǎn)的樹是最小樹，樹中結(jié)點(diǎn)較多時(shí)，每個(gè)結(jié)點(diǎn)都是某一棵子樹的根。 第5頁，共91頁。 圖6.3是一棵由9個(gè)結(jié)點(diǎn)組成的樹T。其中A是根結(jié)點(diǎn)，其余結(jié)點(diǎn)分為三個(gè)互不相交的子集：T1=B,H,I，T2=C，T3=D,E,F,G。T1、T2、T3都是樹根A的子樹，這三棵子樹的根結(jié)點(diǎn)分別是B、C、D。每棵子樹本身也是一棵樹，可繼續(xù)劃分。例如子樹T3以D為根結(jié)點(diǎn)，它的其余結(jié)點(diǎn)又可分為兩個(gè)互不相交的子

3、集：T31=E，T32=F，G，而其中T31可以認(rèn)為是僅有一個(gè)根結(jié)點(diǎn)的子樹。 第6頁，共91頁。圖6.3 樹T 第7頁，共91頁。6.2.2 樹的表示 （1）樹形圖表示 樹形圖表示是樹結(jié)構(gòu)的主要表示方法。 樹的樹形圖表示中：結(jié)點(diǎn)用圓圈表示，結(jié)點(diǎn)的名字寫在圓圈旁邊（有時(shí)亦可寫在圓圈內(nèi)）。（2）樹的其他表示法 嵌套集合表示法 是用集合的包含關(guān)系來描述樹結(jié)構(gòu)。 上圖(a)樹的嵌套集合表示法如圖(b) 凹入表表示法 類似于書的目錄，上圖(a)樹的凹入表示法如圖(c) 廣義表表示法 用廣義表的形式表示的。上圖(a)樹的廣義表表示法如圖(d)（A（B（E，F(xiàn)（I，J），C，D（G，H）第8頁，共91頁。第

4、9頁，共91頁。6.2.3 樹的常用術(shù)語 1. 結(jié)點(diǎn)的度和樹的度 樹的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支。結(jié)點(diǎn)擁有的子樹數(shù)稱為結(jié)點(diǎn)的度(Degree)。而樹的度是指樹中結(jié)點(diǎn)的度的最大值。如圖6.3中，B結(jié)點(diǎn)有2個(gè)子樹，則它的度為2。在樹T中，A結(jié)點(diǎn)的度最大，值為3，也就是說，樹T的度為3。 第10頁，共91頁。 2. 分支結(jié)點(diǎn)和葉子結(jié)點(diǎn) 稱度不為0的結(jié)點(diǎn)為分支結(jié)點(diǎn)，也叫非終端結(jié)點(diǎn)。稱度為0的結(jié)點(diǎn)為葉子(Leaf)或終端結(jié)點(diǎn)。如圖6.3中，分支結(jié)點(diǎn)分別為A、B、D、F，而葉子結(jié)點(diǎn)分別為H、I、C、E、G。第11頁，共91頁。 3. 孩子、雙親、兄弟、子孫、祖先 結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的

5、孩子(Child)，相應(yīng)地，該結(jié)點(diǎn)稱為孩子的雙親(Parent)。同一個(gè)雙親的孩子之間互稱兄弟(Sibling)。如圖6.3中，B、C、D分別是根結(jié)點(diǎn)A的子樹的根，三個(gè)都是A的孩子，相應(yīng)地，A是它們的雙親，其中，B、C、D三者是兄弟。一棵樹上除根結(jié)點(diǎn)以外的其它結(jié)點(diǎn)稱為根結(jié)點(diǎn)的子孫。對于樹中某結(jié)點(diǎn)，從根結(jié)點(diǎn)開始到該結(jié)點(diǎn)的雙親是該結(jié)點(diǎn)的祖先。 第12頁，共91頁。 4. 結(jié)點(diǎn)的層次和樹的高度 結(jié)點(diǎn)的層次(Level)從根結(jié)點(diǎn)開始定義，根為第一層，根結(jié)點(diǎn)的孩子為第二層，依次類推，其余結(jié)點(diǎn)的層次值為雙親結(jié)點(diǎn)層次值加1。樹中結(jié)點(diǎn)的最大層次值稱為樹的高度或深度(Depth)。如圖6.3所示的樹T高度為4。

6、 第13頁，共91頁。 5. 無序樹、有序樹、森林 若樹中結(jié)點(diǎn)的各子樹看成從左至右是有次序的(即不能互換)，則稱該樹為有序樹，否則稱為無序樹。在有序樹中最左邊的子樹的根稱為第一個(gè)孩子，最右邊的稱為最后一個(gè)孩子。 森林(Forest)是m(m0)棵互不相交的樹的集合。對樹中每個(gè)結(jié)點(diǎn)而言，其子樹的集合即為森林。 第14頁，共91頁。6.3 二 叉 樹 6.3.1 二叉樹的定義 二叉樹(Binary Tree)是n(n0)個(gè)結(jié)點(diǎn)的有限集合。它或?yàn)榭諛?n0)，或?yàn)榉强諛洌粚τ诜强諛溆校?(1) 有一個(gè)特定的稱之為根的結(jié)點(diǎn)； (2) 根結(jié)點(diǎn)以外的其余結(jié)點(diǎn)分別由兩棵互不相交的稱之為左子樹和右子樹的二叉樹

7、組成。第15頁，共91頁。 這個(gè)遞歸定義表明二叉樹或?yàn)榭?，或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的互不相交的二叉樹組成的。由于左、右子樹也是二叉樹，則由二叉樹的定義，它們也可以為空。由此，二叉樹可以有五種基本形態(tài)，如圖6.5所示。 圖6.5 二叉樹的五種基本形態(tài)(a) 空二叉樹; (b) 只有一個(gè)根結(jié)點(diǎn); (c) 有根結(jié)點(diǎn)和左子樹;(d) 有根結(jié)點(diǎn)和右子樹; (e) 有根結(jié)點(diǎn)和左、右子樹 第16頁，共91頁。 有兩種特殊形態(tài)的二叉樹，它們是滿二叉樹和完全二叉樹。 滿二叉樹：深度為k且含有2k1個(gè)結(jié)點(diǎn)的二叉樹為滿二叉樹，這種樹的特點(diǎn)是每層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)，如圖6.6(a)所示。對

8、滿二叉樹的結(jié)點(diǎn)可以從根結(jié)點(diǎn)開始自上向下，自左至右順序編號，圖6.6(a)中每個(gè)結(jié)點(diǎn)邊的數(shù)字即是該結(jié)點(diǎn)的編號。 完全二叉樹：深度為k，含有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)每個(gè)結(jié)點(diǎn)的編號與相應(yīng)滿二叉樹結(jié)點(diǎn)順序號從1到n相對應(yīng)時(shí)，則稱此二叉樹為完全二叉樹，如圖6.6(b)所示。而圖6.6(c)則不是完全二叉樹。 第17頁，共91頁。圖6.6 滿二叉樹和完全二叉樹(a) 滿二叉樹；(b) 完全二叉樹；(c) 非完全二叉樹 第18頁，共91頁。6.3.2 二叉樹的重要性質(zhì) 性質(zhì)1 二叉樹第i(i1)層上至多有2i-1個(gè)結(jié)點(diǎn)。 根據(jù)二叉樹和結(jié)點(diǎn)層次的定義可知，根結(jié)點(diǎn)在第一層上，這層結(jié)點(diǎn)數(shù)至多為1個(gè)，即20個(gè)；顯

9、然第二層上至多有2個(gè)結(jié)點(diǎn)，即21個(gè) 假設(shè)第i1層的結(jié)點(diǎn)至多有2i-2個(gè)，且每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，那么第i層上結(jié)點(diǎn)至多有22i-2=2i-1個(gè)。 第19頁，共91頁。 性質(zhì)2 深度為k(k1)的二叉樹至多有2k1個(gè)結(jié)點(diǎn)。 由性質(zhì)1可知，各層結(jié)點(diǎn)最多數(shù)目之和為20+21+22+2k-1；由二進(jìn)制換算關(guān)系可知：20+21+22+2k-1=2k1，因此二叉樹中結(jié)點(diǎn)的最大數(shù)目為2k1。 第20頁，共91頁。 性質(zhì)3 在任意二叉樹中，若葉子結(jié)點(diǎn)(即度為零的結(jié)點(diǎn))個(gè)數(shù)為n0，度為1的結(jié)點(diǎn)個(gè)數(shù)為n1，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，那么n0=n2+1。 證明：設(shè)n代表二叉樹結(jié)點(diǎn)總數(shù)，那么 n=n0+n1+n2 (1

10、) 由于有n個(gè)結(jié)點(diǎn)的二叉樹總分支數(shù)為n1條，于是得 n1=0n0+1n1+2n2 (2) 將式(1)代入式(2)得n0=n2+1 第21頁，共91頁。 性質(zhì)4 具有n個(gè)結(jié)點(diǎn)的完全二叉樹深度為 log2n+1(其中x表示不大于x的最大整數(shù))。 第22頁，共91頁。 性質(zhì)5 若對有n(1in)個(gè)結(jié)點(diǎn)的完全二叉樹進(jìn)行順序編號，那么，對于編號為i(i1)的結(jié)點(diǎn)： 當(dāng)i=1時(shí)，該結(jié)點(diǎn)為根，它無雙親結(jié)點(diǎn)； 當(dāng)i1時(shí)，該結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號為i/2 ； 若2in，則有編號為2i的左孩子，否則沒有左孩子； 若2i+1n，則有編號為2i+1的右孩子，否則沒有右孩子。 第23頁，共91頁。6.3.3 二叉樹的存儲結(jié)

11、構(gòu) 二叉樹常用的存儲結(jié)構(gòu)有兩種，即順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。 (1) 順序存儲結(jié)構(gòu)(向量)可以作為二叉樹的存儲結(jié)構(gòu)。這種存儲結(jié)構(gòu)適用于完全二叉樹和滿二叉樹。假設(shè)用一維數(shù)組a存放圖6.6(a)所示的滿二叉樹?？梢园l(fā)現(xiàn)圖6.6(a)中結(jié)點(diǎn)的編號恰好與數(shù)組元素的下標(biāo)相對應(yīng)，見圖6.7。根據(jù)二叉樹性質(zhì)5，在a數(shù)組中可以方便地由某結(jié)點(diǎn)ai的下標(biāo)i找到它們的雙親結(jié)點(diǎn)ai/2或左、右孩子結(jié)點(diǎn)a2i、a2i+1。在哈夫曼樹構(gòu)造算法中也用到順序存儲結(jié)構(gòu)。一般二叉樹較少采用順序存儲結(jié)構(gòu)。 第24頁，共91頁。1234567891011121314ABCDEFGHJKLMNO圖6.7 二叉樹的順序存儲結(jié)構(gòu) 第25

12、頁，共91頁。 (2) 鏈表存儲結(jié)構(gòu)通常用于二叉樹存儲。常見的有二叉鏈表和三叉鏈表。二叉鏈表的每個(gè)結(jié)點(diǎn)都有一個(gè)數(shù)據(jù)域和兩個(gè)指針域，一個(gè)指針指向左孩子，另一個(gè)指針指向右孩子。typedef struct node datatype data； /*數(shù)據(jù)域*/struct node *lch，*rch； /*左、右指針域*/ BinTNode ; typedef BinTNode *BinTree；/BinTree為指向BinTNode類型結(jié)點(diǎn)的指針類型 第26頁，共91頁。 三叉鏈表的結(jié)點(diǎn)比二叉鏈表多了一個(gè)指向雙親的指針域。結(jié)點(diǎn)結(jié)構(gòu)如圖6.8(b)所示，可以描述為： typedef struct

13、 datatype data； /*數(shù)據(jù)域*/ struct BTlink3 *lch，*parent，*rch；/*parent是雙親指針域*/ Bnode3;第27頁，共91頁。lchdatarchlchdataparentrch(a) (b) 圖6.8 二叉樹鏈表存儲結(jié)構(gòu)中的結(jié)點(diǎn)結(jié)構(gòu)(a) 二叉鏈表中的結(jié)點(diǎn)結(jié)構(gòu)；(b) 三叉鏈表中的結(jié)點(diǎn)結(jié)構(gòu) 第28頁，共91頁。圖6.9 二叉樹的鏈表存儲結(jié)構(gòu) 第29頁，共91頁。6.4 遍歷二叉樹 在二叉樹的應(yīng)用中，常常需要在樹中搜索具有某種特征的結(jié)點(diǎn)，或?qū)渲腥康慕Y(jié)點(diǎn)逐一進(jìn)行處理。這就涉及到一個(gè)遍歷二叉樹的問題。遍歷二叉樹是指以一定的次序訪問二叉樹中

14、的每個(gè)結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)僅被訪問一次。所謂訪問結(jié)點(diǎn)，就是指對結(jié)點(diǎn)進(jìn)行各種操作。例如，查詢結(jié)點(diǎn)數(shù)據(jù)域的內(nèi)容，或輸出它的值，或找出結(jié)點(diǎn)位置，或執(zhí)行對結(jié)點(diǎn)的其他操作。遍歷二叉樹的過程實(shí)質(zhì)是把二叉樹的結(jié)點(diǎn)進(jìn)行線性排列的過程。對于線性結(jié)構(gòu)來說，遍歷很容易實(shí)現(xiàn)，順序掃描結(jié)構(gòu)中的每個(gè)數(shù)據(jù)元素即可。但二叉樹是非線性結(jié)構(gòu)，遍歷時(shí)是先訪問根結(jié)點(diǎn)還是先訪問子樹，是先訪問左子樹還是先訪問右子樹必須有所規(guī)定，這就是遍歷規(guī)則。采用不同的遍歷規(guī)則會產(chǎn)生不同的遍歷結(jié)果，因此必須人為設(shè)定遍歷規(guī)則。 第30頁，共91頁。 由于一棵非空二叉樹是由根結(jié)點(diǎn)、左子樹和右子樹三個(gè)基本部分組成的，遍歷二叉樹時(shí)只要按順序依次遍歷這三部分即可。

15、假定我們以D、L、R分別表示訪問根結(jié)點(diǎn)、遍歷左子樹和遍歷右子樹，則可以有六種遍歷形式：DLR、LDR、LRD、DRL、RDL、RLD，若依習(xí)慣規(guī)定先左后右，則上述六種形式可歸并為三種形式，即：DLR 先序遍歷LDR 中序遍歷 LRD 后序遍歷 第31頁，共91頁。6.4.1 先序遍歷先序遍歷可以遞歸地描述如下： 如果二叉樹為空，則空操作，否則： 訪問根結(jié)點(diǎn)； 按先序次序遍歷左子樹； 按先序次序遍歷右子樹。 先序遍歷的遞歸算法如下: 第32頁，共91頁。 /*算法描述6.2 先序遍歷的遞歸算法*/ void preorder(BTlink * p) if(p!=NULL) printf(%cn，

16、p-data)； /*訪問根結(jié)點(diǎn)*/preorder(p-lch)； /*按先根次序遍歷左子樹*/preorder(p-rch)； /*按先根次序遍歷右子樹*/ /*preorder*/ 第33頁，共91頁。圖6.11 遍歷序列示例 第34頁，共91頁。6.4.2 中序遍歷 中序遍歷可以遞歸地描述如下： 如果二叉樹為空，則空操作，否則： 按中序次序遍歷左子樹， 訪問根結(jié)點(diǎn)， 按中序次序遍歷右子樹。 中序遍歷遞歸算法如下:第35頁，共91頁。/*算法描述6.3 中序遍歷的遞歸算法*/ void inorder(BTlink *p) if (p!=NULL) inorder(p-lch)； /*中

17、序遍歷左子樹*/ printf(%cn，p-data)； /*訪問根結(jié)點(diǎn)*/ inorder(p-rch)； /*中序遍歷右子樹*/ /*inorder*/ 例如，圖6.11(a)所示二叉樹的中根遍歷序列為BAC, 圖6.11(b)所示二叉樹的中根遍歷序列為BCAEDF。 第36頁，共91頁。6.4.3 后根遍歷 后根遍歷可以遞歸地描述如下：如果二叉樹為空，則空操作，否則： 后序遍歷左子樹； 后序遍歷右子樹； 訪問根結(jié)點(diǎn)。 后根遍歷遞歸算法如下： 第37頁，共91頁。 /*算法描述6.4 后序遍歷的遞歸算法*/void postorder (BTlink* p ) if ( p!= NULL

18、) postorder ( p-lch);/*后序遍歷左子樹*/ postorder ( p-rch ); /*后根遍歷右子樹*/ printf ( %cn，p-data); /*訪問根結(jié)點(diǎn)*/ /*postorder*/例如，圖6.11(a)所示二叉樹的后序遍歷序列為BCA, 圖6.11(b)所示二叉樹的后根遍歷序列為CBEFDA。 第38頁，共91頁。6.4.4 思考已知一棵二叉樹的前序跟中序遍歷序列，是否能求得這棵二叉樹？第39頁，共91頁。6.4.5 二叉樹的應(yīng)用二叉樹的初始化void CreateBinTree (BinTree *T) /構(gòu)造二叉鏈表。T是指向根指針的指針，故修改*

19、T就修改了實(shí)參(根指針)本身 char ch； if(ch=getchar()=) T=NULL； /讀人空格，將相應(yīng)指針置空 else /讀人非空格 *T=(BinTNode *)malloc(sizeof(BinTNode)； /生成結(jié)點(diǎn) (*T)-data=ch； CreateBinTree(&(*T)-lchild)； /構(gòu)造左子樹 CreateBinTree(&(*T)-rchild)； /構(gòu)造右子樹 第40頁，共91頁。6.5 線索二叉樹 6.5.1 線索二叉樹的基本概念 我們發(fā)現(xiàn)，具有n個(gè)結(jié)點(diǎn)的二叉樹中有n 1條邊指向其左、右孩子，這意味著在二叉鏈表中的2n個(gè)孩子指針域中只用到了

20、n 1 個(gè)域，還有另外n+1個(gè)指針域是空的。我們可充分利用這些空指針來存放結(jié)點(diǎn)的線性前驅(qū)和后繼信息。 試作如下規(guī)定：若結(jié)點(diǎn)有左子樹，則其lch域指示其左孩子，否則令lch域指示其直接前驅(qū)；若結(jié)點(diǎn)有右子樹，則其rch域指示其右孩子，否則令rch域指示其直接后繼。為了嚴(yán)格區(qū)分結(jié)點(diǎn)的孩子指針域究竟指向孩子結(jié)點(diǎn)還是指向前驅(qū)或后繼結(jié)點(diǎn)，需在原結(jié)點(diǎn)結(jié)構(gòu)中增加兩個(gè)標(biāo)志域。新的結(jié)點(diǎn)結(jié)構(gòu)為： 第41頁，共91頁。lchltagdatartagrch其中：ltag=0 表示lch指示結(jié)點(diǎn)的左孩子ltag=1 表示lch指示結(jié)點(diǎn)的直接前驅(qū)rtag=0 表示rch指示結(jié)點(diǎn)的右孩子rtag=1 表示rch指示結(jié)點(diǎn)的直接

21、后繼算法描述為：struct xtreenode char data; struct xtreenode *lch,*rch; int ltag,rtag; /*左、右標(biāo)志域*/ 第42頁，共91頁。 通常把指向前驅(qū)或后繼的指針稱做線索。對二叉樹以某種次序進(jìn)行遍歷并且加上線索的過程稱做線索化。經(jīng)過線索化之后生成的二叉鏈表表示稱為線索二叉樹。 對一個(gè)已建好的二叉樹的二叉鏈表進(jìn)行線索化時(shí)規(guī)定(對p結(jié)點(diǎn))： (1) p有左孩子時(shí)，則令左特征域p-ltag = 0; (2) p無左孩子時(shí)，令p-ltag = 1, 并且p-lch指向p的前驅(qū)結(jié)點(diǎn); (3) p有右孩子時(shí)，令p-rtag = 0; (4)

22、 p無右孩子時(shí)，令p-rtag = 1,并且讓p-rch指向p的后繼結(jié)點(diǎn)。 第43頁，共91頁。圖6.12 中根次序線索樹(a) 二叉樹；(b) 中根次序線索樹 第44頁，共91頁。6.5.2 線索二叉樹的邏輯表示圖 按照不同的次序進(jìn)行線索化，可得到不同的線索二叉樹，即先根線索二叉樹、中根線索二叉樹和后根線索二叉樹。對圖6.13(a)所示的二叉樹進(jìn)行線索化，可得到圖6.13(b)、(c)、(d)所示的三種線索二叉樹的邏輯表示。 第45頁，共91頁。圖6.13 線索二叉樹的邏輯表示圖二叉樹；(b) 先根線索二叉樹；(c) 中根線索二叉樹；(d) 后根線索二叉樹 第46頁，共91頁。6.5.3 中

23、根次序線索化算法 這里重點(diǎn)介紹中根次序線索化的算法。中根次序線索化是在已建立好的二叉鏈表之上(每個(gè)結(jié)點(diǎn)有5個(gè)域)按中根遍歷的方法在訪問根結(jié)點(diǎn)時(shí)建立線索。 中根次序線索化遞歸算法如下： /*算法描述6.7 中根次序線索化遞歸算法*/void inthread(struct xtreenode *p) if (p!=NULL)inthread(p-lch);第47頁，共91頁。 printf (%6ct,p-data); if(p-lch!=NULL)p-ltag=0; elsep-ltag=1; p-lch=pr; /*建p結(jié)點(diǎn)的左線索，指向前驅(qū)結(jié)點(diǎn)pr*/ if(pr!=NULL) if(pr

24、-rch!=NULL) pr-rtag=0; else pr-rtag=1; pr-rch=p; /*前驅(qū)結(jié)點(diǎn)pr建右線索，指向結(jié)點(diǎn)p*/ pr=p; /*pr跟上p，以便p向后移動*/ inthread(p-rch);/*inthread*/ 第48頁，共91頁。 此算法中pr是全局變量，在主程序中置初值為空。在inthread函數(shù)中pr 始終作為當(dāng)前結(jié)點(diǎn)p的前驅(qū)結(jié)點(diǎn)的指針。在線索化過程中，邊判斷二叉樹的結(jié)點(diǎn)有無左、右孩子，邊給相應(yīng)標(biāo)志域置0或1，邊建立線索。在閱讀此算法時(shí)，將inthread(p-lch )和inthread(p-rch)之間的一組語句看成一個(gè)整體，把這段語句理解為“訪問”

25、，很明顯這里應(yīng)用了典型的中根遍歷算法思路。在遞歸調(diào)用結(jié)束時(shí)p為空，這表明pr已是最后一個(gè)結(jié)點(diǎn)，應(yīng)該沒有后繼結(jié)點(diǎn)。所以在返回主程序后還要使pr-rch=NULL，至此整個(gè)線索化結(jié)束。主函數(shù)語句示意如下： 第49頁，共91頁。main() pr=NULL; /*全局變量*/ t=creat(); /*建立二叉樹*/ inthread(t); /*中根線索化二叉樹*/ pr-rch=NULL； /*善后處理*/ 第50頁，共91頁。 初學(xué)者在這里往往易犯錯(cuò)誤，常把預(yù)處理pr=NULL和善后處理pr-rch=NULL放在線索化子函數(shù)void inthread (struct xtreenode * p

26、 )中，一個(gè)放最前面，另一個(gè)放最后面。這樣每遞歸調(diào)用一次，pr就置一次空，無法記下p的前驅(qū)結(jié)點(diǎn)。而在從深度遞歸返回時(shí)，每返回一次就讓pr-rch置一次空，這顯然是錯(cuò)誤的。因此，在描述遞歸算法時(shí)，提倡同時(shí)寫出主函數(shù)來示意遞歸調(diào)用前的初始化處理和遞歸調(diào)用結(jié)束后的善后處理。 第51頁，共91頁。6.5.4 在中根線索樹上檢索某結(jié)點(diǎn)的前驅(qū)或后繼 1. 已知q結(jié)點(diǎn)找出它的前驅(qū)結(jié)點(diǎn) 根據(jù)線索樹的基本概念，當(dāng)q-ltag=1時(shí)，q-lch就指向q的前驅(qū)。當(dāng)q-ltag=0時(shí)，表明q有左孩子。由中根遍歷的規(guī)律可知，作為根q的前驅(qū)結(jié)點(diǎn)(或者說以根結(jié)點(diǎn)為后繼的結(jié)點(diǎn))，它應(yīng)是中根遍歷q的左子樹時(shí)訪問的最后一個(gè)結(jié)點(diǎn)，

27、即左子樹的最右尾結(jié)點(diǎn)。圖6.13(b)中，結(jié)點(diǎn)D是A的左子樹的最右尾結(jié)點(diǎn)，它就是A的前驅(qū)結(jié)點(diǎn)。而D的后繼指針指向了A，A就是D的后繼結(jié)點(diǎn)。若用p記錄q的前趨，則算法如下： 第52頁，共91頁。/*算法描述6.8 已知q結(jié)點(diǎn)，找出它的前驅(qū)結(jié)點(diǎn)*/struct xtreenode *inpre(struct xtreenode *q) if(q-ltag=1) p=q-lch; else r=q-lch; while (r-rtag!=1) r=r-rch; p=r; return(p); 第53頁，共91頁。6.6 二叉樹、樹和森林 6.6.1 樹的存儲結(jié)構(gòu) 樹的存儲結(jié)構(gòu)有順序結(jié)構(gòu)和鏈表結(jié)構(gòu)。順

28、序存儲結(jié)構(gòu)即向量，一般將樹結(jié)點(diǎn)按自上而下、自左至右的順序一一存放。如前文所介紹的完全二叉樹就可以采用順序存儲結(jié)構(gòu)。對于一般樹結(jié)構(gòu)更適合使用鏈表存儲結(jié)構(gòu)。常用的有結(jié)點(diǎn)定長的雙親鏈表發(fā)、多叉鏈表和孩子兄弟二叉鏈表。 第54頁，共91頁。 圖6.14所示的樹是一個(gè)三叉樹，可用三重鏈表來存儲，其結(jié)點(diǎn)結(jié)構(gòu)為：有一個(gè)數(shù)據(jù)域和三個(gè)指針域，指針域用于指向該結(jié)點(diǎn)的各個(gè)孩子。該樹的三重鏈表如圖6.15(a)所示。如果用孩子兄弟鏈表作存儲結(jié)構(gòu)，其結(jié)點(diǎn)結(jié)構(gòu)為：有一個(gè)數(shù)據(jù)域和兩個(gè)指針域，一個(gè)指針指向它的長子，另一指針指向它的一個(gè)兄弟。孩子兄弟鏈表如圖6.15(b)所示。 第55頁，共91頁。圖6.14 樹 第56頁，共

29、91頁。圖6.15 樹的存儲結(jié)構(gòu)(a) 多重鏈表；(b) 孩子-兄弟鏈表 第57頁，共91頁。6.6.2 樹與二叉樹之間的轉(zhuǎn)換 對于一般樹，樹中孩子的次序并不重要，只要雙親與孩子的關(guān)系正確即可。但在二叉樹中，左、右孩子的次序是嚴(yán)格區(qū)分的。所以在討論二叉樹與一般樹之間的轉(zhuǎn)換時(shí)，為了不引起混淆，就約定按樹上現(xiàn)有結(jié)點(diǎn)次序進(jìn)行轉(zhuǎn)換。 第58頁，共91頁。 1. 一般樹轉(zhuǎn)化為二叉樹 將一般樹轉(zhuǎn)化為二叉樹的思路，主要根據(jù)樹的孩子兄弟存儲方式而來，步驟是： (1) 加線：在各兄弟結(jié)點(diǎn)之間用虛線相連。可理解為每個(gè)結(jié)點(diǎn)的兄弟指針指向它的一個(gè)兄弟。 (2) 抹線：對每個(gè)結(jié)點(diǎn)僅保留它與其最左一個(gè)孩子的連線，抹去該結(jié)

30、點(diǎn)與其它孩子之間的連線?？衫斫鉃槊總€(gè)結(jié)點(diǎn)僅有一個(gè)孩子指針，讓它指向自己的長子。 (3) 旋轉(zhuǎn)：把虛線改為實(shí)線從水平方向向下旋轉(zhuǎn)45，成右斜下方向。原樹中實(shí)線成左斜下方向。這樣就形成一棵二叉樹。 第59頁，共91頁。 由于二叉樹中各結(jié)點(diǎn)的右孩子都是原一般樹中該結(jié)點(diǎn)的兄弟，而一般樹的根結(jié)點(diǎn)又沒有兄弟結(jié)點(diǎn)，因此所生成的二叉樹的根結(jié)點(diǎn)沒有右子樹。在所生成的二叉樹中某一結(jié)點(diǎn)的左孩子仍是原來樹中該結(jié)點(diǎn)的長子，并且是它的最左孩子。圖6.16是一個(gè)由一般樹轉(zhuǎn)為二叉樹的實(shí)例。 第60頁，共91頁。圖6.16 一般樹轉(zhuǎn)換為二叉樹(a) 一般樹；(b) 加線；(c) 抹線；(d) 旋轉(zhuǎn)整理 第61頁，共91頁。 2

31、. 二叉樹還原為一般樹 二叉樹還原為一般樹時(shí)，二叉樹必須是由某一樹轉(zhuǎn)換而來的且沒有右子樹。并非任意一棵二叉樹都能還原成一般樹。其還原過程也分為三步： (1) 加線：若某結(jié)點(diǎn)i是雙親結(jié)點(diǎn)的左孩子，則將該結(jié)點(diǎn)i的右孩子以及當(dāng)且僅當(dāng)連續(xù)地沿著右孩子的右鏈不斷搜索到所有右孩子都分別與結(jié)點(diǎn)i的雙親結(jié)點(diǎn)用虛線連接。 (2) 抹線：把原二叉樹中所有雙親結(jié)點(diǎn)與其右孩子的連線抹去。這里的右孩子實(shí)質(zhì)上是原一般樹中結(jié)點(diǎn)的兄弟，抹去的連線是兄弟間的關(guān)系。 (3) 整理：把虛線改為實(shí)線，把結(jié)點(diǎn)按層次排列。 第62頁，共91頁。圖6.17 二叉樹還原為一般樹(a) 二叉樹；(b) 還原加線；(c) 還原抹線；(d) 還原

32、整理 第63頁，共91頁。6.6.3 森林與二叉樹之間的轉(zhuǎn)換 圖6.18 森林轉(zhuǎn)換為二叉樹第64頁，共91頁。 1. 森林轉(zhuǎn)換為二叉樹 森林轉(zhuǎn)換為二叉樹的步驟為： (1) 將森林中每棵子樹轉(zhuǎn)換成相應(yīng)的二叉樹，形成有若干二叉樹的森林。 (2) 按森林圖形中樹的先后次序，依次將后邊一棵二叉樹作為前邊一棵二叉樹根結(jié)點(diǎn)的右子樹，這樣整個(gè)森林就生成了一棵二叉樹，實(shí)際上第一棵樹的根結(jié)點(diǎn)便是生成后的二叉樹的根結(jié)點(diǎn)。圖6.18是森林轉(zhuǎn)化為二叉樹的示例。 第65頁，共91頁。 2. 二叉樹還原為森林 將一棵由森林轉(zhuǎn)換得到的二叉樹還原為森林的步驟是： (1) 抹線：將二叉樹的根結(jié)點(diǎn)與其右孩子的連線以及當(dāng)且僅當(dāng)連續(xù)

33、地沿著右鏈不斷地搜索到的所有右孩子的連線全部抹去，這樣就得到包含有若干棵二叉樹的森林。 (2) 還原：將每棵二叉樹按二叉樹還原為一般樹的方法還原為一般樹，于是得到森林。 這部分的圖示，請讀者自己練習(xí)畫出。 第66頁，共91頁。6.7.2 哈夫曼樹及其應(yīng)用 哈夫曼(Huffman)樹，又稱最優(yōu)二叉樹，是一類帶權(quán)路徑長度最短的樹，有著廣泛的應(yīng)用。 1. 哈夫曼樹的基本概念 首先我們要學(xué)習(xí)一些與哈夫曼樹有關(guān)的術(shù)語。 兩個(gè)結(jié)點(diǎn)之間的路徑長度：樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支數(shù)目。 樹的路徑長度：從根結(jié)點(diǎn)到每個(gè)結(jié)點(diǎn)的路徑長度之和。 第67頁，共91頁。 樹的帶權(quán)路徑長度：設(shè)一棵二叉樹有n個(gè)葉子，每個(gè)葉

34、子結(jié)點(diǎn)擁有一個(gè)權(quán)值W1，W2，Wn，從根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)的路徑長度分別為L1，L2，Ln，那么樹的帶權(quán)路徑長度為每個(gè)葉子的路徑長度與該葉子權(quán)值乘積之和，通常記作： 第68頁，共91頁。 為了直觀起見，在圖6.21中，把帶權(quán)的葉子結(jié)點(diǎn)畫成方形，其它非葉子結(jié)點(diǎn)仍為圓形。請看圖6.21中的三棵二叉樹以及它們的帶權(quán)路徑長度。 (a) WPL=22+42+52+82=38 (b) WPL=42+53+83+21=49 (c) WPL=81+52+43+23=36 注意: 這三棵二叉樹葉子結(jié)點(diǎn)數(shù)相同，它們的權(quán)值也相同，但是它們的WPL帶權(quán)路徑長各不相同。圖6.21(c)所示二叉樹的WPL最小。它就是哈夫

35、曼樹，最優(yōu)樹。 第69頁，共91頁。 哈夫曼樹：在具有同一組權(quán)值的葉子結(jié)點(diǎn)的不同二叉樹中，帶權(quán)路徑長度最短的樹。 圖6.21 具有不同帶權(quán)路徑長度的二叉樹(a) WPL=38；(b) WPL=49；(c) WPL=36 第70頁，共91頁。 2. 哈夫曼樹的構(gòu)造及其算法 1) 構(gòu)造哈夫曼樹的方法 對于已知的一組葉子的權(quán)值W1，W2，Wn： (1) 首先把n個(gè)葉子結(jié)點(diǎn)看作n棵樹(有一個(gè)結(jié)點(diǎn)的二叉樹)，把它們看作一個(gè)森林。 (2) 在森林中把權(quán)值最小和次小的兩棵樹合并成一棵樹，該樹根結(jié)點(diǎn)的權(quán)值是兩棵子樹權(quán)值之和。這時(shí)森林中還有n1棵樹。 (3) 重復(fù)第(2)步直到森林中只有一棵樹為止。(此樹就是哈

36、夫曼樹。) 第71頁，共91頁。圖6.22 哈夫曼樹構(gòu)造過程森林中有四棵樹；(b) 森林中有三棵樹；(c) 森林中有兩棵樹；(d) 生成一棵樹 第72頁，共91頁。 3哈夫曼樹的應(yīng)用在通信及數(shù)據(jù)傳輸中多采用二進(jìn)制編碼，即由0、1組成的字符串。接收方收到一系列0、1串后，再把它還原成文字，即譯碼。 例如：需傳送的電文為“ACDACAB”，其間只用到了四個(gè)字符，則只需兩個(gè)字符的串便足以分辨。令A(yù)、B、C、D的編碼分別為00、01、10、11，則電文的二進(jìn)制代碼串為00101100100001，總碼長14位。接收方按兩位一組進(jìn)行分割，便可譯碼。 第73頁，共91頁。 但是，在傳送電文時(shí)，總希望總碼長

37、盡可能的短。如果對每個(gè)字符設(shè)計(jì)長度不等的編碼，且讓電文中出現(xiàn)次數(shù)較多的字符采用盡可能短的編碼，則傳送電文的總長便可減少。上例電文中A和C出現(xiàn)的次數(shù)較多，我們可以再設(shè)計(jì)一種編碼方案，即A、B、C、D的編碼分別為0、01、1、11，此時(shí)，電文“ACDACAB”的二進(jìn)制代碼串為011101001，總碼長9位，顯然縮短了。 但是，接收方收到該代碼串后無法進(jìn)行譯碼。比如代碼串的“01”是代表B還是代表AC呢？因此，若要設(shè)計(jì)長度不等的編碼，必須是任一個(gè)字符的編碼都不是另一個(gè)字符的編碼的前綴，這個(gè)編碼稱為前綴編碼。電話號碼就是前綴碼，例如110是報(bào)警電話的號碼，其他的電話號碼就不能以110開頭了。 第74頁

38、，共91頁。 利用哈夫曼樹不僅能構(gòu)造出前綴碼，而且還能使電文編碼的總長度最短。方法如下： 假定電文中共用了n種字符，每種字符在電文中出現(xiàn)的次數(shù)為Wi(i=1，2，n)。以Wi作為哈夫曼樹葉子結(jié)點(diǎn)的權(quán)值，用我們前面所介紹的哈夫曼算法構(gòu)造出哈夫曼樹，然后將每個(gè)結(jié)點(diǎn)的左分支標(biāo)上“0”，右分支標(biāo)上“1”，則從根結(jié)點(diǎn)到代表該字符的葉子結(jié)點(diǎn)之間，沿途路徑上的分支號組成的代碼串就是該字符的編碼。 第75頁，共91頁。 例如，在電文“ACDACAB”中，A、B、C、D四個(gè)字符出現(xiàn)的次數(shù)為3、1、2、1，則按上述方法可得到各字符的哈夫曼編碼：A(0)，B(110)，C(10)，D(111)，見圖6.25。 信息

39、編碼是一個(gè)復(fù)雜的問題，還應(yīng)考慮其他一些因素。比如譯碼時(shí)較困難，還有檢測、糾正等問題，都應(yīng)考慮在內(nèi)。這里僅對哈夫曼樹舉了一個(gè)應(yīng)用實(shí)例。 第76頁，共91頁。圖6.25 哈夫曼編碼 第77頁，共91頁。6.8 實(shí)習(xí)：二叉樹的建立和遍歷 二叉樹的建立和遍歷C語言源程序示例如下：#include stdio.h#include stdib.h#define ELEMTP int;struct node ELEMTP data; struct node *lc, *rc; struct node *root; /*根結(jié)點(diǎn)指針root定義為全局變量*/ int m=0; /*統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)，初值置零*/

40、第78頁，共91頁。main() int cord;struct node *creat();void preorderz(struct node *t); /*參數(shù)必須與下邊函數(shù)說明一致*/void inorder(struct node *t);void postorder(struct node *t);do printf(n 主菜單 n)；printf( 1 建立二叉樹 n)；printf( 2 先根非遞歸遍歷 n)；printf( 3 中根遞歸遍歷 n)；printf( 4 后根遞歸遍歷，求葉子結(jié)點(diǎn)數(shù) n)； printf( 5 結(jié)束程序運(yùn)行 n)； 第79頁，共91頁。printf

41、(-n)；printf(請輸入您的選擇(1，2，3，4) ); scanf(%d,&cord);switch (cord)case 1: root=creat(); /*建立二叉樹*/ printf(建立二叉樹程序已執(zhí)行完n); printf(請返回主菜單，用遍歷算法驗(yàn)證程序的正確性n); break; case 2: preorderz(root); printf(先根非遞歸遍歷程序已執(zhí)行完n); break; 第80頁，共91頁。case 3: inorder(root); printf(n中根遍歷二叉樹程序已執(zhí)行完n); break; case 4: postorder(root); printf(n后根遍歷二叉樹程序已執(zhí)行完n); printf(葉子結(jié)點(diǎn)數(shù)m=%3dn,m;) case 5: printf(二叉樹程序執(zhí)行完，再見! n); exit(0); /*switch*/ while(corddata=x; q-lch=NULL;q-rch=NULL; si=q; if(i=1)t=q; /*t代表樹根結(jié)點(diǎn)*/ elsej=i/2; /*雙親結(jié)點(diǎn)編號*/ 第82頁，共91