《哈夫曼樹及其應(yīng)用.ppt》由會員分享，可在線閱讀，更多相關(guān)《哈夫曼樹及其應(yīng)用.ppt（112頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第6章 樹和二叉樹,6.1 樹的概念與定義 6.2 二叉樹 6.3 二叉樹的遍歷與線索化 6.4 樹、森林和二叉樹的關(guān)系 6.5 哈夫曼樹及其應(yīng)用 6.6 樹的計數(shù),整理發(fā)布,6.1 樹的概念與定義,樹是n（n0）個結(jié)點的有限集合T。當(dāng)n=0時，稱為空樹；當(dāng)n0時，該集合滿足如下條件：,(1) 其中必有一個稱為根（root）的特定結(jié)點，它沒有直接前驅(qū)，但有零個或多個直接后繼。,(2) 其余n-1個結(jié)點可以劃分成m（m0）個互不相交的有限集T1，T2，T3，Tm，其中Ti又是一棵樹，稱為根root的子樹。每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但有零個或多個直接后繼。,例如：,其中：A是根；其余結(jié)

2、點分成三個互不相交的子集， T1=B,E,F,K,L； T2=C,G； T3=D,H,I,J,M, T1,T2,T3都是根A的子樹，且本身也是一棵樹,1. 樹型表示法 2. 嵌套集合表示法,3. 廣義表表示法 (A(B(D),C),3. 凹入表示法,樹的表示法,樹的基本術(shù)語,1層,2層,4層,3層,height = 4,A,C,G,B,D,E,F,K,L,H,M,I,J,結(jié)點 結(jié)點的度 葉結(jié)點 分支結(jié)點,子女 雙親 兄弟,祖先 子孫 結(jié)點層次,樹的深度 樹的度 森林,有關(guān)樹的一些術(shù)語：,結(jié)點：包含一個數(shù)據(jù)元素及若干指向其它結(jié)點的分支信息。,結(jié)點的度：一個結(jié)點的子樹個數(shù)稱為此結(jié)點的度。,葉結(jié)點：

3、度為0的結(jié)點，即無后繼的結(jié)點，也稱為終端結(jié)點。,分支結(jié)點：度不為0的結(jié)點，也稱為非終端結(jié)點。,孩子結(jié)點：一個結(jié)點的直接后繼稱為該結(jié)點的孩子結(jié)點。如上圖的B、C、D是A的孩子。,雙親結(jié)點：一個結(jié)點的直接前驅(qū)稱為該結(jié)點的雙親結(jié)點。上圖中A是B、C、D的雙親。,兄弟結(jié)點：同一雙親結(jié)點的孩子結(jié)點之間互稱兄弟結(jié)點。上圖中的結(jié)點H、I、J互為兄弟結(jié)點。,祖先結(jié)點：一個結(jié)點的祖先結(jié)點是指從根結(jié)點到該結(jié)點的路徑上的所有結(jié)點。如結(jié)點K的祖先結(jié)點是A、B、E。,子孫結(jié)點：一個結(jié)點的直接后繼和間接后繼稱為該結(jié)點的子孫結(jié)點。如結(jié)點D的子孫是H、I、J、M。,樹的度：樹中所有結(jié)點的度的最大值。,堂兄弟結(jié)點：其雙親在同一

4、層的結(jié)點。如結(jié)點G與結(jié)點E、F、H、I、J互為堂兄弟。,結(jié)點的層次：從根結(jié)點開始定義，根結(jié)點的層次為1，根的直接后繼的層次為2，依此類推。,樹的高度（深度）：樹中所有結(jié)點的層次的最大值。,有序樹：在樹T中，如果各子樹Ti之間是有先后次序的，則稱為有序樹。,森林：m（m0）棵互不相交的樹的集合。將一棵非空樹的根結(jié)點刪去，樹就變成一個森林；反之，給森林增加一個統(tǒng)一的根結(jié)點，森林就變成一棵樹。,樹的抽象數(shù)據(jù)類型定義：,數(shù)據(jù)對象D：一個集合，該集合中的所有元素具有相同的特性。,數(shù)據(jù)關(guān)系R：若D為空集，則為空樹。若D中僅含有一個數(shù)據(jù)元素，則R為空集，否則R=H，H是如下的二元關(guān)系：,(1) 在D中存在唯

5、一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下沒有前驅(qū)。,(2) 除root以外，D中每個結(jié)點在關(guān)系H下都有且僅有一個前驅(qū)。,基本操作：,InitTree（Tree）： 將Tree初始化為一棵空樹。 (2) DestoryTree（Tree）： 銷毀樹Tree。 (3) CreateTree（Tree）： 創(chuàng)建樹Tree。 (4) TreeEmpty（Tree）： 若Tree為空，則返回TRUE，否則返回FALSE。 (5) Root（Tree）： 返回樹Tree的根。 (6) Parent（Tree，x）： 樹Tree存在，x是Tree中的某個結(jié)點。若x為非根結(jié)點，則返回它的雙親，否則返回“空”

6、。,(7) FirstChild（Tree，x）： 樹Tree存在，x是Tree中的某個結(jié)點。若x為非葉子結(jié)點，則返回它的第一個孩子結(jié)點，否則返回“空”。 (8) NextSibling（Tree，x）： 樹Tree存在，x是Tree中的某個結(jié)點。若x不是其雙親的最后一個孩子結(jié)點，則返回x后面的下一個兄弟結(jié)點，否則返回“空”。 (9) InsertChild（Tree，p，Child）： 樹Tree存在，p指向Tree中某個結(jié)點，非空樹Child與Tree不相交。將Child插入Tree中，做p所指向結(jié)點的子樹。,基本操作:,基本操作:,(10) DeleteChild（Tree，p，i）：

7、樹Tree存在，p指向Tree中某個結(jié)點，1id，d為p所指向結(jié)點的度。刪除Tree中p所指向結(jié)點的第i棵子樹。 (11) TraverseTree（Tree，Visit（）： 樹Tree存在，Visit（）是對結(jié)點進(jìn)行訪問的函數(shù)。按照某種次序?qū)銽ree的每個結(jié)點調(diào)用Visit（）函數(shù)訪問一次且最多一次。若Visit（）失敗，則操作失敗。,6.2 二叉數(shù),6.2.1 二叉樹的定義與基本操作,6.2.2 二叉樹的性質(zhì),6.2.3 二叉樹的存儲結(jié)構(gòu),6.2.1 二叉樹的定義與基本操作,定義：我們把滿足以下兩個條件的樹型結(jié)構(gòu)叫做二叉樹（Binary Tree）： （1）每個結(jié)點的度都不大于2； （

