《西北大學樹和二叉樹.ppt》由會員分享，可在線閱讀，更多相關《西北大學樹和二叉樹.ppt（133頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第6章 樹和二叉樹,6.1 樹的定義與基本術語 6.2 二叉樹 6.3 二叉樹的遍歷與線索化 6.4 樹、森林和二叉樹的關系 6.5 哈夫曼樹及其應用 6.6 總結(jié)與提高,6.1 樹的定義與基本術語,1樹的基本概念 2樹的圖解表示法 3樹的相關術語 4樹的抽象數(shù)據(jù)類型,6.1 樹的定義與基本術語,樹定義：是n（n0）個結(jié)點的有限集合T。當n=0時，稱為空樹；當n0時，該集合滿足如下條件：,(1) 其中必有一個稱為根（root）的特定結(jié)點，它沒有直接前驅(qū)，但有零個或多個直接后繼。,(2) 其余n-1個結(jié)點可以劃分成m（m0）個互不相交的有限集T1，T2，T3，Tm，其中Ti又是一棵樹，稱為根ro

2、ot的子樹。每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，可有零個或多個直接后繼。,1樹的基本概念,例如：一棵樹的邏輯結(jié)構圖（6.1）為：,從圖中可以看出它好象一棵倒栽的樹。,2樹的圖解表示法,1）倒置樹結(jié)構（樹形表示法）圖6.1,2）文氏圖表示法（嵌套集合形式） 圖6.2,3）廣義表形式（嵌套擴號表示法）,4）凹入表示法 圖6.3,圖6.2 文氏圖表示法,圖6.3 凹入表示法,3.樹的相關術語：,結(jié)點：包含一個數(shù)據(jù)元素及若干指向其它結(jié)點的分支信息。,結(jié)點的度：一個結(jié)點的子樹個數(shù)稱為此結(jié)點的度。,葉結(jié)點：度為0的結(jié)點，即無后繼的結(jié)點，也稱為終端結(jié)點。,分支結(jié)點：度不為0的結(jié)點，也稱為非終端結(jié)點。,結(jié)點

3、的層次：從根結(jié)點開始定義，根結(jié)點的層次為1，根的直接后繼的層次為2，依此類推。,結(jié)點的層次編號：將樹中的結(jié)點按從上層到下層、同層從左到右的次序排成一個線性序列，依次給它們編以連續(xù)的自然數(shù)。,樹的度：樹中所有結(jié)點的度的最大值。,樹的高度（深度）：樹中所有結(jié)點的層次的最大值。,有序樹：在樹T中，如果各子樹Ti之間是有先后次序的，則稱為有序樹。,森林：m（m0）棵互不相交的樹的集合。將一棵非空樹的根結(jié)點刪去，樹就變成一個森林；反之，給森林增加一個統(tǒng)一的根結(jié)點，森林就變成一棵樹。,同構：對兩棵樹，通過對結(jié)點適當?shù)刂孛?，就可以使兩棵樹完全相等（結(jié)點對應相等，對應結(jié)點的相關關系也像等），則稱這兩棵樹同構

4、。,雙親結(jié)點：一個結(jié)點的直接前驅(qū)稱為該結(jié)點的雙親結(jié)點。上圖中A是B、C的雙親。,兄弟結(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é)點的直接后繼稱為該結(jié)點的孩子結(jié)點。如上圖的B、C是A的孩子。,我們常常借助人類家族樹的術語，以便于直觀理解結(jié)點間的層次關系。,堂兄弟：父親是兄弟關系或堂兄關系的結(jié)點稱為堂兄弟結(jié)點。在圖6.1中，結(jié)點E、G、H互為堂兄弟。

5、,前輩：層號比該結(jié)點小的結(jié)點，都稱為該結(jié)點的前輩。,后輩：層號比該結(jié)點大的結(jié)點，都稱為該結(jié)點的后輩。,4.樹的抽象數(shù)據(jù)類型,數(shù)據(jù)對象D：一個集合，該集合中的所有元素具有相同的特性。,數(shù)據(jù)關系R：若D為空集，則為空樹。若D中僅含有一個數(shù)據(jù)元素，則R為空集，否則R=H，H是如下的二元關系：,(1) 在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關系H下沒有前驅(qū)。,(2) 除root以外，D中每個結(jié)點在關系H下都有且僅有一個前驅(qū)。,基本操作：,InitTree（Tree）： 將Tree初始化為一棵空樹。 (2) DestoryTree（Tree）： 銷毀樹Tree。 (3) CreateTree（T

6、ree）： 創(chuàng)建樹Tree。 (4) TreeEmpty（Tree）： 若Tree為空，則返回TRUE，否則返回FALSE。 (5) Root（Tree）： 返回樹Tree的根。 (6) Parent（Tree，x）： 樹Tree存在，x是Tree中的某個結(jié)點。若x為非根結(jié)點，則返回它的雙親，否則返回“空”。 (7) FirstChild（Tree，x）： 樹Tree存在，x是Tree中的某個結(jié)點。若x為非葉子結(jié)點，則返回它的第一個孩子結(jié)點，否則返回“空”。 (8) NextSibling（Tree，x）： 樹Tree存在，x是Tree中的某個結(jié)點。若x不是其雙親的最后一個孩子結(jié)點，則返回x后

7、面的下一個兄弟結(jié)點，否則返回“空”。,基本操作:,(9) InsertChild（Tree，p，Child）： 樹Tree存在，p指向Tree中某個結(jié)點，非空樹Child與Tree不相交。將Child插入Tree中，做p所指向結(jié)點的子樹。 (10) DeleteChild（Tree，p，i）： 樹Tree存在，p指向Tree中某個結(jié)點，1id，d為p所指向結(jié)點的度。刪除Tree中p所指向結(jié)點的第i棵子樹。 (11) TraverseTree（Tree，Visit（）： 樹Tree存在，Visit（）是對結(jié)點進行訪問的函數(shù)。按照某種次序?qū)銽ree的每個結(jié)點調(diào)用Visit（）函數(shù)訪問一次且最多一

