1、第六章 樹和二叉樹,6.1 樹的定義和基本概念 6.2 二叉樹 6.2.1 樹的定義和基本術語 6.2.2 二叉樹的性質 6.2.3 二叉樹的存儲結構 6.3 遍歷二叉樹 6.3.1 遍歷二叉樹 6.3.2 線索二叉樹 6.4 樹和森林 6.4.1 樹的存儲結構 6.4.2 森林與二叉樹的轉換 6.4.3 樹和森林的遍歷 6.6 赫夫曼樹及其應用 6.6.1 最優(yōu)二叉數（赫夫曼數） 6.6.2 赫夫曼編碼,樹型結構是一類重要的非線性結構。樹型結構是結點之間有分支，并且具有層次關系的結構，它非常類似于自然界中的樹。樹結構在客觀世界中 是大量存在的，例如家譜、行政組織機構都可用樹形象地表示。樹在計

2、算機領域中也有著廣泛的應用，例如在編譯程序中，用樹來表示源程序的語法結構；在數據庫系統(tǒng)中，可用樹來組織信息；在分析算法的行為時，可用樹來描述其執(zhí)行過程。等等。,6.1 樹的定義和基本術語 定義：樹(Tree)是n(n=0)個結點的有限集T，T為空時稱為空樹，否則它滿足如下兩個條件： 有且僅有一個特定的稱為根(Root)的結點； 其余的結點可分為m(m=0)個互不相交的子集T1,T2,T3Tm，其中每個子集又是一棵樹，并稱其為子樹(Subtree)。 圖示,樹具有下面兩個特點： 樹的根結點沒有前驅結點，除根結點之外的所有結點有且只有一個前驅結點。 樹中所有結點可以有零個或多個后繼結點。,A,B,

3、C,D,E,F,G,H,I,J,M,K,L,抽象數據類型樹的定義：用二元組T（D，R） 數據對象 D：是具有相同特性的數據元素的集合。 數據關系 R： 若D為空集，則稱為空樹 ； 如D僅含一個數據元素，則R為空集； 否則:R=H，H如下二元關系： (1) 在D中存在唯一的稱為根的數據元素root； 該結點沒有前驅。 (2) 當n1時，其余結點可分為m (m0)個互 不相交的有限集T1, T2, , Tm，其中每一 棵子集本身又是一棵符合本定義的樹， 稱為根root的子樹。,其中D為樹T中結點的集合 R為樹中結點之間關系的集合。 當樹為空樹時，D； 當樹T不為空樹時有： DRootDF 其中，R

4、oot為樹T的根結點，DF為樹T的根Root的子樹集合。DF可由下式表示： DFD1D2Dm且DiDj（ij，1im，1jm） 當樹T中結點個數n1時，R；當樹T中結點個數n1時有： R，i1，2，m 其中，Root為樹T的根結點，ri是樹T的根結點Root的子樹Ti的根結點。,基本操作：,查 找 類,插 入 類,刪 除 類,Root(T) / 求樹的根結點,查找類：,Value(T, cur_e) / 求當前結點的元素值,Parent(T, cur_e) / 求當前結點的雙親結點,LeftChild(T, cur_e) / 求當前結點的最左孩子,RightSibling(T, cur_e)