8、2）每個結(jié)點的孩子結(jié)點次序不能任意顛倒。,下面給出二叉樹的五種基本形態(tài)：,二叉樹的基本操作：,Initiate（bt）：將bt初始化為空二叉樹。 (2) Create(bt)：創(chuàng)建一棵非空二叉樹bt。 (3) Destory（bt）： 銷毀二叉樹bt。 (4) Empty（bt）： 若bt為空，則返回TRUE，否則返回FALSE。 (5) Root(bt)： 求二叉樹bt的根結(jié)點。若bt為空二叉樹，則函數(shù)返回“空”。 (6) Parent（bt，x）：求雙親函數(shù)。求二叉樹bt中結(jié)點x的雙親結(jié)點。若結(jié)點x是二叉樹的根結(jié)點或二叉樹bt中無結(jié)點x，則返回“空”。,基本操作：,(7) LeftChil

9、d（bt，x）：求左孩子。若結(jié)點x為葉子結(jié)點或x不在bt中，則返回“空”。 (8) RightChild（bt，x）：求右孩子。若結(jié)點x為葉子結(jié)點或x不在bt中，則返回“空”。 (9) Traverse（bt）: 遍歷操作。按某個次序依次訪問二叉樹中每個結(jié)點一次且僅一次。 (10) Clear（bt）：清除操作。將二叉樹bt置為空樹。,6.2.2 二叉樹的性質(zhì),性質(zhì)1：在二叉樹的第i層上至多有2i-1個結(jié)點(i1)。,當(dāng)i=1時，整個二叉樹只有一根結(jié)點，此時2i-1=20=1，結(jié)論成立。,證明：,假設(shè)i=k時結(jié)論成立，即第k層上結(jié)點總數(shù)最多為2k-1個。,現(xiàn)證明當(dāng)i=k+1時，結(jié)論成立：,因為

10、二叉樹中每個結(jié)點的度最大為2，則第k+1層的結(jié)點總數(shù)最多為第k層上結(jié)點最大數(shù)的2倍，即22k-1=2(k+1)-1，故結(jié)論成立。,性質(zhì)2：深度為k的二叉樹至多有2k-1個結(jié)點（k1）。,證明：,由性質(zhì)1可見，深度為k的二叉樹的最大結(jié)點數(shù)為,故結(jié)論成立。,性質(zhì)3：對任意一棵二叉樹T，若終端結(jié)點數(shù)為n0，而其度數(shù)為2的結(jié)點數(shù)為n2，則n0= n2+1 。,證明：設(shè)二叉樹中結(jié)點總數(shù)為n，n1為二叉樹中度為1的結(jié)點總數(shù)。因為二叉樹中所有結(jié)點的度小于等于2，所以有 n= n0+ n1+n2 設(shè)二叉樹中分支數(shù)目為B，因為除根結(jié)點外，每個結(jié)點均對應(yīng)一個進(jìn)入它的分支，所以有：n=B+1。 又因為二叉樹中的分支

11、都是由度為1和度為2的結(jié)點發(fā)出，所以分支數(shù)目為：B=n1+2n2 整理上述兩式可得到：n=B+1=n1+2n2+1 將n= n0+ n1+n2代入上式得出n0+ n1+n2=n1+2n2+1，整理后得n0= n2+1，故結(jié)論成立。,兩種特殊的二叉樹：,定義1：滿二叉樹(Full Binary Tree) 深度為k且有2k-1個結(jié)點的二叉樹。在滿二叉樹中，每層結(jié)點都是滿的，即每層結(jié)點都具有最大結(jié)點數(shù)。,滿二叉樹,定義2：完全二叉樹：,關(guān)系：滿二叉樹必為完全二叉樹，而完全二叉樹不一定是滿二叉樹。,若設(shè)二叉樹的高度為h，則共有h層。除第 h 層外，其它各層 (0 h-1) 的結(jié)點數(shù)都達(dá)到最大個數(shù)，第

12、 h 層從右向左連續(xù)缺若干結(jié)點，這就是完全二叉樹。,非完全二叉樹,性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為2n+1。,證明：設(shè)n個結(jié)點的完全二叉樹的深度為k，根據(jù)性質(zhì)2可知，k-1層滿二叉樹的結(jié)點總數(shù)為： 2k-1-1 k層滿二叉樹的結(jié)點總數(shù)為： 2k-1 顯然有： 2k-1 - 1 n 2k- 1 2k- 1 n 2k 取對數(shù)有：k -1 log2n k 因為k是整數(shù)，所以k -1 =log2n ， k= 2n+1 結(jié)論成立。,性質(zhì)5：對于具有n個結(jié)點的完全二叉樹，如果按照從上到下和從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點從1開始順序編號，則對于任意的序號為i的結(jié)點有：,(1)若i = 1, 則