8、次。若Visit（）失敗，則操作失敗。,6.2 二叉樹,6.2.1 二叉樹的定義與基本操作,6.2.2 二叉樹的性質(zhì),6.2.3 二叉樹的存儲結(jié)構,6.2.1 二叉樹的定義與基本操作,定義：我們把滿足以下兩個條件的樹型結(jié)構叫做二叉樹（Binary Tree）： （1）每個結(jié)點的度都不大于2； （2）每個結(jié)點的孩子結(jié)點次序不能任意顛倒。,下面給出二叉樹的五種基本形態(tài)：,二叉樹的基本操作：,Initiate（bt）：將bt初始化為空二叉樹。 (2) Create(bt)：創(chuàng)建一棵非空二叉樹bt。 (3) Destory（bt）： 銷毀二叉樹bt。 (4) Empty（bt）： 若bt為空，則返回T

9、RUE，否則返回FALSE。 (5) Root(bt)： 求二叉樹bt的根結(jié)點。若bt為空二叉樹，則函數(shù)返回“空”。 (6) Parent（bt，x）：求雙親函數(shù)。求二叉樹bt中結(jié)點x的雙親結(jié)點。若結(jié)點x是二叉樹的根結(jié)點或二叉樹bt中無結(jié)點x，則返回“空”。,基本操作：,(7) LeftChild（bt，x）：求左孩子。若結(jié)點x為葉子結(jié)點或x不在bt中，則返回“空”。 (8) RightChild（bt，x）：求右孩子。若結(jié)點x為葉子結(jié)點或x不在bt中，則返回“空”。 (9) Traverse（bt）: 遍歷操作。按某個次序依次訪問二叉樹中每個結(jié)點一次且僅一次。 (10) Clear（bt）：

10、清除操作。將二叉樹bt置為空樹。,6.2.2 二叉樹的性質(zhì),性質(zhì)1：在二叉樹的第i層上至多有2i-1個結(jié)點(i1)。,當i=1時，整個二叉樹只有一根結(jié)點，此時2i-1=20=1，結(jié)論成立。,證明：,假設i=k時結(jié)論成立，即第k層上結(jié)點總數(shù)最多為2k-1個。,現(xiàn)證明當i=k+1時，結(jié)論成立：,因為二叉樹中每個結(jié)點的度最大為2，則第k+1層的結(jié)點總數(shù)最多為第k層上結(jié)點最大數(shù)的2倍，即22k-1=2(k+1)-1，故結(jié)論成立。,性質(zhì)2：深度為k的二叉樹至多有2k-1個結(jié)點（k1）。,證明：,因為深度為k的二叉樹，其結(jié)點總數(shù)的最大值是將二叉樹每層上結(jié)點的最大值相加，所以深度為k的二叉樹的結(jié)點總數(shù)至多為

11、：,故結(jié)論成立。,性質(zhì)3：對任意一棵二叉樹T，若終端結(jié)點數(shù)為n0，而其度數(shù)為2的結(jié)點數(shù)為n2，則n0= n2+1 。,證明：設二叉樹中結(jié)點總數(shù)為n，n1為二叉樹中度為1的結(jié)點總數(shù)。因為二叉樹中所有結(jié)點的度小于等于2，所以有 n= n0+ n1+n2 設二叉樹中分支數(shù)目為B，因為除根結(jié)點外，每個結(jié)點均對應一個進入它的分支，所以有：n=B+1。 又因為二叉樹中的分支都是由度為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é)論成立。,兩種

12、特殊的二叉樹：,滿二叉樹：深度為k且有2k-1個結(jié)點的二叉樹。在滿二叉樹中，每層結(jié)點都是滿的，即每層結(jié)點都具有最大結(jié)點數(shù)。,滿二叉樹,完全二叉樹：,關系：滿二叉樹必為完全二叉樹，而完全二叉樹不一定是滿二叉樹。,深度為k，結(jié)點數(shù)為n的二叉樹，如果其結(jié)點1n的位置序號分別與滿二叉樹的結(jié)點1n的位置序號一一對應，則為完全二叉樹,性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為2n+1。,證明：設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

13、 log2n k 因為k是整數(shù)，所以k -1 =log2n ， k= 2n+1 結(jié)論成立。,性質(zhì)5：對于具有n個結(jié)點的完全二叉樹，如果按照從上到下和從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點從1開始順序編號，則對于任意的序號為i的結(jié)點有：,(1)若i = 1, 則 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é)構,二叉樹的結(jié)構是非線性的，每一結(jié)點最

14、多可有兩個后繼。,二叉樹的存儲結(jié)構有兩種：順序存儲結(jié)構和鏈式存儲結(jié)構。,1.順序存儲結(jié)構：是用一組連續(xù)的存儲單元來存放二叉樹的數(shù)據(jù)元素 。,二叉樹的順序存儲結(jié)構,對于一般的二叉樹，我們必須按照完全二叉樹的形式來存儲，就會造成空間的浪費。單支樹就是一個極端情況。,單支樹,2. 鏈式存儲結(jié)構,對于任意的二叉樹來說，每個結(jié)點只有兩個孩子，一個雙親結(jié)點。我們可以設計每個結(jié)點至少包括三個域：數(shù)據(jù)域、左孩子域和右孩子域：,二叉鏈表,二叉樹T,二叉鏈表,typedef struct Node DataType data; strct Node * LChild; struct Node * RChild;

15、BiTNode, *BiTree;,用C語言描述定義二叉樹的二叉鏈表結(jié)構如下 ：,結(jié)論：若一個二叉樹含有n個結(jié)點，則它的二叉鏈表中必含有2n個指針域，其中必有n1個空的鏈域。,證明：,分支數(shù)目B=n-1，即非空的鏈域有n-1個，故空鏈域有2n-(n-1)=n+1個。,為了便于找到雙親結(jié)點，可以增加一個Parent域，以指向該結(jié)點的雙親結(jié)點。采用這種結(jié)點結(jié)構存放稱做二叉樹的三叉鏈表存儲結(jié)構。,6.3 二叉樹的遍歷與線索化,6.3.1 二叉樹的遍歷 6.3.2 遍歷算法應用 6.3.3 基于棧的遞歸消除 6.3.4 線索二叉樹 6.3.5 由遍歷序列確定二叉樹,6.3 二叉樹的遍歷與線索化,二叉樹

16、的遍歷：指按一定規(guī)律對二叉樹中的每個結(jié)點進行訪問且僅訪問一次。,二叉樹的基本結(jié)構由根結(jié)點、左子樹和右子樹組成,如圖示,6.3.1 二叉樹的遍歷,用L、D、R分別表示遍歷左子樹、訪問根結(jié)點、遍歷右子樹，那么對二叉樹的遍歷順序就可以有：,訪問根，遍歷左子樹，遍歷右子樹(記做DLR)。 訪問根，遍歷右子樹，遍歷左子樹(記做DRL)。 遍歷左子樹，訪問根，遍歷右子樹(記做LDR)。 遍歷左子樹，遍歷右子樹，訪問根 (記做LRD)。 遍歷右子樹，訪問根，遍歷左子樹 (記做RDL)。 遍歷右子樹，遍歷左子樹，訪問根 (記做RLD)。,在以上六種遍歷方式中，如果我們規(guī)定按先左后右的順序，那么就只剩有 DLR