5、/ 求當前結點的右兄弟,TreeEmpty(T) / 判定樹是否為空樹,TreeDepth(T) / 求樹的深度,TraverseTree( T, Visit() ) / 遍歷,InitTree( / 0號單元存儲根結點 SqBiTree bt; 從樹根起，自上層至下層，每層自左至右的給所有結點編號，完全二叉樹上編號為i的結點元素存儲在如上定義的一維數組中下標為i-1的分量中。,編號： 1 2 3 4 5 6 7 8 9 10 11 12,完全二叉樹,a,b,c,d,e,f,g,h,i,j,k,l,存儲單元： 0 1 2 3 4 5 6 7 8 9 10 11, 表示該處沒有元素存在僅僅為了好

6、理解,一般二叉樹,缺點是有可能對存儲空間造成極大的浪費，在最壞的情況下，一個深度為H且只有H個結點的右單支樹確需要2h-1個結點存儲空間。因此僅適用于完全二叉樹， 而且，若經常需要插入與刪除樹中結點時，順序存儲方式不是很好！,二、鏈式存儲結構 設計不同的結點結構可以構成不同形式的鏈式存儲結構： 1、二叉鏈表,A,D,E,B,C,F,root,結點結構:,lchild data rchild,C 語言的類型描述如下: typedef struct BiTNode / 結點結構 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指針 Bi

7、TNode, *BiTree;,2三叉鏈表,root,lchild data parent rchild,結點結構:,A,B,D,C,E,F,C 語言的類型描述如下: typedef struct TriTNode / 結點結構 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指針 struct TriTNode *parent; /雙親指針 TriTNode, *TriTree;,6.3 遍歷二叉樹和線索二叉樹 6.3.1遍歷二叉樹 一、問題的提出 順著某一條搜索路徑巡訪二叉樹中的結點，使得每個結點均被訪問一次，而且僅被訪問一次

8、。 “訪問”的含義可以很廣，如：輸出結點的信息等。 “遍歷”是任何類型均有的操作，對線性結構而言，只有一條搜索路徑(因為每個結點均只有一個后繼)，故不需要另加討論。而二叉樹是非線性結構， 每個結點有兩個后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。,假如以L、D、R分別表示遍歷左子樹、遍歷根結點和 遍歷右子樹，遍歷整個二叉樹則有DLR、LDR、LRD、 DRL、RDL、RLD六種遍歷方案。若規(guī)定先左后右，則只有前三種情況，分別規(guī)定為： DLR先（根）序遍歷， LDR中（根）序遍歷， LRD后（根）序遍歷。,由二叉樹的遞歸定義， 二叉樹的三個基本組成 單元是：根結點、左子 樹和右子樹。,b

9、,c,a,(根結點),(右子樹),(左子樹),1、先序遍歷二叉樹的操作定義為： 若二叉樹為空，則空操作；否則 （1）訪問根結點； （2）先序遍歷左子樹； （3）先序遍歷右子樹。 2、中序遍歷二叉樹的操作定義為： 若二叉樹為空，則空操作；否則 （1）中序遍歷左子樹； （2）訪問根結點； （3）中序遍歷右子樹。 3、后序遍歷二叉樹的操作定義為： 若二叉樹為空，則空操作；否則 （1）后序遍歷左子樹； （2）后序遍歷右子樹； （3）訪問根結點。,先根序列是： A B D C E G F H I ； 中根序列是： D B A E G C H F I 后根序列是： D B G E H I F C A ；,

10、可定義前驅及后繼結點： 如：二叉樹中的結點C， 它的先根前驅是D，先根后繼是E， 中根前驅是G，對稱序后繼是H,算法的遞歸描述 void Preorder (BiTree T, void( *visit)(TElemType/ 遍歷右子樹 /中序遍歷二叉樹？后序遍歷二叉樹 ？,非遞歸形式的算法？,非遞歸算法（棧應用的一個絕好的例子） 以中序遍歷為例： 當棧頂記錄中的指針非空時，應遍歷左子樹，即指向左子樹根的指針進棧； 若棧頂記錄中的指針值為空，則應退至上一層，若是從左子樹返回，則應訪問當前即棧頂記錄中指針所指的根結點； 若是從右子樹返回，則表明當前層遍歷結束，應繼續(xù)退棧。,出棧訪問的順序： c

11、baefdg,中序遍歷算法的非遞歸描述,BiTNode *GoFarLeft(BiTree T, Stack *S) if (!T ) return NULL; while (T-lchild ) Push(S, T); T = T-lchild; return T; ,void Inorder_I(BiTree T, void (*visit) (TelemType / 棧空表明遍歷結束 / while / Inorder_I,“遍歷”是二叉樹各種操作的基礎： 在一棵已知的樹中求指定結點的父結點； 求指定結點的子女結點. 遍歷的過程中生成結點，建立二叉樹的鏈式表示 例：按先序序列建立二叉樹：

12、 ABDCEFGHI；先序、中序、后序序列中任一個不能唯一確定一棵二叉樹，所以不能直接用，但如果 讀入A B D C E G F H I ， 則可建立相應的二叉鏈表 所以：二叉樹要先擴充為擴充的二叉樹，然后再按先序遍歷，其中表示為空結點,遍歷算法的應用舉例 建立二叉樹的存儲結構，如下二叉樹,ABDCEFGHI-按ABDCEFHI順序讀入字符 設從A開始，A的左子為B，B的左子樹為空，因此D一定是B的右子結點 D有兩個空子結點，說明C一定是A的右子結點,Status CreateBiTree(BiTree / CreateBiTree,若n2這個結點左子樹對應一個子表達式E1，右子樹對應另一個表

13、達式E2，則結點n2為根的子樹表示了一個E1 - E2的表達式。顯然因為abba， 所以上述子樹的次序是重要的。由于二叉樹本身的層次已經可以定義計算的次序，所以原表達式中的括號不再需要。 表達式為： (a-b) (c+d),二叉數與表達式 圖中n1，n2，n7是結點的名字，a，b，c，d和，是這些結點的值 圖中每個葉結點對應一個操作數，每個內部結點對應一個運算符 每個子樹對應一個子表達式,例如圖（1）所示的二叉樹表達式 (a+b*(c-d)-e/f) 若先序遍歷此二叉樹,按訪問結點的先后次序將結點排列起來,其先序序列為： -+a*b-cd/ef 按中序遍歷,其中序序列為： a+b*c-d-e/

14、f 按后序遍歷,其后序序列為： abcd-*+ef/- 人們喜歡中綴形式的算術 表達式,對于計算機,使 用后綴易于求值,*,a,/,b,-,d,c,f,e,僅知二叉樹的先序序列“abcdefg” 不能唯一確定一棵二叉樹，,由二叉樹的先序和中序序列建樹,如果同時已知二叉樹的中序序列“cbdaegf”，則會如何？,二叉樹的先序序列,二叉樹的中序序列,左子樹,左子樹,右子樹,右子樹,根,根,a b c d e f g,c b d a e g f,例如:,a,a,b,b,c,c,d,d,e,e,f,f,g,g,a,b,c,d,e,f,g,先序序列中序序列,6.3.2 線索二叉樹 當以二叉鏈表作為存儲結

15、構時,只能找到結點的左右孩子的信息,而不能在結點的任一序列的前驅與后繼信息,這種信息只有在遍歷的動態(tài)過程中才能得到；并且為了能保存遍歷過程中得到的信息,可增加標志域; 任何包括n個結點的二叉樹中，2n個指針中只有n - 1個用來指示結點的左、右子女，而另外n + 1個為空 解決方法：用指向結點在對稱序下的前驅結點或后繼結點的指針來代替這些空的指針，這種附加的指針稱作“線索”,ltag 0:指針,指向結點的左子女 1:線索,指向結點的前趨結點,rtag 0:指針,指向結點的右子女 1:線索,指向結點的后繼結點,指向該線性序列中的“前驅”和 “后繼” 的指針，稱作“線索”,與其相應的二叉樹，稱作

16、“線索二叉樹”,包含 “線索” 的存儲結構，稱作 “線索鏈表”,A B C D E F G H K, D ,C , B,E ,typedef struct BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左右指針 PointerThr LTag, RTag; / 左右標志 BiThrNode, *BiThrTree;,線索鏈表的類型描述：,typedef enum Link, Thread PointerThr; / Link=0:指針，Thread=1:線索,線索鏈表的遍歷算法:,p = firstNode(T);

17、While(p) Visit (p); p = Succ(p) ,由于在線索鏈表中添加了遍歷中得到的“前驅”和“后繼”的信息，從而簡化了遍歷的算法。 遍歷中，只要先找到序列的第一個結點，然后依次找結點的后繼直至其后繼為空時而止,如何在中序線索化鏈表中找結點的后繼 ？,若無右子樹，其右標志為“1”，則右鏈域直接指示了結點的后續(xù)；如葉子結點。 否則為對其右子樹進行中序遍歷時訪問的第一個結點。,如何在中序線索化鏈表中找結點的前驅 ？,若其左標志為“1”，則左鏈域直接指示了結點的前驅； 否則為遍歷左子樹時最后訪問的一個結點為前驅。,訪問線索二叉樹 在中序線索二叉樹中查找p指針所指結點的前驅 在中序線索

18、二叉樹中查找p指針所指結點的后繼,若p-ltag= =1，則p-lchild即指向前驅。 若p-ltag= =0，查中序遍歷直至某個結點的后繼是 *p時，則該結點即為*p的前驅。,若p-rtag= =1，則p-rchild即指向后繼。 若p-rtag= =0，則p所指結點的中序后繼必為其右子 樹第一個中序遍歷到達的結點，即從*p的右孩子開 始沿左指針鏈向下查找，直到找到一個沒有左孩子 的結點，該結點又稱為*p右子樹中“最左下”結點。,在后序線索二叉樹中查找p指針所指結點的前驅,若p-ltag= =1，則p-lchild即指向前驅。 若p-ltag= =0，則: 當p-rtag= =0,則p-r

19、child即指向前驅 當p-rtag= =1,則p-lchild即指向前驅,在后序線索二叉樹中查找p指針所指結點的后繼,若*p為根，后繼為空； 若*p是雙親的右孩子，則其雙親即為后繼； 若*p是雙親的左孩子，且*p沒有右兄弟，則其雙親即為后繼； 若*p是雙親的左孩子，且*p有右兄弟，則*p的后繼是其雙親右子樹中“最左下”的葉結點。,在前序線索二叉樹中查找p指針所指接點的前驅 在前序線索二叉樹中查找p指針所指接點的后繼,若p-ltag= =1，則p-lchild即指向前驅。 若p-ltag= =0，則查前序遍歷直至某個結點的后繼 是*p時，則該結點即為*p的前驅。,若p-rtag= =1，則p-

20、rchild即指向后繼。 若p-ltag= =0，則按前序遍歷從*p出發(fā)查找它的 第一個后繼結點，即為*p的后繼,模仿線性表的存儲結構,在二叉樹的線索鏈表上也添加一個頭結點,令其lchild域的指針指向二叉樹的根結點,其rchild域的指針指向中序遍歷時訪問的最后一個結點;同時,令二叉樹中序序列中的第一個結點lchild域指針的和最后一個結點rchild域的指針均指向頭結點;就像為二叉樹建立了一個雙向線索鏈表,就好比人在一個圓圈上走路,即可以從第一個結點順序后繼進行遍歷，也可以從最后一個結點起順前驅進行遍歷。 雙向線索鏈表的遍歷算法如下：,Status InorderTraverse_Thr(

21、BiThrTree T,status(*visit)(TElemType) /T指向頭結點,頭結點的lchild左鏈指向根結點 /中序遍歷二叉線索樹的非遞歸算法,對每個數據元素調用 /函數Visit p=Tlchild; / p指向根結點 while(p!=T) / 空樹或遍歷結束時，p=T while(p LTag = =Link) p=p lchild; / 第一個結點 if(!visit(p data) return error; while(p RTag = =Thread /InorderTraverse_Thr,在中序遍歷過程中修改結點的左、右指針域，以保存當前訪問結點的“前驅”和

22、“后繼”信息。遍歷過程中，附設指針pre, 并始終保持指針pre指向當前訪問的、指針p所指結點的前驅。 訪問操作的過程就是“在當前訪問的結點與它的前驅之間建立線索”,如何建立線索鏈表？,void InThreading(BiThrTree p) if (p) / 對以p為根的非空二叉樹進行線索化 InThreading(p-lchild); / 左子樹線索化 if (!p-lchild) / 建前驅線索 p-LTag = Thread; p-lchild = pre; if (!pre-rchild) / 建后繼線索 pre-RTag = Thread; pre-rchild = p; pre

23、 = p; / 保持 pre 指向 p 的前驅 InThreading(p-rchild); / 右子樹線索化 / if / InThreading,Status InOrderThreading(BiThrTree / InOrderThreading, ,if (!T) Thrt-lchild = Thrt; else Thrt-lchild = T; pre = Thrt; InThreading(T); pre-rchild = Thrt; / 處理最后一個結點 pre-RTag = Thread; Thrt-rchild = pre; ,6.4 樹和森林,6.4.1 樹的存儲結構 一

24、、雙親表示法 以一組連續(xù)空間存儲樹的結點，同時在每個結點中附設一個指示器指示其雙親結點在鏈表中的位置，形式如下： #define MAX_TREE_SIZE 100 typedef struct PTNode /結點結構 TElemType data; int parent;/雙親位置域 PTNode; typedef struct /樹結構 PTNode nodesMAX_TREE_SIZE; Int r,n;/根的位置和結點數 PTree；,二、孩子表示法 在樹的孩子鏈表中，以單鏈表將所有的雙親相同的孩子結點鏈接在一起，并將該鏈表的頭指針和雙親構成樹中的一個結點，定義如下： typedef

25、 struct CTNode /孩子結點 int child; struct CTNode *next; *ChildPtr; typedef struct TElemType data; ChildPtr firstchild;/孩子鏈表頭指針 CTBox; typedef struct CTNode nodesMAX_TREE_SIZE; int r,n;/根的位置和結點數 CTree；,如 r=5 n=11,A,B,C,D,E,R,F,G,H,J,K,0 1 2 3 4 5 6 7 8 9 10,1,3,2,4,0,7,6,8,9,10,樹？,三、孩子兄弟表示法 又稱為二叉樹表示法，或二

26、叉鏈表表示法。即以二叉鏈表作樹的存儲結構，表中結點的兩個鏈域分別指向該結點的“最左”孩子結點和下一個兄弟結點。形式表示為： Typedef struct CSNode ElemType data; struct CSNode *firstchild,*nextsibling; CSNode,*CSTree; 表示？（圖示）,6.4.2 森林與二叉樹的轉換 一、樹轉換為二叉樹 樹對應到二叉樹其根結點的右子樹總是為空的,二、森林轉換為二叉樹 把樹林F看作樹的序列，F = T1，T2，Tn，對應于F的二叉樹B(F)的定義： 若n = 0，則B(F)為空； 若，則B(F)的根是T1的根ROOT（T1）

27、，B(F)的左子樹是B( T11，T12，T1m1 )，其中T11，T12，T1m1是T1的子樹；B(F)的右子樹是B( T2，Tn )。,例: 對于圖的樹林F = T1，T2， 取T1的根A作B(F)的根 A的左子樹為B( T11，T12 )，再取T11的根B為A的左子樹的根 B的左子樹為空，B的右子樹為B( T12 )，于是取T12的根結點C作為B的右子樹的根 C的左子樹為B（T121 ），于是取T121的根K作C的左子樹的根，C的右子樹為空。類似地構造A的右子樹,三、二叉樹轉換為森林 設B是一棵二叉樹，r是B的根，L是r的左子樹，R是r的右子樹，則對應于B的樹林F(B)的定義是： 若B為

28、空，則F(B)是空的樹林； 若B不為空，則F(B)是一棵樹T1加上樹林F(R)，其中樹T1的根為r，r的子樹為F(L),二叉樹轉換為森林（續(xù)） 若某結點是其雙親的左孩子，則把該結點的右孩子，右孩子的右孩子，都與該結點的雙親線連起來，最后去掉所有的雙親到右孩子的連線 圖 (a)所示的二叉樹用這樣的方式處理就轉換成了(b)所示的樹林,6.4.2 樹和森林的遍歷 一、樹的遍歷可有三條搜索路徑: 先根(次序)遍歷: 若樹不空，則先訪問根結點，然后依次先根遍歷各棵子樹。 后根(次序)遍歷: 若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結點。 按層次遍歷: 若樹不空，則自上而下自左至右訪問樹中每個結點。

29、,A B C D E F G H I J K,先根遍歷時頂點的訪問次序：,A B E F C D G H I J K,后根遍歷時頂點的訪問次序：,E F B C I J K H G D A,層次遍歷時頂點的訪問次序：,A B C D E F G H I J K,A C D B G E F H I J K,1森林中第一棵樹的根結點；,2森林中第一棵樹的子樹森林；,3森林中其它樹構成的森林。,二、森林 的遍歷 森林由三部分構成：,1. 先序遍歷,森林的遍歷,若森林不空， 則訪問森林中第一棵樹的根結點； 先序遍歷森林中第一棵樹的子樹森林； 先序遍歷森林中(除第一棵樹之外)其余樹構成的森林。,即：依次

30、從左至右對森林中的每一棵樹進行先根遍歷。 頂點的訪問次序：？,中序遍歷,若森林不空，則 中序遍歷森林中第一棵樹的子樹森林； 訪問森林中第一棵樹的根結點； 中序遍歷森林中(除第一棵樹之外)其余樹構成的森林。,即：依次從左至右對森林中的每一棵樹進行后根遍歷。 頂點的訪問次序：？ 轉換為二叉樹進行比較？,樹的遍歷和二叉樹遍歷的對應關系 ？,先根遍歷,后根遍歷,樹,二叉樹,森林,先序遍歷,先序遍歷,中序遍歷,中序遍歷,實驗三：利用樹型結構的搜索算法模擬因特網域名的查詢,問題描述： 以樹型結構實現域名的搜索。既輸入某站點的域名，在域名系統(tǒng)的樹型結構中進行搜索，直至域名全部匹配成功或匹配失?。蝗舫晒t給出

31、該站點的IP地址，否則給出找不到該站點的信息。 基本要求： 首先要實現一個反映域名結構的樹，例如清華大學站點在該樹從根到葉子的各層結點就應是root,cn,edu,tsinghua,www。葉子結點www另有一個數據域，存放清華大學站點的IP地址,測試數據 可以取常用到的著名站點餓域名和IP地址為例構建域名結構的樹，一般應有30個左右的站點域名，當輸入 時，輸出為“”，而輸入為”時，輸出應為“找不到服務器或發(fā)生DNS錯誤。 實現提示 樹的存儲結構采用孩子-兄弟鏈表。 二叉鏈表的樹結構是一種動態(tài)結構，除第一次生成的過程需要人工輸入數據外，以后每次進行搜

32、索查詢時，應首先從文件中保存的數據自動生成樹結構。,實驗報告,題目 一、問題描述 二、需求分析 三、概要設計 四、詳細設計 五、調試分析 六、使用說明 七、測試結果 八、附錄（帶注釋的源程序）,6.6 哈夫曼樹及其應用,6.6.1 最優(yōu)二叉樹（哈夫曼樹） 一、最優(yōu)樹的定義 結點的路徑長度定義為： 從根結點到該結點的路徑上分支的數目。 樹的路徑長度定義為： 樹中每個結點的路徑長度之和 樹的帶權路徑長度定義為： 樹中所有葉子結點的帶權路徑長度之和 WPL(T) = wklk (對所有葉子結點)。 則帶權路徑長度取最小值的樹，稱為“最優(yōu)樹”。,假設有n個權值w1,w2, wn，構造一棵有n個葉子結點

33、的二叉樹，每個葉子結點的權值為wi,則其中帶權路徑長度WPL最小的二叉樹稱做最優(yōu)二叉樹或哈夫曼樹。,給出權是2，3，4，11，我們可以形成各種二叉樹，圖為其中三種。它們的帶權外部路徑長度分別為 WPL=111 + 24 + 32 + 33 = 34 WPL= 23 + 34 + 311 + 12 = 53 WPL= 22 + 211 + 23 + 24 = 40,哈夫曼樹的構造思想: 權越大的葉子離根越近，則二叉樹的帶權外部路徑長度就越小。 或說權越小的葉子離根越遠。,二、如何構造最優(yōu)二叉樹 根據給定的 n 個權值 w1, w2, , wn，構造 n 棵二叉樹的集合 F = T1, T2, ,

34、 Tn，其中每棵二叉樹中均只含一個帶權值為 wi 的根結點，其左、右子樹為空樹； 在 F 中選取其根結點的權值為最小的兩棵二叉樹，分別作為左、右子樹構造一棵新的二叉樹，并置這棵新的二叉樹根結點的權值為其左、右子樹根結點的權值之和； 從F中刪去這兩棵樹，同時加入剛生成的新樹； 重復 (2) 和 (3) 兩步，直至 F 中只含一棵樹為止。,例如: 已知權值 W= 5, 6, 2, 9, 7 ,構造哈夫曼樹算法,ww 外部結點：結點的權 內部結點：ww是以該結點為根的子樹中所有外部結點權的總和,parent 表示其父結點的位置，即父結點在數組中的下標值 根結點無父結點，其parent字段為-1,ll

35、ink,rlink llink, rlink分別為結點的左子女和右子女的位置，用子女在數組中的下標值給出 外部結點無子女，其子女的位置為-1。,哈夫曼樹算法采用的數據結構,構造哈夫曼樹(續(xù)),哈夫曼樹類型： struct HtNode/* 哈夫曼樹結點的結構 */ int ww; int parent,llink,rlink; struct HtTree struct HtNode htMAXNODE; int root;/* 哈夫曼樹根在數組中的位置 */ ; typedef struct HtTree *PHtTree;/* 哈夫曼樹類型的指針類型 */ 具有m個外部結點的哈夫曼樹，根據擴充二叉樹的定義，其內部結點為m-1，一共需要2m-1個結點空間,構造哈夫曼樹(續(xù)),哈夫曼樹的思想,初始化哈夫曼樹的數組 令前m個為外部結點，并賦權值,創(chuàng)建m-1個內部結點,申請2m-1大小的存放 哈夫曼樹的數組,構造哈夫曼樹(續(xù)),創(chuàng)建m-1個內部結點,在集合A找兩個最小權 無父結點的結點,構造內部結點,back,構造哈夫曼樹的算法,void CreateHuffmanTree(HuffmanTree / n個帶權結點形成初始化的森林，每個結點的左、右孩子為空,for