13、i 無雙親結(jié)點 若i 1, 則 i 的雙親結(jié)點為i /2 (2)若2*i n, 則 i 無左孩子 若2*in, 則 i 結(jié)點的左孩子結(jié)點為2*i (3)若 2*i+1 n ,則i 無右孩子 若 2*i+1n, 則i的右孩子結(jié)點為2* i+1,用歸納法證明其中的(2)和(3)。,6.2.3 二叉樹的存儲結(jié)構(gòu),二叉樹的結(jié)構(gòu)是非線性的，每一結(jié)點最多可有兩個后繼。,二叉樹的存儲結(jié)構(gòu)有兩種：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。,完全二叉樹 一般二叉樹 的順序表示 的順序表示,二叉樹的存儲結(jié)構(gòu),1 2 3 4 5 6 7 8 910,9,1 2 3 4 0 5 6 7 8 0 0 910,1,2,3,6,5,4,

14、7,8,順序表示,9,10,對于一般的二叉樹，我們必須按照完全二叉樹的形式來存儲，就會造成空間的浪費。單支樹就是一個極端情況。,單支樹,鏈表表示,二叉鏈表,含兩個指針域的結(jié)點結(jié)構(gòu),lChild data parent rChild,含三個指針域的結(jié)點結(jié)構(gòu),三叉鏈表,二叉樹鏈表表示的示例,A,A,A,B,B,B,C,C,C,D,D,D,F,F,F,E,E,E,root,root,root,二叉樹 二叉鏈表 三叉鏈表,有時，為了找到父結(jié)點，可以增加一個Parent域，Parent域指向該結(jié)點的父結(jié)點。該結(jié)點結(jié)構(gòu)如下：,typedef struct Node DataType data; strct

15、 Node * LChild; struct Node * RChild; BiTNode, *BiTree;,二叉樹的二叉鏈表結(jié)點的結(jié)構(gòu)用C語言描述為 ：,結(jié)論：若一個二叉樹含有n個結(jié)點，則它的二叉鏈表中必含有2n個指針域，其中必有n1個空的鏈域。,證明結(jié)論：,分支數(shù)目B=n-1，即非空的鏈域有n-1個，故空鏈域有2n-(n-1)=n+1個。,6.3 二叉樹的遍歷與線索化,二叉樹的遍歷：指按一定規(guī)律對二叉樹中的每個結(jié)點進(jìn)行訪問且僅訪問一次。,二叉樹的基本結(jié)構(gòu)由根結(jié)點、左子樹和右子樹組成,如圖示,用L、D、R分別表示遍歷左子樹、訪問根結(jié)點、遍歷右子樹，那么對二叉樹的遍歷順序就可以有：,訪問根，

16、遍歷左子樹，遍歷右子樹(記做DLR)。 訪問根，遍歷右子樹，遍歷左子樹(記做DRL)。 遍歷左子樹，訪問根，遍歷右子樹(記做LDR)。 遍歷左子樹，遍歷右子樹，訪問根 (記做LRD)。 遍歷右子樹，訪問根，遍歷左子樹 (記做RDL)。 遍歷右子樹，遍歷左子樹，訪問根 (記做RLD)。,在以上六種遍歷方式中，如果我們規(guī)定按先左后右的順序，那么就只剩有 DLR 、LDR 和LRD三種。根據(jù)對根的訪問先后順序不同，分別稱DLR為先序遍歷或先根遍歷；LDR為中序遍歷（對稱遍歷）；LRD為后序遍歷。,注意：先序、中序、后序遍歷是遞歸定義的，即在其子樹中亦按上述規(guī)律進(jìn)行遍歷。,三種遍歷方法的遞歸定義：,先

17、序遍歷（DLR）操作過程：,若二叉樹為空，則空操作，否則依次執(zhí)行如下操作： （1）訪問根結(jié)點； （2）按先序遍歷左子樹； （3）按先序遍歷右子樹。,若二叉樹為空，則空操作，否則依次執(zhí)行如下操作： （1）按中序遍歷左子樹； （2）訪問根結(jié)點； （3）按中序遍歷右子樹。,中序遍歷（LDR）操作過程,后序遍歷（LRD）操作過程：,若二叉樹為空，則空操作，否則依次執(zhí)行如下操作： （1）按后序遍歷左子樹； （2）按后序遍歷右子樹； （3）訪問根結(jié)點。,對于如下圖的二叉樹，其先序、中序、后序遍歷的序列為： 先序遍歷： A、B、D、F、G、C、E、H 。 中序遍歷： B、F、D、G、A、C、E、H 。 后序