17、 、LDR 和LRD三種。根據(jù)對根的訪問先后順序不同，分別稱DLR為先序遍歷或先根遍歷；LDR為中序遍歷（對稱遍歷）；LRD為后序遍歷。,注意：先序、中序、后序遍歷是遞歸定義的，即在其子樹中亦按上述規(guī)律進行遍歷。,三種遍歷方法的遞歸定義：,（1）先序遍歷（DLR）操作過程：,若二叉樹為空，則空操作，否則依次執(zhí)行如下操作： 訪問根結(jié)點； 按先序遍歷左子樹； 按先序遍歷右子樹。,若二叉樹為空，則空操作，否則依次執(zhí)行如下操作： 按中序遍歷左子樹； 訪問根結(jié)點； 按中序遍歷右子樹。,（2）中序遍歷（LDR）操作過程,（3）后序遍歷（LRD）操作過程：,若二叉樹為空，則空操作，否則依次執(zhí)行如下操作： 按

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

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

20、(root!=NULL) PostOrder(root -LChild); /*后序遍歷左子樹*/ PostOrder(root -RChild); /*后序遍歷右子樹* Visit(root -data); /*訪問根結(jié)點*/ ,以中序遍歷為例來說明中序遍歷二叉樹的遞歸過程,A,B,D,C,E,第一次經(jīng)過,第二次經(jīng)過,第三次經(jīng)過,6.3.2 遍歷算法應用,1.輸出二叉樹種的結(jié)點,【算法描述】 void PreOrder(BiTree root) /* 先序遍歷輸出二叉樹結(jié)點, root為指向二叉樹根結(jié)點的指針 */ if (root!=NULL) printf (root -data); /

