數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)及其算法）

馮耀霖1.

Chap6

樹（二）

樹與森林

搜索二叉樹

哈夫曼樹

堆

2.§1樹與森林

▲樹的存儲結(jié)構(gòu)▲樹的實現(xiàn)3.1.1樹的存儲結(jié)構(gòu)

關(guān)于樹的存儲結(jié)構(gòu)有許多種，這里介紹常用的兩種。■父結(jié)點數(shù)組表示法■左孩子右兄弟表示法4.1.

父結(jié)點數(shù)組表示法

這是一種順序結(jié)構(gòu)與鏈結(jié)構(gòu)相結(jié)合的樹存儲方法，它以一組連續(xù)的存儲單元（數(shù)組）來存放樹中的結(jié)點。每個結(jié)點有兩個域：data域，存放數(shù)據(jù)元素；parent域，存放其父結(jié)點在數(shù)組中的位置序號（下標），相當于父結(jié)點的指針，其數(shù)值為0（或-1），則表示該結(jié)點無父結(jié)點，即它是根結(jié)點。如圖6-1所示樹，圖6-2所示該樹的父結(jié)點數(shù)組表示法結(jié)構(gòu)。樹中結(jié)點的存放順序一般不做特殊要求。如圖6-2中使用的是層次方法。5.ABCDEFGIHJdataparentA0B1C1D1E2F3G4H7I7J7下標12345678910

圖6.1樹

圖6.2樹的父結(jié)點表示法6.2.左孩子右兄弟表示法左孩子右兄弟表示法是目前已知的最節(jié)省存儲空間的樹的鏈式存儲結(jié)構(gòu)方法，它是一種基于遞歸的定義方式。它的每一個結(jié)點由三個域組成：data、leftChild和rightSibling。leftChild域存放的是該結(jié)點最左（第一個）孩子的地址，rightSibling域存放的是該結(jié)點右兄弟的地址。

leftChilddatarightSibling7.在圖6-1中，樹的根結(jié)點是A，它沒有兄弟，所以它的rightSibling值為空。A有三個孩子，分別為B、C和D，因此它的leftChild值是其最左孩子——結(jié)點B的地址。B既有孩子又有兄弟，它的rightSibling指向的是右鄰兄弟C，而leftChild指向的是其孩子E。結(jié)點E是B的唯一孩子且為葉子，所以它的leftChild值和rightSibling值均為空。依照上述規(guī)則可以很方便地建立起樹形結(jié)構(gòu)的存儲模式。理解該表示方法的關(guān)鍵在于理解它的遞歸本質(zhì)。為了幫助理解為什么僅通過每個結(jié)點的3個域就能實現(xiàn)整棵樹的存儲，下面給出對以圖6-1中樹的基于先序的遍歷過程。8.→先訪問根結(jié)點A。A無兄弟有左孩子，所以A不入棧，并訪問A的左孩子B；→結(jié)點B既有孩子也有兄弟，于是B入棧，并訪問它的左孩子E；→結(jié)點E是葉子，且無兄弟，所以遍歷過程回退到結(jié)點B；→訪問B的右兄弟C，C既有兄弟又有孩子，所以C入棧，并訪問C的左孩子F；→結(jié)點F是葉子，且無兄弟，所以遍歷過程回退到結(jié)點C；→訪問C的右兄弟D，D無兄弟但有孩子，所以D不入棧，并訪問D的左孩子G；9.→結(jié)點G無兄弟有孩子，所以G不入棧，并訪問G的左孩子H；→結(jié)點H是葉子，但有兄弟，所以H不入棧，并訪問H的右兄弟I;→結(jié)點I是葉子，但有兄弟，所以I不入棧，并訪問I的右兄弟J；→結(jié)點J是葉子，也無兄弟，且此時棧為空，至此整個遍歷過程結(jié)束。

由此可見，盡管左孩子右兄弟表示法的每個結(jié)點單元僅有3個域，但它們對構(gòu)建樹形結(jié)構(gòu)的復(fù)雜模型已經(jīng)足夠了。10.1.2樹的實現(xiàn)

以左孩子右兄弟樹為例。