18、遍歷： F、G、D、B、H、E、C、A 。,以二叉鏈表作為存儲結(jié)構(gòu)，討論二叉樹的遍歷算法,1) 先序遍歷,void PreOrder(BiTree root) /*先序遍歷二叉樹, root為指向二叉樹(或某一子樹)根結(jié)點的指針*/ if (root!=NULL) Visit(root -data); /*訪問根結(jié)點*/ PreOrder(root -LChild); /*先序遍歷左子樹*/ PreOrder(root -RChild); /*先序遍歷右子樹*/ ,2) 中序遍歷,void InOrder(BiTree root) /*中序遍歷二叉樹, root為指向二叉樹(或某一子樹)根結(jié)點

19、的指針*/ if (root!=NULL) InOrder(root -LChild); /*中序遍歷左子樹*/ Visit(root -data); /*訪問根結(jié)點*/ InOrder(root -RChild); /*中序遍歷右子樹*/ ,3) 后序遍歷,void PostOrder(BiTree root) /* 后序遍歷二叉樹，root為指向二叉樹(或某一子樹)根結(jié)點的指針*/ if(root!=NULL) PostOrder(root -LChild); /*后序遍歷左子樹*/ PostOrder(root -RChild); /*后序遍歷右子樹* Visit(root -data)

20、; /*訪問根結(jié)點*/ ,以中序遍歷為例來說明中序遍歷二叉樹的遞歸過程,A,B,D,C,E,第一次經(jīng)過,第二次經(jīng)過,第三次經(jīng)過,6.3.2 基于棧的遞歸消除,1) 中序遍歷二叉樹的非遞歸算法,首先應(yīng)用遞歸進(jìn)層的三件事與遞歸退層的三件事的原則,直接先給出中序遍歷二叉樹的非遞歸算法基本實現(xiàn)思路。,中序遍歷二叉樹的非遞歸算法初步如下：,在大量復(fù)雜的情況下，遞歸的問題無法直接轉(zhuǎn)換成循環(huán)，需要采用工作棧消除遞歸。工作棧提供一種控制結(jié)構(gòu)，當(dāng)遞歸算法進(jìn)層時需要將信息保留；當(dāng)遞歸算法出層時需要從棧區(qū)退出信息。,中序遍歷二叉樹的非遞歸算法（直接實現(xiàn)棧操作）,/*sm表示棧，top表示棧頂指針*/ Void in