21、* 輸出根結(jié)點 */ PreOrder(root -LChild); /* 先序遍歷左子樹 */ PreOrder(root -RChild); /* 先序遍歷右子樹 */ ,【算法思想】輸出二叉樹中的結(jié)點并無次序要求，因此可用三種遍歷算法中的任何一種完成，只需將訪問操作具體變?yōu)榇蛴〔僮骷纯伞Ｏ旅娼o出采用前序遍歷實現(xiàn)的算法。,2.輸出二叉樹中的葉子結(jié)點,【算法思想】輸出二叉樹中的葉子結(jié)點與輸出二叉樹中的結(jié)點相比，它是一個有條件的輸出問題，即在遍歷過程中走到每一個結(jié)點時需進行測試，看是否滿足葉子結(jié)點的條件。,【算法描述】 void PreOrder(BiTree root) /* 先序遍歷輸出二

22、叉樹中的葉子結(jié)點 , root為指向二叉樹根結(jié)點的指針 */ if (root!=NULL) if (root -LChild=NULL /* 先序遍歷右子樹 */ ,3.統(tǒng)計葉子結(jié)點數(shù)目,【算法思想】統(tǒng)計二叉樹中的葉子結(jié)點數(shù)目并無次序要求，因此可用三種遍歷算法中的任何一種完成，只需將訪問操作具體變?yōu)榕袛嗍欠駷槿~子結(jié)點及統(tǒng)計操作即可。,【算法描述】 /* LeafCount為保存葉子結(jié)點數(shù)目的全局變量,調(diào)用之前初始化值為0 */ void leaf(BiTree root) if(root!=NULL) leaf(root-LChild); leaf(root-RChild); if (roo

23、t -LChild=NULL ,方法一：,【算法思想】采用遞歸算法，如果是空樹，返回0；如果只有一個結(jié)點，返回1；否則為左右子樹的葉子結(jié)點數(shù)之和。,【算法描述】 int leaf(BiTree root) int LeafCount; if(root=NULL) LeafCount =0; else if (root-LChild=NULL) ,方法二：,3.統(tǒng)計葉子結(jié)點數(shù)目,4.建立二叉鏈表方式存儲的二叉樹,【算法思想】采用類似先序遍歷的遞歸算法，首先讀入當前根結(jié)點的數(shù)據(jù)，如果是.則將當前樹根置為空，否則申請一個新結(jié)點，存入當前根結(jié)點的數(shù)據(jù)，分別用當前根結(jié)點的左子域和右子域進行遞歸調(diào)用，創(chuàng)建

24、左右子樹。,【算法描述】 void CreateBiTree(BiTree *bt) char ch; ch=getchar(); if(ch=.) *bt=NULL; else *bt=(BiTree)malloc(sizeof(BiTNode); (*bt)-data=ch; CreateBiTree( ,5.求二叉樹的高度,設函數(shù)表示二叉樹bt的高度，則遞歸定義如下: 若bt為空，則高度為0 若bt非空，其高度應為其左右子樹高度的最大值加1,左 子 樹,右 子 樹,bt,hl,hr,High=max(hl+hr)+1,【算法思想】二叉樹bt的高度可以遞歸定義如下： l 若bt為空，則高度

25、為0 l若bt非空，其高度應為其左右子樹高度的最大值加1,【算法描述】 int PostTreeDepth(BiTree bt) /* 后序遍歷求二叉樹bt高度的遞歸算法 */ int hl, hr, max; if(bt!=NULL) hl=PostTreeDepth(bt-LChild); /* 求左子樹的深度 */ hr=PostTreeDepth(bt-RChild); /* 求右子樹的深度 */ max=hlhr?hl:hr; /* 得到左、右子樹深度較大者*/ return(max+1); /* 返回樹的深度 */ else return(0); /* 如果是空樹，則返回0 */

26、,求二叉樹的高度是也可用前序遍歷的方式實現(xiàn)。,【算法思想】二叉樹的高度（深度）為二叉樹中結(jié)點層次的最大值。設根結(jié)點為第1層的結(jié)點，所有h層的結(jié)點的左右孩子結(jié)點在h+1層。故可以通過遍歷計算二叉樹中的每個結(jié)點的層次，其中最大值即為二叉樹的高度。,【算法描述】 void PreTreeDepth(BiTeee bt, int h) /* 先序遍歷求二叉樹bt高度的遞歸算法，h為bt指向結(jié)點所在層次，初值為1*/ /*depth為當前求得的最大層次，為全局變量，調(diào)用前初值為0 */ if(bt!=NULL) if(hdepth) depth = h; /*如果該結(jié)點層次值大于depth，更新dept

27、h的值*/ PreTreeDepth(bt-Lchild, h+1); /* 遍歷左子樹 */ PreTreeDepth(bt-Rchild, h+1); /* 遍歷右子樹 */ ,6. 按樹狀打印的二叉樹,假設以二叉鏈表存儲的二叉樹中，每個結(jié)點所含數(shù)據(jù)元素均為單字母，要求實現(xiàn)如下圖的打印結(jié)果。,分析：這是二叉樹的橫向顯示問題，橫向顯示應是豎向顯示的900旋轉(zhuǎn)，又由于二叉樹的橫向顯示算法一定是中序遍歷算法，所以把橫向顯示的二叉樹算法改為RDL結(jié)構，實現(xiàn)算法為：,【算法思想】 （1）二叉樹的橫向顯示應是二叉樹豎向顯示的90。旋轉(zhuǎn)。分析圖6.15圖示可知，這種樹形打印格式要求先打印右子樹，再打印根

28、，最后打印左子樹，按由上而下順序看，其輸出的結(jié)點序列為：CFEADB，這恰為逆中序順序。解決二叉樹的橫向顯示問題采用“逆中序”遍歷框架，所以橫向顯示二叉樹算法為先右子樹、再根結(jié)點、再左子樹的RDL結(jié)構。 （2）在這種輸出格式中，結(jié)點的左右位置與結(jié)點的層深有關，故算法中設置了一個表示當前根結(jié)點層深的參數(shù)，以控制輸出結(jié)點的左右位置，每當遞歸進層時層深參數(shù)加1。這些操作應在訪問根結(jié)點時實現(xiàn)。,【算法描述】 void PrintTree(BiTree bt, int nLayer) /* 按豎向樹狀打印的二叉樹 */ if(bt = =NULL) return; PrintTree(bt -RChil

29、d, nLayer+1); PrintTree(bt -LChild , nLayer+1); ,for(int i=0; idata); /*按逆中序輸出結(jié)點，用層深決定的左右位置*/,思考：對二叉樹實現(xiàn)左右子樹交換，是否可采用先序、中序、后序中的任何一種算法實現(xiàn)，請簡要說明原因。,6.3.3 基于棧的遞歸消除,1. 中序遍歷二叉樹的非遞歸算法,首先應用遞歸進層的三件事與遞歸退層的三件事的原則,直接先給出中序遍歷二叉樹的非遞歸算法基本實現(xiàn)思路。,在大量復雜的情況下，遞歸的問題無法直接轉(zhuǎn)換成循環(huán)，需要采用工作棧消除遞歸。工作棧提供一種控制結(jié)構，當遞歸算法進層時需要將信息保留；當遞歸算法出層時需

30、要從棧區(qū)退出信息。,【算法思想】 （1）針對左遞歸，寫出遞歸進層的三件事 （2）接著寫出左遞歸返回時應執(zhí)行的語句：訪問根結(jié)點 （3）接著針對右遞歸，寫出遞歸進層的三件事 （4）針對遞歸退層，寫出遞歸退層的三件事（左、右遞歸公用）,void inorder(BiTree root); int i=0; p=bt; L1: if (p!=NULL) /* 遍歷左子樹 */ top=top+2; if(topm); stop-1=p; /* 本層參數(shù)進棧 */ stop=L2; /* 返回地址進棧 */ p=p-LChild; /* 給下層參數(shù)賦值 */ goto L1; /* 轉(zhuǎn)向開始 */ L2

31、: Visit(p-data); /* 訪問根 */ top=top+2; if(topm); stop-1=p; /* 遍歷右子樹 */,【算法描述】,stop=L3; p=p-RChild; goto L1; L3: if(top!=0) addr=stop; p=stop-1; /* 取出返回地址 */ top=top-2; /* 退出本層參數(shù) */ goto addr; ,可以看到，直接按定義得到的上述算法結(jié)構并不好，為使程序合理組織，需去掉goto語句，用循環(huán)句代替if與goto，此時返回斷點已無保留的必要，棧區(qū)只需保留本層參數(shù)。,整理后的算法框圖如下圖所示：,【算法思想】 從根結(jié)點

32、開始，只要當前結(jié)點存在，或者棧不空，則重復下面操作：,（1）從當前結(jié)點開始，進棧并走左子樹，直到左子樹為空。 （2）退棧并訪問。 （3）走右子樹。,【算法描述】 /*sm 表示棧，top表示棧頂指針*/ void inorder(BiTree root) /* 中序遍歷二叉樹，root為二叉樹的根結(jié)點 */ top=0; p=root; do while(p!=NULL) if (topm) return; top=top+1; stop=p; p=p-LChild ; /* 遍歷左子樹 */ if(top!=0) p=stop; top=top-1; Visit(p-data); /* 訪問

33、根結(jié)點 */ p=p-RChild; /* 遍歷右子樹 */ while(p!=NULL | top!=0) ,【算法思想】 從根結(jié)點開始，只要當前結(jié)點存在，或者棧不空，則重復下面操作：,(1)如果當前結(jié)點存在，則進棧并走左子樹。 (2)否則退棧并訪問，然后走右子樹。,【算法描述】 void InOrder（BiTree root）/* 中序遍歷二叉樹的非遞歸算法 */ InitStack ( ,遞歸算法的時間復雜度分析： 對有n個結(jié)點二叉樹，該算法每循環(huán)一次，p指向一個結(jié)點或空（無左孩子或無右孩子的結(jié)點的空鏈域），因此指向空的次數(shù)為n+1，n為結(jié)點個數(shù)，故循環(huán)次數(shù)為n+(n+1)=2n+1,

34、從而算法的復雜度為O(n)。 遞歸算法的空間復雜度分析：所需棧的空間最多等于二叉樹深度K乘以每個結(jié)點所需空間數(shù)，記作O(K)，。表面上看，遞歸算法好象并沒有使用棧，實際上遞歸算法的執(zhí)行，需要反復多次的自己調(diào)用自己。每調(diào)用一次，系統(tǒng)內(nèi)部都有系統(tǒng)運行棧區(qū)在支持，這是隱含的棧，需要保留本層參數(shù)、臨時變量與返回地址等等。隨著函數(shù)遞歸調(diào)用，運行棧繼續(xù)增長，直到函數(shù)執(zhí)行完，才徹底釋放占用的?？臻g。因此遞歸算法比非遞歸算法占用的空間更多。,2.后序遍歷二叉樹的非遞歸算法,【算法思想】 從根結(jié)點開始，只要當前結(jié)點存在，或者棧不空，則重復下面操作：,(1)從當前結(jié)點開始，反復入棧并左走，直到空的左子樹； (2)

35、 如果棧頂結(jié)點的右子為空，或者頂結(jié)點的右子為剛訪問過的結(jié)點，則退棧并訪問； (3) 否則，右走一步 。,【算法描述】 void PostOrder（BiTree root） BiTNode * p,*q； BiTree sStack_Size; int top=0; q=NULL; p=root; while(p!=NULL | top!=0) while(p!=NULL) top=+; if(top=Stack_Size) OverFlow(); /*棧溢出處理*/ stop=p; p=p-LChild; /*遍歷左子樹*/ if(top0) p=stop; if(p-RChild=NULL

36、) |(p-RChild=q) /* 無右孩子，或右孩子已遍歷過 */, visit(p-data); /* 訪問根結(jié)點* / q=p; /* 保存到q，為下一次已處理結(jié)點前驅(qū) */ top-; p=NULL; else p=p-RChild; ,6.3.4 線索二叉樹,1. 基本概念,二叉樹的遍歷運算是將二叉樹中結(jié)點按一定規(guī)律線性化的過程。當以二叉鏈表作為存儲結(jié)構時，只能找到結(jié)點的左、右孩子信息，而不能直接得到結(jié)點在遍歷序列中的前驅(qū)和后繼信息。要得到這些信息，第一種方法是將二叉樹遍歷一遍，在遍歷過程中便可得到結(jié)點的前驅(qū)和后繼，但這種動態(tài)訪問浪費時間；第二種方法是充分利用二叉鏈表中的空鏈域，將

37、遍歷過程中結(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é)點。,為了區(qū)分孩子結(jié)點和前驅(qū)、后繼結(jié)點，為結(jié)點結(jié)構增設兩個標志域，如下圖所示：,其中：,線索：在這種存儲結(jié)構中，指向前驅(qū)和后繼結(jié)點的指針叫做線索。,線索鏈表：以這種結(jié)構組成的二叉鏈表作為二叉樹的存儲結(jié)構，叫做線索鏈表。

38、,線索化：對二叉樹以某種次序進行遍歷并且加上線索的過程叫做線索化。,線索二叉樹：線索化了的二叉樹稱為線索二叉樹。,2. 二叉樹的線索化,【算法思想】,（1）中序線索化采用中序遞歸遍歷算法框架。 （2）加線索操作就是訪問結(jié)點操作。 （3）加線索操作需要利用剛訪問過結(jié)點與當前結(jié)點的關系，因此設置一個指針pre，始終記錄剛訪問過的結(jié)點，其操作如下： 如果當前遍歷結(jié)點root的左子域為空，則讓左子域指向pre ； 如果前驅(qū)pre的右子域為空，則讓右子域指向當前遍歷結(jié)點root； 為下次做準備，當前訪問結(jié)點root作為下一個訪問結(jié)點的前驅(qū)pre。,void Inthread(BiTree root) /

39、* 對root所指的二叉樹進行中序線索化，其中pre始終指向剛訪問過的結(jié)點，其初值為NULL* / if (root!=NULL) Inthread(root-LChild); /* 線索化左子樹 */ if (root-LChild=NULL) root-Ltag=1; root-LChile=pre; / *置前驅(qū)線索 */ if (pre!=NULL /*線索化右子樹*/ ,【算法描述】,3.在線索二叉樹中找前驅(qū)、后繼結(jié)點,(1) 找結(jié)點的中序前驅(qū)結(jié)點,【算法描述】 BiTNode * InPre(BiTNode * p) /* 在中序線索二叉樹中查找p的中序前驅(qū), 并用pre指針返回結(jié)

40、果 */ if(p-Ltag=1) pre= p-LChild; /*直接利用線索*/ else /* 在p的左子樹中查找“最右下端”結(jié)點 */ for(q= p-LChild;q-Rtag=0;q=q-RChild); pre=q; return(pre); ,下面是對同一棵二叉樹的遍歷方法不同得到的不同線索樹。,NULL,(2)在中序線索樹中找結(jié)點后繼,對于結(jié)點p，若要找其后繼結(jié)點，當p-Rtag=1時，p-RChild即為p的后繼結(jié)點；當p-Rtag=0時，說明p有右子樹，此時p的中序后繼結(jié)點即為其右子樹的“最左下端”的結(jié)點。其查找算法如下：,【算法描述】 BiTNode * InNex

41、t(BiTNode * p) /*在中序線索二叉樹中查找p的中序后繼結(jié)點，并用Next指針返回結(jié)果*/ if (p-Rtag=1) Next= p- RChild; /*直接利用線索*/ else /*在p的右子樹中查找“最左下端”結(jié)點*/ for(q= p-RChild; q-Ltag=0 ;q=q-LChild ); Next=q; return(Next) ,4.遍歷中序線索樹,(1)在中序線索樹上求中序遍歷的第一個結(jié)點,【算法描述】 BiTNode * InFirst(BiTree Bt) BiTNode *p=Bt; If(!p) return (NULL); while(p-LTa

42、g=0) p=p-Lchild; return p; ,(2)遍歷中序二叉線索樹,【算法描述】 void TInOrder(BiTree Bt) BITNode *p; P=InFirst(Bt); While(p) Visit(p); p = InNext(p)； ,5. 線索二叉樹的插入、刪除運算,二叉樹加上線索之后，當插入或刪除一結(jié)點時，可能會破壞原樹的線索。所以在線索二叉樹中插入或刪除結(jié)點的難點在于：插入一個結(jié)點后，仍要保持正確的線索。,我們主要以中序線索二叉樹為例，說明線索二叉樹的插入和刪除運算。,（1）插入結(jié)點運算,在中序線索二叉樹中插入結(jié)點可分為兩種情況： 第一種：將新的結(jié)點插入

43、到二叉樹中，作某結(jié)點的左孩子； 第二種：將新的結(jié)點插入到二叉樹中，作某結(jié)點的右孩子。,我們僅討論后一種情況。,InsNode(BiTNode * p, BiTNode * r)表示在線索二叉樹中插入r所指向的結(jié)點，做p所指結(jié)點的右孩子。,若結(jié)點p的右孩子為空，則插入結(jié)點r的過程很簡單。原來p的后繼變?yōu)閞的后繼，結(jié)點p變?yōu)閞的前驅(qū)，結(jié)點r成為p的右孩子。結(jié)點r的插入對p原來的后繼結(jié)點沒有任何的影響。,結(jié)點的右孩子為空時的插入過程為：,插入前,插入后,若p的右孩子不為空，則插入后，p的右孩子變?yōu)閞的右孩子結(jié)點，p變?yōu)閞的前驅(qū)結(jié)點，r變?yōu)閜的右孩子結(jié)點。這時還需要修改原來p的右子樹中“最左下端”結(jié)點