1.樹結(jié)點template<typenameType>structTreeNode{Typedata;TreeNode*leftChild,*rightSibling;//左孩子右兄弟指針};11.2.樹類

template<typenameType>classTree{private:TreeNode<Type>*root,*current;//根指針與當前指針<基本操作的內(nèi)部成員函數(shù)原型聲明>public:<基本操作的外部成員函數(shù)原型聲明>};

12.3.基本操作的算法

SetCurNodeParentElemLeftChildRightSiblingAddNewChildInsertLeftChildInsertSibling13.算法6.1SetCurNode

功能：設(shè)置當前結(jié)點boolSetCurNode(Typee){//將值為e的結(jié)點設(shè)置為當前結(jié)點returnCurNode(root,e);}

算法6.2CurNode

功能：設(shè)置當前結(jié)點14.boolCurNode(TreeNode*r,Typee){//在根為r的樹中查找值為e的結(jié)點，將其設(shè)置為當前結(jié)點if(r==NULL)returnFALSE;if(r->data==e){current=r;returnTRUE;}if(CurNode(r->leftChild,e)==TRUE)//遞歸遍歷r的左孩子returnTRUE;TreeNode*p=r->rightSibling;while(p!=NULL){//遞歸遍歷r的右兄弟if(CurNode(p,e)==TRUE)returnTRUE;p=r->rightSibling;}returnFALSE;}15.算法6.3ParentElem

功能：查找父結(jié)點并讀取其元素boolParentElem(Typev,Type&e){//查找v結(jié)點的父結(jié)點，并讀取其元素if(v==root->data)returnFALSE;if(CurNode(root,v)==FALSE)returnFALSE;if(Parent(root,current)==FALSE)returnFALSE;e=current->data;returnTRUE;}16.算法6.4Parent

功能：查找父結(jié)點boolParent(TreeNode*r,TreeNode*k){//在根為r的樹中查找結(jié)點k的父結(jié)點，使其成為當前結(jié)點if(r==NULL)returnFALSE;TreeNode*cp=r->leftChild,*sp=cp->rightSibling;if(cp==k){current=r;returnTRUE;}if(Parent(cp->leftChild,k)==TRUE)//左孩子遞歸查找returnTRUE;17.while(sp!=NULL){if(sp==k){current=r;returnTRUE;}

//右兄弟的孩子的遞歸查找if(Parent(sp->leftChild,k)==TRUE)returnTRUE;sp=sp->rightSibling;}returnFALSE;}18.算法6.5LeftChild

功能：查找左孩子boolLeftChild(){//查找當前結(jié)點的左孩子，使其成為當前結(jié)點if((current!=NULL&¤t->leftChild!=NULL){current=current->leftChild;returnTRUE;}returnFALSE;}19.算法6.6RightSibling

功能：查找右兄弟boolRightSibling(){//查找當前結(jié)點的右兄弟，使其成為當前結(jié)點if(current!=NULL&¤t->rightSibling!=NULL){current=current->rightSibling;returnTRUE;}returnFALSE;}20.算法6.7AddNewChild

功能：添加孩子

boolAddNewChild(Typev,Typee){//元素e添加為元素v的結(jié)點的孩子if(CurNode(root,v)==FALSE)returnFALSE;

//設(shè)置元素為v的結(jié)點為當前結(jié)點AddChild(current,e);returnTRUE;}21.算法6.8AddChild

功能：添加孩子22.voidAddChild(TreeNode*x,Typee){//為結(jié)點x添加元素為e的孩子TreeNode*p=newTreeNode,*t;p->data=e;p->leftChild=p->Sibling=NULL;if(x->leftChild==NULL)x->leftChild=p;else{t=x->leftChild;while(t->rightSibling!=NULL)t=t->rightSibling;t->rightSibling=p;}}23.算法6.9InsertLeftChild

功能：插入左孩子voidInsertLeftChild(TreeNode*x,Typee){//將元素為e的結(jié)點插入為結(jié)點x的左孩子TreeNode*p=newTreeNode,*t;p->data=e;p->leftChild=NULL;p->Sibling=x->leftChild;x->leftChild=p;}24.算法6.10AddRightSibling

功能：添加右兄弟boolAddRightSibling(Typev,Typee){//元素e添加為元素v的右兄弟TreeNode*p;if(CurNode(root,v)==FALSE)returnFALSE;InsertSibling(current,e);returnTRUE;}25.算法6.11InsertSibling

功能：插入右兄弟voidInsertSibling(TreeNode*x,Typee){//將元素為e的結(jié)點插入為結(jié)點x的右兄弟TreeNode*p=newTreeNode;p->data=e;p->leftChild=NULL;if(x->rightSibling!=NULL)p->rightSibling=x->rightSibling;x->rightSibling=p;}26.1.3樹與森林的遍歷

樹的遍歷方式有兩種：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。森林的遍歷主要采用的是深度優(yōu)先方式。27.1.樹的深度優(yōu)先遍歷可以分為兩種具體的形式：先序遍歷和后序遍歷。先序遍歷的規(guī)則：如果樹非空，則訪問其根結(jié)點，然后從左到右先序遍歷根的每棵子樹。后序遍歷的規(guī)則：如果樹非空，則從左到右后序遍歷根的每棵子樹，然后訪問根結(jié)點。28.ACBDEFGIHJADCBGFEJIH圖6.3樹的深度優(yōu)先遍歷

先序遍歷ABECFDGHIJ(b)后序遍歷EBFCHIJGDA

29.算法6.12PreTreeOrder

功能：樹的先序深度優(yōu)先遍歷

voidPreTreeOrder(TreeNode<Type>*r,void(*Visit)(Type&))//private{if(r!=NULL){Visit(r->data);TreeNode*p=r->leftChild;PreTreeOrder(p,Visit);//遞歸遍歷左孩子while(p->rightSibling!=NULL){//遞歸遍歷右兄弟PreTreeOrder(p->rightSibling,Visit);p=p->rightSibling;}}}30.2.廣度優(yōu)先遍歷遵循的是分層訪問原則。首先訪問樹中深度為0的那一層中的結(jié)點，然后訪問深度為1的那一層中的結(jié)點，……，在訪問每一層結(jié)點的時候，遵循的原則是從左向右，直到樹中所有的結(jié)點都被訪問過。31.3.森林的遍歷主要采用的是深度優(yōu)先方式，同樣可分為先序遍歷和后序遍歷兩種。森林的先序遍歷規(guī)則是：當森林非空時，按從左向右原則訪問森林的第一棵樹（最左樹）的根結(jié)點，然后先序遍歷第一棵樹的子森林，再以先序次序遍歷其他樹組成的森林。如果森林為空，則執(zhí)行空操作。32.ABCDEFGIHJ圖6.4森林的先序遍歷

33.1.4森林與二叉樹的轉(zhuǎn)換二叉樹是一種結(jié)構(gòu)最簡單、運算最簡便的樹形結(jié)構(gòu)。但對許多問題來講，其自然的描述形態(tài)是樹或森林。因此，研究樹、森林和二叉樹之間的關(guān)系是有意義的。樹的左孩子右兄弟表示法就是將一棵樹表示成二叉樹的形態(tài)，這樣就可以將二叉樹中的許多方法應(yīng)用在樹的處理中。反之，將一棵二叉樹的左孩子看成是樹的第一個孩子，右孩子看成是樹的第一個孩子的兄弟，可以將一棵二叉樹還原成一棵普通的樹。34.1.樹轉(zhuǎn)化為二叉樹

從左孩子右兄弟表示法可知，樹中每個結(jié)點最多只有一個最左的孩子和一個右鄰的兄弟，這就是兩者轉(zhuǎn)化操作實現(xiàn)的原理所在。將一棵樹轉(zhuǎn)化為二叉樹的方法如下：(1)樹中所有兄弟之間加一條連線；(2)對樹中的每個結(jié)點，只保留它與第一個孩子之間的連線，刪去它與其他孩子結(jié)點之間的連線；(3)以樹的根結(jié)點為軸心，將整棵樹順時針轉(zhuǎn)動一定的角度（使每個弟弟都變成其哥哥的右孩子），以使其結(jié)構(gòu)層次分明。35.ABCEDFGHIACBEDFGHIABCDEGGFHI圖6.5樹與二叉樹的轉(zhuǎn)換36.2.森林轉(zhuǎn)化為二叉樹森林是若干棵樹的集合，只要將森林中各棵樹的根視為兄弟，每棵樹又可以用二叉樹表示（左孩子右兄弟），這樣森林也可以用二叉樹表示。將森林轉(zhuǎn)化為二叉樹的方法如下：(1)將森林中的每棵樹轉(zhuǎn)化成相應(yīng)的二叉樹；(2)第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點作為前一棵二叉樹根結(jié)點的右孩子，當所有二叉樹連起來后，此時所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。37.ACBDEFGHIJABCDEFGHIJ圖6.6(a)森林與二叉樹的轉(zhuǎn)換38.ABCDEFGHIJ圖6.6(b)森林與二叉樹的轉(zhuǎn)換39.

§2哈夫曼樹

▲哈夫曼樹的應(yīng)用▲哈夫曼樹的基本概念▲哈夫曼樹的構(gòu)造算法▲哈夫曼編碼▲哈夫曼樹的實現(xiàn)40.2.1哈夫曼樹的應(yīng)用

在數(shù)據(jù)膨脹、信息爆炸的今天，數(shù)據(jù)壓縮的意義不言而喻。談到數(shù)據(jù)壓縮，就不能不提到哈夫曼／霍夫曼（Huffman）編碼。哈夫曼編碼是一種有關(guān)數(shù)據(jù)壓縮的算法，它也是首個實用的壓縮編碼方案，該算法由哈夫曼（D.A.Huffman）于1952年提出。當時，哈夫曼就讀于麻省理工學(xué)院，為了向老師證明自己可以不參加某門功課的期末考試，他設(shè)計了這個看似簡單卻影響深遠的編碼方法。哈夫曼編碼效率高，運算速度快，實現(xiàn)方式靈活。從20世紀60年代開始，哈夫曼編碼在數(shù)據(jù)壓縮領(lǐng)域得到了廣泛應(yīng)用。而20世紀80年代初，哈夫曼編碼又出現(xiàn)在CP/M和DOS系統(tǒng)中，即使在當今的許多知名的壓縮工具和壓縮算法里，依然可以見到哈夫曼編碼的影子。41.文本處理是計算機的重要應(yīng)用之一。文本由字符組成。在計算機中每個字符用一個由0，1組成的二進制串表示，稱之為編碼。大多數(shù)計算機采用ASCII編碼。ASCII編碼是一種等長的編碼，每個字符的編碼長度是相同的。為了提高文本存儲和處理的效率，在某些場合希望采用不等長的編碼，讓使用頻率較高的字符有較短的編碼，而使用頻率較低的字符有較長的編碼，總體來講，保存文本的空間總量會減少，傳送文本的速度也會提高。42.例如給出一段文本：ABCDEACBDBDBDBCB在該文本中出現(xiàn)的字符集合為｛A,B,C,D,E｝，其中B出現(xiàn)的次數(shù)最多，為6次；其它依次為D＝4次，C=3次，A=2次，E=1次。首先采用定長編碼方法。要給5個字符進行編碼，最少需要三位二進制碼。可以給每個字符賦一個等長的三位二進制的編碼為A:000B:001C:010D:011E:100，將原始文本進行編碼后所得結(jié)果如下：000001010011100000010001011001011001011001010001編碼長度為57(bit)43.另一種方案是采用非等長編碼，將出現(xiàn)頻率最高的B用最少的編碼來表示，D用次少的編碼來表示，依次類推。如上述5個字符的二進制編碼為B:0D:10C:110A:1110E:1111，將原始文本進行編碼后所得結(jié)果如下：11100110101111111011001001001001100編碼長度為41(bit)顯然，采用非等長編碼可以減少文本占用的存儲空間。但怎樣找出這種優(yōu)化的編碼呢？44.哈夫曼提出可用一種特定的二叉樹來生成優(yōu)化編碼，這種二叉樹被稱為哈夫曼樹，也稱最優(yōu)二叉樹，由哈夫曼樹生成的編碼稱為哈夫曼編碼。哈夫曼編碼不僅可應(yīng)用于文本編碼，也同樣可應(yīng)用于圖象編碼等領(lǐng)域中。45.2.2哈夫曼樹的基本概念■路徑：從樹的一個結(jié)點到另一個結(jié)點的分支（邊）構(gòu)成這兩個結(jié)點之間的路徑。對于哈夫曼樹特指從根結(jié)點到某結(jié)點的路徑。■路徑長度：路徑上的分支數(shù)目（邊數(shù)）。樹的路徑長度：從樹根到每一結(jié)點的路徑長度之和。■權(quán)：賦予某個事物的一個量，是對事物的某個（些）屬性的數(shù)值化描述。在數(shù)據(jù)結(jié)構(gòu)中，包括結(jié)點權(quán)和邊權(quán)兩類，它們的具體意義由具體情況決定。■結(jié)點的帶權(quán)路徑長度：結(jié)點的路徑長度與結(jié)點上權(quán)的乘積。46.■樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點的帶權(quán)路徑長度（weightedpathlength）之和。記做WPL＝∑wili其中，wi是第i個葉子的權(quán)值，li是第i個葉子的路徑長度（i=1,2,…,n）。■哈夫曼樹：設(shè)有結(jié)點集合K={k1,k2,…,kn}，并以k1,k2,…,kn為葉子結(jié)點構(gòu)造二叉樹，如果它們的權(quán)值分別為w1,w2,…,wn，那么稱使得該二叉樹的WPL值最小的二叉樹為哈夫曼樹（最優(yōu)二叉樹）。47.例如，有4個權(quán)值分別為1、6、8、9的結(jié)點A、B、C、D，可以構(gòu)造出以它們?yōu)槿~子結(jié)點的多個二叉樹，如圖6.7。對于這三棵二叉樹，它們的帶權(quán)路徑長度如下：(a)WPL=9×2＋8×2＋1×2＋6×2＝48(b)WPL=9×3＋8×3＋1×1＋6×2＝64(c)WPL=9×1＋8×2＋1×3＋6×3＝46

可見二叉樹(c)的WPL值最小，這正是一棵哈夫曼樹。48.918616896981ABCDDACBBACD圖6.7具有不同帶權(quán)路徑長度的二叉樹(a)WPL=48(b)WPL=64(c)WPL=4649.由此可見，由相同權(quán)值的一組葉子接點所構(gòu)成的二叉樹有不同的形態(tài)和不同的帶權(quán)路徑長度WPL。那么，如何找到WPL最小的二叉樹（哈夫曼樹）呢？根據(jù)哈夫曼樹的定義，一棵二叉樹要使其WPL值最小，必須使權(quán)值越大的葉子接點越靠近根接點，而權(quán)值越小的葉子結(jié)點越遠離根結(jié)點。50.2.3哈夫曼樹的構(gòu)造算法算法可描述如下：(1)根據(jù)給定的n個權(quán)值w1,w2,…,wn，構(gòu)造由n棵二叉樹構(gòu)成的森林F={T1,T2,…,Tn}，其中每棵二叉樹Ti

都是只含有一個帶權(quán)值為wi的根結(jié)點。(2)從森林f中選取兩棵權(quán)值最小的二叉樹Ti

和Tj，分別作為左右子樹構(gòu)造一棵新的二叉樹，并置新二叉樹的根結(jié)點r的權(quán)值為wr=wi+wj

。(3)從森林F中刪去Ti和Tj

，而把新二叉樹r加入到F中。(4)重復(fù)步驟2和步驟3，直到F中只含一棵二叉樹為止。這棵二叉樹便是所要建立的哈夫曼樹。51.9816987169158716249158716圖6.8哈夫曼樹的構(gòu)造過程

52.2.4哈夫曼編碼

哈夫曼樹是哈夫曼編碼的基礎(chǔ)，利用哈夫曼樹可以構(gòu)造哈夫曼編碼。哈夫曼編碼的基本原理是：對頻繁使用的字符用較短的代碼代替，而對較少使用的字符用較長的代碼代替，這樣就可以使文件中的編碼數(shù)減少到最小。因此，哈夫曼編碼是一種非等長的并使文件的編碼總長為最短的編碼方案。53.利用構(gòu)建哈夫曼樹的方法可以得到文件的哈夫曼編碼。下面給出哈夫曼編碼算法的基本思路：(1)對需要編碼的文件統(tǒng)計出它的字符集{C1,C2,…,Cn}，并統(tǒng)計出各個字符在文件中出現(xiàn)的次數(shù)或頻率，如為｛w1,w2,…,wn｝。(2)以C1,C2,…,Cn作為葉子結(jié)點，w1,w2,…,wn作為結(jié)點的權(quán)值，構(gòu)造一棵哈夫曼樹。(3)規(guī)定哈夫曼樹中的左分支代表0，右分支代表1，則從根結(jié)點到每個葉子結(jié)點所經(jīng)過的路徑分支組成的0和1的序列便為該葉子結(jié)點所對應(yīng)字符的哈夫曼編碼。54.例如，某文本的字符集及各自的頻率為：A(1),B(9),C(6),D(8)，將它們構(gòu)造成一棵哈夫曼樹，于是便可得到A、B、C、D的哈夫曼編碼，如圖6.9所示。55.8169249158716圖6.9哈夫曼編碼的生成過程

BDAC100011哈夫曼編碼

A:110B:0C:111D:1056.

在構(gòu)建編碼的二叉樹時必須將字符結(jié)點作為葉子結(jié)點，否則會產(chǎn)生具有二義性的編碼。例如，有人為字符集合A(1),B(9),C(6),D(8)建立了如下圖所示的一棵二叉樹，從而得到的編碼是A:01B:010C:001D:10198657.在該方案中，字符A的編碼01是字符B的編碼010的前綴部分，這樣對于代碼串0101001，既是AAC的代碼，也是ABD和BDA的代碼，因此，這樣的編碼不能保證譯碼的唯一性，被稱之為具有二義性的編碼。然而，采用哈夫曼編碼則不會產(chǎn)生二義性問題。因為，在哈夫曼樹中每個字符結(jié)點都是葉子結(jié)點，它們不可能在根結(jié)點到其他字符結(jié)點的路徑上，所以一個字符的哈夫曼編碼不可能是另一個字符的哈夫曼編碼的前綴，從而保證了譯碼的非二義性。58.2.5哈夫曼樹類的實現(xiàn)

1.基本思路為了找出一組符號（字符、圖象符號等）的哈夫曼編碼，可以定義一個哈夫曼樹類。哈夫曼樹類的對象可以接受一組符號以及對應(yīng)的權(quán)值，并返回每個符號的哈夫曼編碼。因此，哈夫曼樹類應(yīng)該提供兩個public操作：MakeHfmTree和GetHfmCode。MakeHfmTree操作接受一組待編碼的符號以及相應(yīng)的權(quán)值，構(gòu)造一棵哈夫曼樹。GetHfmCode操作根據(jù)生成的哈夫曼樹為每個葉子結(jié)點生成并返回哈夫曼編碼。59.實現(xiàn)哈夫曼樹類的兩個重要問題是：■如何設(shè)計哈夫曼樹結(jié)點?■如何構(gòu)造并保存哈夫曼樹?

下面給出解決上述問題的一種方案。(1)哈夫曼樹結(jié)點可包括：符號值、符號的權(quán)值、左孩子指針、右孩子指針及父結(jié)點指針。60.(2)在哈夫曼樹中，每個待編碼的符號對應(yīng)的是一個葉子結(jié)點，其他結(jié)點都是度為2的結(jié)點。只要給定了待編碼的符號個數(shù)n，由n0=n2+1可知哈夫曼樹的規(guī)模為2n-1。鑒于這些特性，可以考慮用一個長度為2n-1的結(jié)點數(shù)組forest來構(gòu)造哈夫曼樹。初始時，葉子結(jié)點依次存放在forest中的n到2n-1的數(shù)組元素中，它們的parent值均為0，表示所有的樹都只有根結(jié)點。第一次歸并在n到2n-1的數(shù)組元素中查找權(quán)值最小和次小的樹，歸并后的樹的根結(jié)點存放在數(shù)組元素forest[n-1]中，并設(shè)置父子關(guān)系。第二次歸并后的樹的根結(jié)點存放在數(shù)組元素forest[n-2]中……。最后一次歸并的結(jié)果存放在數(shù)組元素forest[1]中。至此，在forest中便生成了一棵哈夫曼樹，數(shù)組元素forest[1]是該哈夫曼樹的根結(jié)點。61.2.哈夫曼樹類的定義

template<typenameType>structHfmNode{//哈夫曼樹結(jié)點的類型Typedata;//符號值intweight;//符號的權(quán)值intparent,leftChild,rightChild;//父及左右孩子的下標值};template<typenameType>structHfmCode{//哈夫曼編碼的類型Typedata;//待編碼的符號stringcode;//對應(yīng)的哈夫曼編碼};62.template<typenameType>classHfmTree{//哈夫曼樹類private:HfmNode*forest;//哈夫曼樹結(jié)點數(shù)組，用于構(gòu)造并保存哈夫曼樹intsize;//待編碼的符號個數(shù)（葉子結(jié)點個數(shù)）HfmCode*hfm_code;//哈夫曼編碼數(shù)組intMinTree(intpos);//查找森林中的最小樹public:HfmTree(intn){//n為待編碼的符號個數(shù)size=n;forest=newHfmNode<Type>[size*2-1];//為森林分配空間hfm_code=newHfmCode<Type>[size];//為編碼數(shù)組分配空間}~HfmTree(){delete[]forest;}voidMakeHfmTree(Type*datas,int*w);//構(gòu)造哈夫曼樹voidGetHfmCode(stringcode[]);//生成并返回哈夫曼編碼}63.3.構(gòu)造哈夫曼樹的算法實現(xiàn)voidMakeHfmTree(Type*datas,int*w){//datas為待編碼的符號數(shù)組，w為權(quán)值數(shù)組intx,y;//最小樹、次最小樹的下標intk=size*2-1;//初始化森林for(inti=size;i<=k;i++){forest[i].weight=w[i-size+1];forest