21、order(BiTree root) /*中序遍歷二叉樹，bt為二叉樹的根結(jié)點*/ top=0;p=bt do while(p!=NULL) if (topm) return(overflow); top=top+1; stop=p; p=p-Lchild; /*遍歷左子樹*/ if(top!=0), p=stop; top=top-1; Visit(p-data); /*訪問根結(jié)點*/ p=p-Rchild; /*遍歷右子樹*/ while(p!=NULL|top!=0) ,中序遍歷二叉樹的非遞歸算法（調(diào)用棧操作的函數(shù)）,void InOrder（BiTree root）/* 中序遍歷二叉樹

22、的非遞歸算法 */ InitStack ( ,2) 后序遍歷的二叉樹的非遞歸算法,void PostOrder（BiTree root） BiTNode * p,*q； BiTNode *S； int top=0; q=NULL; p=root; S=（BiTNode*）malloc（sizeof（BiTNode*）*NUM）; /* NUM為預(yù)定義的常數(shù) */ while(p!=NULL | top!=0) while(p!=NULL) top=+; stop=p; p=p-LChild; /* 左子樹遍歷 */ if(top0), p=stop; if(p-RChild=NULL) |(p

23、-RChild=q) /* 無右孩子，或右孩子已遍歷過 */ visit(p-data); /* 訪問根結(jié)點* / q=p; /* 保存到q，為下一次已處理結(jié)點前驅(qū) */ top-; p=NULL; else p=p-RChild; free(s); ,6.3.3 遍歷算法應(yīng)用,二叉樹的遍歷運算是一個重要的基礎(chǔ)。在實際應(yīng)用中，一是重點理解訪問根結(jié)點操作的含義，二是注意對具體的實現(xiàn)問題是否需要考慮遍歷的次序問題。,1. 輸出二叉樹中的結(jié)點,遍歷算法將走遍二叉樹中的每一個結(jié)點，故輸出二叉樹中結(jié)點并無次序要求，因此可用任一種算法來完成。,先序遍歷輸出二叉樹中的結(jié)點,void PreOrder(BiT

24、ree root) /* 先序遍歷輸出二叉樹結(jié)點, root為指向二叉樹根結(jié)點的指針 */ if (root!=NULL) printf (root -data); /* 輸出根結(jié)點 */ PreOrder(root -LChild); /* 先序遍歷左子樹 */ PreOrder(root -RChild); /* 先序遍歷右子樹 */ ,問題思考：若要求統(tǒng)計二叉樹中結(jié)點個數(shù)應(yīng)如何去實現(xiàn)？,2. 輸出二叉樹中的葉子結(jié)點,條件：判斷結(jié)點既沒有左孩子，又沒有右孩子時，則輸出該結(jié)點。,void PreOrder(BiTree root) /* 先序遍歷輸出二叉樹中葉結(jié)點 , root為指向二叉樹根

25、結(jié)點的指針 */ if (root!=NULL) if (root -LChild=NULL /* 先序遍歷右子樹 */ ,3. 統(tǒng)計葉子結(jié)點數(shù)目,/* LeafCount保存葉子結(jié)點數(shù)目的全局變量,調(diào)用之前初始化值為0 */ void leaf(BiTree root) if(root!=NULL) leaf(root-LChild); leaf(root-RChild); if (root -LChild=NULL ,方法一：,int leaf(BiTree root) int LeafCount; if(root=NULL) LeafCount =0; else if(root-LChi

26、ld=NULL) ,方法二,/* 采用遞歸算法，如果是空樹，返回0；如果只有一個結(jié)點， 返回1；否則為左右子樹的葉子結(jié)點數(shù)之和 */,4. 建立二叉鏈表方式存儲的二叉樹,給定一棵二叉樹，可以得到它的遍歷序列；反過來，給定一個遍歷序列，也可以創(chuàng)建相應(yīng)的二叉鏈表。在這里所說的遍歷序列是一種“擴(kuò)展的遍歷序列”，通常用特定的元素表示空子樹。例如：,右圖中的二叉樹的“擴(kuò)展的遍歷序列”為：,AB.DF.G.C.E.H.,其中用小圓點表示空子樹,利用“擴(kuò)展先序遍歷序列”創(chuàng)建二叉鏈表的算法為：,void CreateBiTree(BiTree *bt) char ch; ch=getchar(); if(ch

27、=.) *bt=NULL; else *bt=(BiTree)malloc(sizeof(BiTNode); (*bt)-data=ch; CreateBiTree( ,5. 求二叉樹的高度,設(shè)函數(shù)表示二叉樹bt的高度，則遞歸定義如下: 若bt為空，則高度為0 若bt非空，其高度應(yīng)為其左右子樹高度的最大值加1,左 子 樹,右 子 樹,bt,hl,hr,High=max(hl+hr)+1,后序遍歷求二叉樹的高度遞歸算法：,int PostTreeDepth(BiTree bt) /* 后序遍歷求二叉樹的高度遞歸算法 */ int hl,hr,max; if(bt!=NULL) hl=PostTr

28、eeDepth(bt-LChild); /* 求左子樹的深度 */ hr=PostTreeDepth(bt-RChild); /* 求右子樹的深度 */ max=hlhr?hl:hr; /* 得到左、右子樹深度較大者*/ return(max+1); /* 返回樹的深度 */ else return(0); /* 如果是空樹，則返回0 */ ,問題思考： 求二叉樹的深度是否可用先序遍歷的方式實現(xiàn)？若能，請寫出實現(xiàn)算法，若不能，請說明原因。,6. 按樹狀打印的二叉樹,假設(shè)以二叉鏈表存儲的二叉樹中，每個結(jié)點所含數(shù)據(jù)元素均為單字母，要求實現(xiàn)如下圖的打印結(jié)果。,分析：這是二叉樹的橫向顯示問題，橫向顯示

29、應(yīng)是豎向顯示的900旋轉(zhuǎn)，又由于二叉樹的橫向顯示算法一定是中序遍歷算法，所以把橫向顯示的二叉樹算法改為RDL結(jié)構(gòu)，實現(xiàn)算法為：,void PrintTree(TreeNode Root,int nLayer) /* 豎向樹狀打印的二叉樹 */ if(Root= =NULL) return; PrintTree(Root-RChild,nLayer+1); for(int i=0;ich); PrintTree(Root-LChild,nLayer+1); ,6.3.4 線索二叉樹,1. 基本概念,二叉樹的遍歷運算是將二叉樹中結(jié)點按一定規(guī)律線性化的過程。當(dāng)以二叉鏈表作為存儲結(jié)構(gòu)時，只能找到結(jié)點的

30、左、右孩子信息，而不能直接得到結(jié)點在遍歷序列中的前驅(qū)和后繼信息。要得到這些信息，第一種方法是將二叉樹遍歷一遍，在遍歷過程中便可得到結(jié)點的前驅(qū)和后繼，但這種動態(tài)訪問浪費時間；第二種方法是充分利用二叉鏈表中的空鏈域，將遍歷過程中結(jié)點的前驅(qū)、后繼信息保存下來。,在有n個結(jié)點的二叉鏈表中共有2n個鏈域，但只有n-1個有用非空鏈域，其余n+1個鏈域是空的。我們可以利用剩下的n+1個空鏈域來存放遍歷過程中結(jié)點的前驅(qū)和后繼信息。 現(xiàn)作如下規(guī)定：,若結(jié)點有左子樹，則其LChild域指向其左孩子，否則LChild域指向其前驅(qū)結(jié)點；若結(jié)點有右子樹，則其RChild域指向其右孩子，否則RChild域指向其后繼結(jié)點。

31、,為了區(qū)分孩子結(jié)點和前驅(qū)、后繼結(jié)點，為結(jié)點結(jié)構(gòu)增設(shè)兩個標(biāo)志域，如下圖所示：,其中：,線索：在這種存儲結(jié)構(gòu)中，指向前驅(qū)和后繼結(jié)點的指針叫做線索。,線索鏈表：以這種結(jié)構(gòu)組成的二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，叫做線索鏈表。,線索化：對二叉樹以某種次序進(jìn)行遍歷并且加上線索的過程叫做線索化。,線索二叉樹：線索化了的二叉樹稱為線索二叉樹。,2. 二叉樹的線索化,線索化實質(zhì)上是將二叉鏈表中的空指針域填上相應(yīng)結(jié)點的遍歷前驅(qū)或后繼結(jié)點的地址，而前驅(qū)和后繼的地址只能在動態(tài)的遍歷過程中才能得到。因此線索化的過程是在遍歷過程中修改空指針域的過程。 對二叉樹按照不同的遍歷次序進(jìn)行線索化，可以得到不同的線索二叉樹 （先序線

32、索二叉樹、中序線索二叉樹和后序線索二叉樹）。,中序線索化算法：,void Inthread(BiTree root) /* 對root所指的二叉樹進(jìn)行中序線索化，其中pre始終指向剛訪問過的結(jié)點，其初值為NULL* / if (root!=NULL) Inthread(root-LChild); /* 線索化左子樹 */ if (root-LChild=NULL) root-Ltag=1; root-LChile=pre; / *置前驅(qū)線索 */ if (pre!=NULL /*線索化右子樹*/ ,下面是對同一棵二叉樹的遍歷方法不同得到的不同線索樹。,NULL,3. 在線索二叉樹中找前驅(qū)、后繼

33、結(jié)點,1）找結(jié)點的中序前驅(qū)結(jié)點,根據(jù)線索二叉樹的基本概念和存儲結(jié)構(gòu)可知，對于結(jié)點p，當(dāng)p-Ltag=1時，p-LChild指向p的前驅(qū)。,當(dāng)p-Ltag=0時，p-LChild指向p的左孩子。由中序遍歷的規(guī)律可知，作為根p的前驅(qū)結(jié)點，它是中序遍歷p的左子樹時訪問的最后一個結(jié)點，即左子樹的“最右下端”結(jié)點。其查找算法如下：,在中序線索樹中找結(jié)點前驅(qū)算法：,void InPre(BiTNode * p, BiTNode * pre) /* 在中序線索二叉樹中查找p的中序前驅(qū), 并用pre指針返回結(jié)果 */ if(p-Ltag=1) pre= p-LChild; /*直接利用線索*/ else /*

34、 在p的左子樹中查找“最右下端”結(jié)點 */ for(q= p-LChild;q-Rtag=0;q=q-RChild); pre=q; ,2）在中序線索樹中找結(jié)點后繼,對于結(jié)點p，若要找其后繼結(jié)點，當(dāng)p-Rtag=1時，p-RChild即為p的后繼結(jié)點；當(dāng)p-Rtag=0時，說明p有右子樹，此時p的中序后繼結(jié)點即為其右子樹的“最左下端”的結(jié)點。其查找算法如下：,void InSucc(BiTNode * p, BiTNode * succ) /*在中序線索二叉樹中查找p的后繼結(jié)點，并用succ指針返回結(jié)果*/ if (p-Rtag=1) succ= p- RChild; /*直接利用線索*/ e

35、lse /*在p的右子樹中查找“最左下端”結(jié)點*/ for(q= p-RChild; q-Ltag=0 ;q=q-LChild ); succ=q; ,6.4 樹、森林和二叉樹的關(guān)系,討論的重點： 樹的存儲結(jié)構(gòu) 樹、森林與二叉樹的轉(zhuǎn)換關(guān)系,6.4.1 樹的存儲結(jié)構(gòu),樹的主要存儲方法有： 1.雙親表示法 2.孩子表示法 3.孩子兄弟表示法,1. 雙親表示法：用一組連續(xù)的空間來存儲樹中的結(jié)點，在保存每個結(jié)點的同時附設(shè)一個指示器來指示其雙親結(jié)點在表中的位置，其結(jié)點的結(jié)構(gòu)如下：,樹的雙親表示法如下圖：,雙親表示法的優(yōu)點： 利用了樹中每個結(jié)點（根結(jié)點除外）只有一個雙親結(jié)點的性質(zhì)，使得查找某個結(jié)點的雙親結(jié)

36、點非常容易。,雙親表示法的缺點： 在求某個結(jié)點的孩子時，需要遍歷整個向量。,雙親表示法的形式說明如下：,#define MAX 100 typedef struct TNode DataType data; int parent; TNode;,一棵樹可以定義為：,typedef struct TNode treeMAX; int nodenum; /*結(jié)點數(shù)*/ ParentTree;,2. 孩子表示法：通常是把每個結(jié)點的孩子結(jié)點排列起來，構(gòu)成一個單鏈表，稱為孩子鏈表。n個結(jié)點共有n個孩子鏈表（葉結(jié)點的孩子鏈表為空表），而n個結(jié)點的數(shù)據(jù)和n個孩子鏈表的頭指針又組成一個順序表。,樹的孩子鏈表表

37、示法見p137的圖6.14,孩子表示法的形式說明如下：,typedef struct ChildNode /* 孩子鏈表結(jié)點的定義 */ int Child; /* 該孩子結(jié)點在線性表中的位置 */ struct ChildNode * next; /*指向下一個孩子結(jié)點的指針 */ ChildNode; typedef struct /* 順序表結(jié)點的結(jié)構(gòu)定義 */ DataType data; /* 結(jié)點的信息 */ ChildNode * FirstChild ; /* 指向孩子鏈表的頭指針 */ DataNode;,返回主目錄,typedef struct /* 樹的定義 */ Dat

38、aNode nodesMAX; /* 順序表 */ int root,num; /* 該樹的根結(jié)點在線性表中的位置和該樹的結(jié)點個數(shù) */ ChildTree;,返回主目錄,3. 孩子兄弟表示法（二叉鏈表表示法）：鏈表中每個結(jié)點設(shè)有兩個鏈域，分別指向該結(jié)點的第一個孩子結(jié)點和下一個兄弟（右兄弟）結(jié)點。,樹的孩子兄弟表示法見p137的圖6.15,孩子兄弟表示法的類型定義如下：,typedef struct CSNode DataType data; /*結(jié)點信息*/ Struct CSNode *FirstChild, *Nextsibling; /*第一個孩子,下一個兄弟*/ CSNode, *C

39、STree;,優(yōu)點：便于實現(xiàn)樹的各種操作。,6.4.2 樹、森林與二叉樹的相互轉(zhuǎn)換,1. 樹轉(zhuǎn)換為二叉樹,我們約定樹中每一個結(jié)點的孩子結(jié)點按從左到右的次序順序編號，也就是說，把樹作為有序樹看待。,例如：右圖的樹,將一棵樹轉(zhuǎn)換為二叉樹的方法：, 樹中所有相鄰兄弟之間加一條連線。 對樹中的每個結(jié)點，只保留其與第一個孩子結(jié)點之間的連線，刪去其與其它孩子結(jié)點之間的連線。 以樹的根結(jié)點為軸心，將整棵樹順時針旋轉(zhuǎn)一定的角度，使之結(jié)構(gòu)層次分明。,樹轉(zhuǎn)換為二叉樹的轉(zhuǎn)換過程示意見p137圖6.16,結(jié)論：從轉(zhuǎn)換過程可看出：樹中的任意一個結(jié)點都對應(yīng)于二叉樹中的一個結(jié)點。樹中某結(jié)點的第一個孩子在二叉樹中是相應(yīng)結(jié)點的

40、左孩子，樹中某結(jié)點的右兄弟結(jié)點在二叉樹中是相應(yīng)結(jié)點的右孩子。也就是說，在二叉樹中，左分支上的各結(jié)點在原來的樹中是父子關(guān)系，而右分支上的各結(jié)點在原來的樹中是兄弟關(guān)系。由于樹的根結(jié)點沒有兄弟，所以變換后的二叉樹的根結(jié)點的右孩子必然為空。,樹與二叉樹的對應(yīng)關(guān)系及轉(zhuǎn)換方法,見p137的圖6.16所示,2. 森林轉(zhuǎn)換為二叉樹,森林轉(zhuǎn)換為二叉樹的方法為：,（1）將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹。,（2）第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點作為前一棵二叉樹根結(jié)點的右孩子，當(dāng)所有二叉樹連在一起后，所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。,森林轉(zhuǎn)換為二叉樹的過程見p138的圖6.

41、17,用遞歸的方法描述森林轉(zhuǎn)換為二叉樹的過程為：,將森林F看作樹的有序集F=T1，T2，,TN，它對應(yīng)的二叉樹為B（F）：,（1）若N0，則B（F）為空。,（2）若N0，二叉樹B（F）的根為森林中第一棵樹T1的根； B（F）的左子樹為B（T11，T1m），其中T11，T1m是T1的子樹森林；B（F）的右子樹是B（T2，TN）。,3. 二叉樹還原為樹或森林,一棵二叉樹還原為樹或森林，具體方法為：,（1）若某結(jié)點是其雙親的左孩子，則把該結(jié)點的右孩子、右孩子的右孩子、都與該結(jié)點的雙親結(jié)點用線連起來。 （2）刪掉原二叉樹中所有雙親結(jié)點與右孩子結(jié)點的連線。 （3）整理由（1）、（2）兩步所得到的樹或森林

42、，使之結(jié)構(gòu)層次分明。,一棵二叉樹還原為森林的過程示意:,用遞歸的方法描述其轉(zhuǎn)換過程為：,若B是一棵二叉樹，T是B的根結(jié)點，L是B的左子樹，R為B的右子樹，且B對應(yīng)的森林F（B）中含有的n棵樹為T1,T2, ,Tn，則有：,（1）B為空，則F（B）為空的森林（n0）。,（2）B非空，則F（B）中第一棵樹T1的根為二叉樹B的根T；T1中根結(jié)點的子樹森林由B的左子樹L轉(zhuǎn)換而成，即F（L）=T11,T1m；B的右子樹R轉(zhuǎn)換為F（B）中其余樹組成的森林，即F(R) T2, T3, ,Tn。,6.4.3 樹與森林的遍歷,1. 樹的遍歷,樹的遍歷方法主要有以下兩種：,1）先根遍歷,若樹非空，則遍歷方法為：

43、（1）訪問根結(jié)點。 （2）從左到右，依次先根遍歷根結(jié)點的每一棵子樹。,如圖中樹的先根遍歷序列為：ABECFHGD。,2）后根遍歷,若樹非空，則遍歷方法為：,（1）從左到右，依次后根遍歷根結(jié)點的每一棵子樹。 （2）訪問根結(jié)點。,如圖中樹的后根遍歷序列為：EBHFGCDA。,2. 森林的遍歷,森林的遍歷方法主要有以下三種：,1）先序遍歷,若森林非空，則遍歷方法為：,（1）訪問森林中第一棵樹的根結(jié)點。 （2）先序遍歷第一棵樹的根結(jié)點的子樹森林。 （3）先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。,2）中序遍歷,若森林非空，則遍歷方法為：,（1）中序遍歷森林中第一棵樹的根結(jié)點的子樹森林。 （2）訪問第

44、一棵樹的根結(jié)點。 （3）中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。,3）后序遍歷,若森林非空，則遍歷方法為：,（1）后序遍歷森林中第一棵樹的根結(jié)點的子樹森林。 （2）后序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。 （3）訪問第一棵樹的根結(jié)點。,6.5 哈夫曼樹及其應(yīng)用,6.5.1 哈夫曼樹,基本概念：,路徑：指從一個結(jié)點到另一個結(jié)點之間的分支序列。 路徑長度：指從一個結(jié)點到另一個結(jié)點所經(jīng)過的分支數(shù)目。 結(jié)點的權(quán)：給樹的每個結(jié)點賦予一個具有某種實際意義的實數(shù)，我們稱該實數(shù)為這個結(jié)點的權(quán)。,帶權(quán)路徑長度：在樹形結(jié)構(gòu)中，我們把從樹根到某一結(jié)點的路徑長度與該結(jié)點的權(quán)的乘積，叫做該結(jié)點的帶權(quán)路徑長度。,

45、樹的帶權(quán)路徑長度：為樹中所有葉子結(jié)點的帶權(quán)路徑長度之和，通常記為：,其中n為葉子結(jié)點的個數(shù)， wi為第i個葉子結(jié)點的權(quán)值，li為第i個葉子結(jié)點的路徑長度。,例如下圖所示的具有不同帶權(quán)路徑長度的二叉樹,WPL(a)=7252224236 WPL(b)=4273532146 WPL(c)=7152234335,圖例見p144的圖6.22所示,問題1：什么樣的二叉樹的路徑長度WPL最小？,一棵樹的路徑長度為0結(jié)點至多只有1個（根）；路徑長度為1結(jié)點至多只有2個（兩個孩子）；路徑長度為2結(jié)點至多只有4個；以此類推：路徑長度為K結(jié)點至多只有2k個，所以n個結(jié)點二叉樹其路徑長度至少等于如下序列的前n項之和

46、。,路徑長度 0 ，1 ， 1 ，2， 2， 2， 2，3， 3，3，3，3，3，3，3，4，4，. 結(jié)點數(shù)n n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 . K=15,由此可知，結(jié)點n對應(yīng)的路徑長度為 log2n ，所以前n項之和為:,完全二叉樹的路徑長度為：,h為樹的深度，其路徑長度可達(dá)到最小，所以完全二叉樹具有最小路徑長度的性質(zhì)，但不具有唯一性。,例如：下列不同形狀的二叉樹具有最小的路徑長度,問題2：什么樣的樹的帶權(quán)路徑長度最??？,例如：給定一個權(quán)值序列2,3,4,7，可構(gòu)造的多種二叉樹的形態(tài)。,4. 哈夫曼樹,哈夫曼樹又叫最優(yōu)二叉樹，它是由n個帶權(quán)葉子結(jié)點構(gòu)成的所有

47、二叉樹中帶權(quán)路徑長度WPL最短的二叉樹。,構(gòu)造哈夫曼算法的步驟如下：,（1）用給定的n個權(quán)值w1,w2, ,wn對應(yīng)的n個結(jié)點構(gòu)成n棵二叉樹的森林F=T1,T2, ,Tn，其中每一棵二叉樹Ti (1in)都只有一個權(quán)值為wi的根結(jié)點，其左、右子樹為空。,（2）在森林F中選擇兩棵根結(jié)點權(quán)值最小的二叉樹，作為一棵新二叉樹的左、右子樹，標(biāo)記新二叉樹的根結(jié)點權(quán)值為其左右子樹的根結(jié)點權(quán)值之和。,（3）從F中刪除被選中的那兩棵二叉樹，同時把新構(gòu)成的二叉樹加入到森林F中。,（4）重復(fù)（2）、（3）操作，直到森林中只含有一棵二叉樹為止，此時得到的這棵二叉樹就是哈夫曼樹。,直觀地看，在哈夫曼樹中權(quán)越大的葉子離根

48、越近，則其具有最小帶權(quán)路徑長度。,哈夫曼樹的手工構(gòu)造的方法也非常簡單：,給定數(shù)列W1.Wn，以n個權(quán)值構(gòu)成n棵樹的森林F；將F=T1.Tn按權(quán)從小到大排列； 取T1和T2合并組成一棵樹，使其根結(jié)點的權(quán)值T=T1+T2，再按大小插入F，反復(fù)此過程直到只有一棵樹為止。,6.5.2 哈夫曼編碼,哈夫曼樹最典型的應(yīng)用是在編碼技術(shù)上的應(yīng)用。利用哈夫曼樹，我們可以得到平均長度最短的編碼。,例如：設(shè)有一臺模型機，共有7種不同的指令，其使用頻率為：,變長編碼為：,使用變長編碼雖然可以使得程序的總位數(shù)達(dá)到最小，但機器卻無法解碼。如對編碼串0010110該怎樣識別呢？因此，若要設(shè)計變長的編碼，則這種編碼必須滿足這

49、樣一個條件：任意一個編碼不能成為其它任意編碼的前綴。我們把滿足這個條件的編碼叫做前綴編碼。,利用哈夫曼算法，我們可以設(shè)計出最優(yōu)的前綴編碼。見P148圖6.26。,對于該二叉樹，我們可以規(guī)定向左的分支標(biāo)記為1，向右的分支標(biāo)記為0。這樣，從根結(jié)點開始，沿線到達(dá)各頻度指令對應(yīng)的葉結(jié)點，所經(jīng)過的分支代碼序列就構(gòu)成了相應(yīng)頻度指令的哈夫曼編碼 。,指令的哈夫曼編碼,例如：傳送數(shù)據(jù)state,seat,act,tea,cat,set,a,eat，如何使傳送的長度最短？,為了保證長度最短，先看字符出現(xiàn)的次數(shù)，然后將出現(xiàn)次數(shù)當(dāng)作權(quán)。,按權(quán)構(gòu)造哈夫曼樹的過程見p144的圖6.33,規(guī)定二叉樹的構(gòu)造為左走0，右走1

50、。,按規(guī)定：0左1右，則有,000 001 01 10 11 2 3 5 7 8 c s e a t,所以state的編碼為00111101101 stat的編碼為001111011。,構(gòu)造滿足哈夫曼編碼的最短最優(yōu)性質(zhì)：,（1）若didj（字母不同），則對應(yīng)的樹葉不同。因此前綴碼（任一字符的編碼都不是另一個字符編碼 ）不同，一個路徑不可能是其他路徑的一部分，所以字母之間可以完全區(qū)別。,（2）將所有字符變成二進(jìn)制的哈夫曼編碼，使帶權(quán)路徑長度最短，相當(dāng)總的通路長度最短。,6.5.3 哈夫曼編碼算法的實現(xiàn),由于哈夫曼樹中沒有度為1的結(jié)點，則一棵有n個葉子的哈夫曼樹共有2n-1個結(jié)點，可用一個大小為2

51、n-1的一維數(shù)組來存放各個結(jié)點。,因為每個結(jié)點同時還包含其雙親信息和孩子結(jié)點信息，所以構(gòu)成一個靜態(tài)三叉鏈表。,靜態(tài)三叉鏈表的描述如下：,typedef struct unsigned int weight ; /* 用來存放各個結(jié)點的權(quán)值*/ unsigned int parent, LChild,RChild ; /*指向雙親、孩子結(jié)點的指針*/ HTNode, * HuffmanTree; /*動態(tài)分配數(shù)組，存儲哈夫曼樹*/ typedef char * *HuffmanCode ; /*動態(tài)分配數(shù)組，存儲哈夫曼編碼*/,創(chuàng)建哈夫曼樹并求哈夫曼編碼的算法 見p147的算法6.12,數(shù)組ht的前n個分量表示葉子結(jié)點，最后一個分量表示根結(jié)點。每個葉子結(jié)點對應(yīng)的編碼長度不等，但最長不超過n。,