44、的左指針域，使它由原來的指向結(jié)點p變?yōu)橹赶蚪Y(jié)點r。插入過程為：,插入前,插入后,void InsNode(BiTNode * p , BiTNode * r) if (p-Rtag=1) /* p無右孩子 */ r-RChild=p-RChild; /* p的后繼變?yōu)閞的后繼 */ r-Rtag=1; p-RChild=r; /* r成為p的右孩子 */ r-LChild=p; /* p變?yōu)閞的前驅(qū) */ r-Ltag=1; else /* p有右孩子 */ s=p-RChild; while(s-Ltag=0) s=s-LChild; /* 查找p結(jié)點的右子樹的“最左下端”結(jié)點 */ r-R

45、Child=p-RChild; /* p的右孩子變?yōu)閞的右孩子 */ r-Rtag=0; r-LChild=p; /* p變?yōu)閞的前驅(qū) */ r-Ltag=1; p-RChild=r; /* r變?yōu)閜的右孩子 */ s-LChild=r; /* r變?yōu)閜原來右子樹的“最左下端”結(jié)點的前驅(qū) */ ,【算法描述】,（2）刪除結(jié)點運算,與插入操作一樣，在線索二叉樹中刪除一個結(jié)點也會破壞原來的線索，所以需要在刪除的過程中保持二叉樹的線索化。,在中序線索二叉樹中刪除結(jié)點r的過程為：,6.3.5 由遍歷序列確定二叉樹,由定義，二叉樹的前序遍歷是先訪問根結(jié)點D，其次遍歷左子樹L，最后遍歷右子樹R。即在結(jié)點的

46、前序序列中，第一個結(jié)點必是根D；而另一方面，由于中序遍歷是先遍歷左子樹L，然后訪問根D，最后遍歷右子樹R，則根結(jié)點D將中序序列分割成兩部分：在D之前是左子樹結(jié)點的中序序列，在D之后是右子樹結(jié)點的中序序列。反過來，根據(jù)左子樹的中序序列中結(jié)點個數(shù)，又可將前序序列除根以外分成左子樹的前序序列和右子樹的前序序列兩個部分。依次類推，便可遞歸得到整棵二叉樹 。,例：已知結(jié)點的前序序列和中序序列分別為： 前序序列：18 14 7 3 11 22 35 27 中序序列：3 7 11 14 18 22 27 35 則可按上述分解求得整棵二叉樹。,6.4 樹、森林和二叉樹的關系,6.4.1 樹的存儲結(jié)構 6.4.

47、2 樹、森林與二叉樹的相互轉(zhuǎn)換 6.4.3 樹與森林遍歷,6.4.1 樹的存儲結(jié)構,樹的主要存儲方法有： 1.雙親表示法 2.孩子表示法 3.孩子兄弟表示法,1. 雙親表示法：用一組連續(xù)的空間來存儲樹中的結(jié)點，在保存每個結(jié)點的同時附設一個指示器來指示其雙親結(jié)點在表中的位置，其結(jié)點的結(jié)構如下：,樹的雙親表示法如下圖：,雙親表示法的優(yōu)點： 利用了樹中每個結(jié)點（根結(jié)點除外）只有一個雙親結(jié)點的性質(zhì)，使得查找某個結(jié)點的雙親結(jié)點非常容易。,雙親表示法的缺點： 在求某個結(jié)點的孩子時，需要遍歷整個向量。,雙親表示法的存儲結(jié)構,#define MAX 100 typedef struct TNode DataT

48、ype data; int parent; TNode;,一棵樹可以定義為：,typedef struct TNode treeMAX; int nodenum; /*結(jié)點數(shù)*/ ParentTree;,2. 孩子表示法：通常是把每個結(jié)點的孩子結(jié)點排列起來，構成一個單鏈表，稱為孩子鏈表。n個結(jié)點共有n個孩子鏈表（葉結(jié)點的孩子鏈表為空表），而n個結(jié)點的數(shù)據(jù)和n個孩子鏈表的頭指針又組成一個順序表。,r,孩子表示法的存儲結(jié)構：,typedef struct ChildNode /* 孩子鏈表結(jié)點的定義 */ int Child; /* 該孩子結(jié)點在線性表中的位置 */ struct ChildNod

49、e * next; /*指向下一個孩子結(jié)點的指針 */ ChildNode; typedef struct /* 順序表結(jié)點的結(jié)構定義 */ DataType data; /* 結(jié)點的信息 */ ChildNode * FirstChild ; /* 指向孩子鏈表的頭指針 */ DataNode; typedef struct /* 樹的定義 */ DataNode nodesMAX; /* 順序表 */ int root,num; /* 該樹的根結(jié)點在線性表中的位置和該樹的結(jié)點個數(shù) */ ChildTree;,3. 孩子兄弟表示法（二叉鏈表表示法）：鏈表中每個結(jié)點設有兩個鏈域，分別指向該結(jié)點

50、的第一個孩子結(jié)點和下一個兄弟（右兄弟）結(jié)點。,孩子兄弟表示法的存儲結(jié)構：,typedef struct CSNode DataType data; /*結(jié)點信息*/ Struct CSNode *FirstChild, *Nextsibling; /*第一個孩子,下一個兄弟*/ CSNode, *CSTree;,優(yōu)點：便于實現(xiàn)樹的各種操作。,6.4.2 樹、森林與二叉樹的相互轉(zhuǎn)換,1. 樹轉(zhuǎn)換為二叉樹,我們約定樹中每一個結(jié)點的孩子結(jié)點按從左到右的次序順序編號，也就是說，把樹作為有序樹看待。,例如：右圖的樹,將一棵樹轉(zhuǎn)換為二叉樹的方法：, 樹中所有相鄰兄弟之間加一條連線。 對樹中的每個結(jié)點，只保

51、留其與第一個孩子結(jié)點之間的連線，刪去其與其它孩子結(jié)點之間的連線。 以樹的根結(jié)點為軸心，將整棵樹順時針旋轉(zhuǎn)一定的角度，使之結(jié)構層次分明。,結(jié)論：從轉(zhuǎn)換過程可看出：樹中的任意一個結(jié)點都對應于二叉樹中的一個結(jié)點。樹中某結(jié)點的第一個孩子在二叉樹中是相應結(jié)點的左孩子，樹中某結(jié)點的右兄弟結(jié)點在二叉樹中是相應結(jié)點的右孩子。也就是說，在二叉樹中，左分支上的各結(jié)點在原來的樹中是父子關系，而右分支上的各結(jié)點在原來的樹中是兄弟關系。由于樹的根結(jié)點沒有兄弟，所以變換后的二叉樹的根結(jié)點的右孩子必然為空。,樹與二叉樹的對應關系及轉(zhuǎn)換方法,2. 森林轉(zhuǎn)換為二叉樹,森林轉(zhuǎn)換為二叉樹的方法為：,（1）將森林中的每棵樹轉(zhuǎn)換成相應

52、的二叉樹。 （2）第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點作為前一棵二叉樹根結(jié)點的右孩子，當所有二叉樹連在一起后，所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。,森林轉(zhuǎn)換為二叉樹的過程,將森林F看作樹的有序集F=T1，T2，,TN，它對應的二叉樹為B（F）：則有： （1）若N=0，則B（F）為空。 （2）若N0，二叉樹B（F）的根為森林中第一棵樹T1的根； B（F）的左子樹為B（T11，T1m），其中T11，T1m是T1的子樹森林；B（F）的右子樹是B（T2，TN）。 。,用遞歸的方法描述上述轉(zhuǎn)換過程：,3. 二叉樹還原為樹或森林,一棵二叉樹還原為樹或森林，具體方法為：,（

53、1）若某結(jié)點是其雙親的左孩子，則把該結(jié)點的右孩子、右孩子的右孩子、都與該結(jié)點的雙親結(jié)點用線連起來。 （2）刪掉原二叉樹中所有雙親結(jié)點與右孩子結(jié)點的連線。 （3）整理由（1）、（2）兩步所得到的樹或森林，使之結(jié)構層次分明。,用遞歸的方法描述其轉(zhuǎn)換過程為：,若B是一棵二叉樹，T是B的根結(jié)點，L是B的左子樹，R為B的右子樹，且B對應的森林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）中其余

54、樹組成的森林，即F(R) T2, T3, ,Tn。,6.4.3 樹與森林的遍歷,1. 樹的遍歷,樹的遍歷方法主要有以下兩種：,（1）先根遍歷,若樹非空，則遍歷方法為： 訪問根結(jié)點。 從左到右，依次先根遍歷根結(jié)點的每一棵子樹。,如圖中樹的先根遍歷序列為：ABECFHGD。,(2)后根遍歷,若樹非空，則遍歷方法為：,從左到右，依次后根遍歷根結(jié)點的每一棵子樹。 訪問根結(jié)點。,如圖中樹的后根遍歷序列為：EBHFGCDA。,樹的遍歷結(jié)果與由樹轉(zhuǎn)化成的二叉樹有如下對應關系： 樹的先根遍歷 轉(zhuǎn)化二叉樹的前序遍歷 樹的后根遍歷 轉(zhuǎn)化二叉樹的中序遍歷,2.樹的遍歷算法實現(xiàn),void RootFirst(CSTr

55、ee root) if (root!=NULL) Visit(root -data); /* 訪問根結(jié)點 */ p= root- FirstChild; while (p!=NULL) RootFirst( p ); /* 訪問以p為根的子樹 */ p = p - Nextsibling; ,方法一,void RootFirst(CSTree root) if (root!=NULL) Visit (root -data); /*訪問根結(jié)點*/ RootFirst (root-FirstChild); /*先根遍歷首子樹*/ RootFirst (root-Nextsibling); /*先根

56、遍歷兄弟樹*/ ,方法二,3. 森林的遍歷,森林的遍歷方法主要有以下三種：,(1)先序遍歷,若森林非空，則遍歷方法為：,訪問森林中第一棵樹的根結(jié)點。 先序遍歷第一棵樹的根結(jié)點的子樹森林。 先序遍歷除去第一棵樹之后剩余的樹構成的森林。,(2)中序遍歷,若森林非空，則遍歷方法為：,中序遍歷森林中第一棵樹的根結(jié)點的子樹森林。 訪問第一棵樹的根結(jié)點。 中序遍歷除去第一棵樹之后剩余的樹構成的森林。,(3)后序遍歷,若森林非空，則遍歷方法為：,后序遍歷森林中第一棵樹的根結(jié)點的子樹森林。 后序遍歷除去第一棵樹之后剩余的樹構成的森林。 訪問第一棵樹的根結(jié)點。,6.5 哈夫曼樹及其應用,6.5.1 哈夫曼樹 6

57、.5.2 哈夫曼編碼,1. 哈夫曼樹的基本概念：,路徑：指從一個結(jié)點到另一個結(jié)點之間的分支序列。 路徑長度：指從一個結(jié)點到另一個結(jié)點所經(jīng)過的分支數(shù)目。 結(jié)點的權：給樹的每個結(jié)點賦予一個具有某種實際意義的實數(shù)，我們稱該實數(shù)為這個結(jié)點的權。 帶權路徑長度：在樹形結(jié)構中，我們把從樹根到某一結(jié)點的路徑長度與該結(jié)點的權的乘積，叫做該結(jié)點的帶權路徑長度。 樹的帶權路徑長度：為樹中所有葉子結(jié)點的帶權路徑長度之和，通常記為： 其中n為葉子結(jié)點的個數(shù)， wi為第i個葉子結(jié)點的權值，li為第i個葉子結(jié)點的路徑長度。,例如下圖所示的具有不同帶權路徑長度的二叉樹,WPL(a)=7252224236 WPL(b)=42

58、73532146 WPL(c)=7152234335,問題1：什么樣的二叉樹的路徑長度PL最小？,一棵樹的路徑長度為0結(jié)點至多只有1個（根）； 路徑長度為1結(jié)點至多只有2個（兩個孩子）； 路徑長度為2結(jié)點至多只有4個； 依此類推：路徑長度為K結(jié)點至多只有2k個，所以n個結(jié)點二叉樹其路徑長度至少等于如下序列的前n項之和。,路徑長度 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對應的路徑長度為 log2n ，所以前n項之和為:,完全二叉樹的路徑長度為：

59、,h為樹的深度，其路徑長度可達到最小，所以完全二叉樹具有最小路徑長度的性質(zhì)，但不具有唯一性。,例如：下列不同形狀的二叉樹具有最小的路徑長度,問題2：什么樣的帶權樹路徑長度最??？,例如：給定一個權值序列2,3,4,7，可構造的多種二叉樹的形態(tài)。,2. 構造哈夫曼樹,哈夫曼樹又叫最優(yōu)二叉樹，它是由n個帶權葉子結(jié)點構成的所有二叉樹中帶權路徑長度WPL最短的二叉樹。,構造哈夫曼算法的步驟如下：,(1)用給定的n個權值w1,w2, ,wn對應的n個結(jié)點構成n棵二叉樹的森林F=T1,T2, ,Tn，其中每一棵二叉樹Ti (1in)都只有一個權值為wi的根結(jié)點，其左、右子樹為空。 (2)在森林F中選擇兩棵根

60、結(jié)點權值最小的二叉樹，作為一棵新二叉樹的左、右子樹，標記新二叉樹的根結(jié)點權值為其左右子樹的根結(jié)點權值之和。 (3)從F中刪除被選中的那兩棵二叉樹，同時把新構成的二叉樹加入到森林F中。 (4)重復（2）、（3）操作，直到森林中只含有一棵二叉樹為止，此時得到的這棵二叉樹就是哈夫曼樹。,直觀地看，在哈夫曼樹中權越大的葉子離根越近，則其具有最小帶權路徑長度。,哈夫曼樹的手工構造的方法也非常簡單：,給定數(shù)列W1.Wn，以n個權值構成n棵樹的森林F；將F=T1.Tn按權從小到大排列； 取T1和T2合并組成一棵樹，使其根結(jié)點的權值T=T1+T2，再按大小插入F，反復此過程直到只有一棵樹為止。,3.哈夫曼樹的

61、類型定義,(1)存儲結(jié)構 哈夫曼樹是一種二叉樹 ,由于哈夫曼樹中沒有度為1的結(jié)點，則一棵有n個葉子的哈夫曼樹共有2n1個結(jié)點，可以用一個大小為2n1 的一維數(shù)組存放哈夫曼樹的各個結(jié)點。由于每個結(jié)點同時還包含其雙親信息和孩子結(jié)點的信息，所以構成一個靜態(tài)三叉鏈表。,靜態(tài)三叉鏈表中：每個結(jié)點的結(jié)構為 :,各結(jié)點存儲在一維數(shù)組中，0號單元不使用，從1號位置開始使用。,(2)哈夫曼樹的類型定義,用靜態(tài)三叉鏈表實現(xiàn)的哈夫曼樹類型定義如下： #define N 20 /* 葉子結(jié)點的最大值。*/ #define M 2*N-1 /* 所有結(jié)點的最大值*/ typedef struct int weight

62、; /* 結(jié)點的權值*/ int parent ; /* 雙親的下標*/ int LChild ; /* 左孩子結(jié)點的下標*/ int RChild ; /* 右孩子結(jié)點的下標*/ HTNode, HuffmanTreeM+1; /* HuffmanTree是一個結(jié)構數(shù)組類型，0號單元不用。 */,4. 哈夫曼樹的算法實現(xiàn),【算法描述】 void CrtHuffmanTree(HuffmanTree ht, int w , int n) /*構造哈夫曼樹htM+1， w 存放n個權值。*/ for(i=1;i=n;i+) hti = wi,0,0,0; /* 1 n號單元存放葉子結(jié)點，初始化*

63、/ m=2*n-1; for(i=n+1;i=m;i+) hti =0,0,0,0; /*初始化完畢！對應算法步驟1*/ for(i=n+1; i=m; i+) /*創(chuàng)建非葉結(jié)點，建哈夫曼樹*/ select(ht, i-1, s1, s2); /* 在 ht1 hti-1 的范圍內(nèi)選擇兩個parent為0且 weight最小的結(jié)點，其序號分別賦值給s1、s2返回 */ ht i.weight= ht s1.weight+ ht s2.weight; ht s1.parent=i; ht s2.parent=i; ht i.LChild=s1; ht i.RChild=s2; /*哈夫曼樹建立

64、完畢*/ ,例：傳送數(shù)據(jù)中的二進制編碼。要傳送數(shù)據(jù)state,seat,act,tea,cat,set,a,eat，如何使傳送的長度最短？,為了保證長度最短，先計算各個字符出現(xiàn)的次數(shù)，然后將出現(xiàn)次數(shù)當作權。,字符 s t a e c 字符出現(xiàn)的次數(shù) 3 8 7 5 2,按權構造哈夫曼樹的過程如下圖：,按照創(chuàng)建哈夫曼樹的算法，對上圖建立哈夫曼樹的結(jié)果如下表：,6.5.2 哈夫曼編碼,哈夫曼樹最典型的應用是在編碼技術上的應用。利用哈夫曼樹，我們可以得到平均長度最短的編碼。,例如：設有一臺模型機，共有7種不同的指令，其使用頻率為：,變長編碼為：,1.哈夫曼編碼的概念,(1)前綴碼：如果在一個編碼系統(tǒng)

65、中，任一個編碼都不是其他任何編碼的前綴（最左子串），則稱該編碼系統(tǒng)中的編碼是前綴碼。例如，一組編碼01，001，010，100，110就不是前綴碼，因為01是010的前綴，若去掉01或010就是前綴碼。例如，名字中的鄭霞、鄭霞錦就不是前綴碼。 (2)哈夫曼編碼：對一棵具有n個葉子的哈夫曼樹，若對樹中的每個左分支賦予0，右分支賦予1，則從根到每個葉子的通路上，各分支的賦值分別構成一個二進制串，該二進制串就稱為哈夫曼編碼。,定理6-1 哈夫曼編碼是前綴碼。 證明：哈夫曼編碼是根到葉子路徑上的邊的編碼的序列，也就是等價邊序列，而由樹的特點知，若路徑A是另一條路經(jīng)B的最左部分，則B經(jīng)過了A，因此，A的終點不是葉子。而哈夫曼編碼都對應終點為葉子的路徑，所以，任一哈夫曼碼都不會與任意其他哈夫曼編碼的前部分完全重疊，因此哈夫曼編碼是前綴碼。,定理