紅樓夢賈家家譜6.1樹的類型定義6.2二叉樹6.3

遍歷二叉樹和線索二叉樹6.4樹和森林6.6哈夫曼樹及其應用第6章樹和二叉樹6.1樹的類型定義數據對象D：D是具有相同特性的數據元素的集合。

若D為空集，則稱為空樹。否則:(1)在D中存在唯一的稱為根的數據元素root；

(2)當n>1時，其余結點可分為m(m>0)個互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹。

數據關系R：ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2樹根例如:樹形圖表示的例子ABKELFDHMJICG嵌套集合表示法ABCDEKLFGHIJM凹入表示法（A(B(E(K,L),F),C(G),D(H(M),I,J)))廣義表表示法ABCDEFGHIJMKL對比樹型結構和線性結構的結構特點~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結構樹型結構第一個數據元素

(無前驅)

根結點

(無前驅)最后一個數據元素

(無后繼)多個葉子結點

(無后繼)其它數據元素(一個前驅、一個后繼)其它數據元素(一個前驅、多個后繼)基本術語結點:結點的度:樹的度:葉子結點:分支結點:一個數據元素+若干指向子樹的分支分支的個數樹中所有結點的度的最大值度為零的結點度大于零的結點DHIJM(從根到結點的)路徑：孩子結點、雙親結點兄弟結點、堂兄弟祖先結點、子孫結點結點的層次:樹的深度：

由從根到該結點所經分支和結點構成ABCDEFGHIJMKL假設根結點的層次為1，第l層的結點的子樹根結點的層次為l+1樹中葉子結點所在的最大層次(１)有確定的根；(２)樹根和子樹根之間為有向關系。有向樹：有序樹：子樹之間存在確定的次序關系。無序樹：子樹之間不存在確定的次序關系。任何一棵非空樹是一個二元組

Tree=（root，F）其中：root被稱為根結點

F被稱為子樹森林森林：是m（m≥0）棵互不相交的樹的集合ArootBCDEFGHIJMKLF6.2

二叉樹的類型定義

二叉樹或為空樹，或是由一個根結點加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。ABCDEFGHK根結點左子樹右子樹二叉樹的五種基本形態：N空樹只含根結點NNNLRR右子樹為空樹L左子樹為空樹左右子樹均不為空樹二叉樹

的重要特性

性質1：

在二叉樹的第i

層上至多有2i-1個結點。(i≥1)用歸納法證明：

i=1

層時，只有一個根結點：

2i-1=20=1；二叉樹中第5層上的結點個數最多為____A.8 B.15

C.16 D.32性質2：

深度為k的二叉樹上至多含2k-1個結點（k≥1）。證明：

基于上一條性質，深度為k的二叉樹上的結點數至多為

20+21+

+2k-1=2k-1

。深度為5的二叉樹至多有（

）結點。A．64 B．32C．31 D．63

性質3：

對任何一棵二叉樹，若它含有n0個葉子結點、n2個度為

2

的結點，則必存在關系式：n0=n2+1。證明：設二叉樹上結點總數n=n0+n1+n2又二叉樹上分支總數b=n1+2n2

而b=n-1=n0+n1+n2-1由此，n0=n2+1。度為1的結點1、一棵二叉樹有67個結點,這些結點的度要么是0，要么是2。這棵二叉樹中度數為2的結點有

個。兩類特殊的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個結點的二叉樹。完全二叉樹：樹中所含的n個結點和滿二叉樹中編號為1至n的結點一一對應。123456789101112131415abcdefghij

性質4：

具有n個結點的完全二叉樹的深度為

log2n+1。證明：設完全二叉樹的深度為k則根據第二條性質得2k-1-1<n≤2k

-1計算得出：2k-1≤n<2k即

k-1≤log2n<k

因為k只能是整數，因此，k=log2n

+1。性質5：若對含n個結點的完全二叉樹從上到下且從左至右進行1

至n

的編號，則對完全二叉樹中任意一個編號為i

的結點：

(1)若i=1，則該結點是二叉樹的根，無雙親，否則，編號為i/2的結點為其雙親結點；

(2)若2i>n，則該結點無左孩子，

否則，編號為2i的結點為其左孩子結點；

(3)若2i+1>n，則該結點無右孩子結點，

否則，編號為2i+1的結點為其右孩子結點。1.將一棵有100個結點的完全二叉樹從上到下，從左到右依次對結點進行編號，根結點的編號為1，則編號為49的結點的左孩子的編號為______。A.98 B.99C.50 D.486.3二叉樹的存儲結構二、二叉樹的鏈式存儲表示一、二叉樹的順序存儲表示例如:ABCDEF

ABDCEF

0123456789101112131401326一、二叉樹的順序存儲表示二、二叉樹的鏈式存儲表示1.二叉鏈表2．三叉鏈表ADEBCFrootlchilddatarchild結點結構:1.二叉鏈表typedefstruct

BiTNode

{//結點結構

TElemTypedata;

structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;lchilddatarchild結點結構:C語言的類型描述如下:ADEBCFroot2．三叉鏈表parent

lchilddatarchild結點結構:

typedefstruct

TriTNode

{//結點結構

TElemTypedata;

structTriTNode*lchild,*rchild;//左右孩子指針

structTriTNode

*parent;//雙親指針

}TriTNode,*TriTree;parentlchilddatarchild結點結構:C語言的類型描述如下:6.4二叉樹的遍歷

順著某一條搜索路徑巡訪二叉樹中的結點，使得每個結點均被訪問一次，而且僅被訪問一次。一、問題的提出“訪問”的含義可以很廣，如：輸出結點的信息等。

“遍歷”是任何類型均有的操作，對線性結構而言，只有一條搜索路徑(因為每個結點均只有一個后繼)，不需要另加討論。而二叉樹是非線性結構。

二叉樹每個結點有兩個后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。二、按層次遍歷二叉樹

實現方法為從上層到下層，每層中從左側到右側依次訪問每個結點。下面我們將給出一棵二叉樹及其按層次順序訪問其中每個結點的遍歷序列。按層次遍歷該二叉樹的序列為：

ABECFDGHKABCDEFGHK三、先左后右的遍歷算法先（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法

若二叉樹為空樹，則空操作；否則，（1）訪問根結點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。先（根）序的遍歷算法：四、算法的遞歸描述voidPreorder(BiTreeT,void(*visit)(TElemType&e)){//

先序遍歷二叉樹

if(T){

visit(T->data);//訪問結點

Preorder(T->lchild,visit);//遍歷左子樹

Preorder(T->rchild,visit);//遍歷右子樹

}}ABCDEFGD

L

RTD

L

RD

L

RABED

L

RD

L

RDLRDLRCFDG先序遍歷結果:ABCDEFGT

若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結點；（3）中序遍歷右子樹。中（根）序的遍歷算法：voidInorder(BiTreeT,

void(*visit)(TElemType&e)){//

中序遍歷二叉樹

if(T){

Inreorder(T->lchild,visit);//遍歷左子樹

visit(T->data);//訪問結點

Inreorder(T->rchild,visit);//遍歷右子樹

}}ABCDEFGL

D

RTL

D

RL

D

RABEL

D

RLD

RLDRLDRCFDG中序遍歷結果:BDCAGFET

若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結點。后（根）序的遍歷算法：voidPostorder(BiTreeT,

void(*visit)(TElemType&e)){//

后序遍歷二叉樹

if(T){

Postreorder(T->lchild,visit);//遍歷左子樹

Postreorder(T->rchild,visit);//遍歷右子樹

visit(T->data);//訪問結點

}}ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA練習：設二叉樹結點的先序序列為ABDECFGH，中序序列為DEBAFCHG,則二叉樹的后序序列是

。

五、中序遍歷算法的非遞歸描述

中序遍歷示意圖圖中序遍歷二叉樹的非遞歸算法處理流程

算法思想為：從二叉樹根結點開始，沿左子樹一直走到末端(左孩子為空)為止，在走的過程中，把依次遇到的結點進棧,待左子樹為空時,從棧中退出結點并訪問,然后再轉向它的右子樹。如此重復，直到棧空或指針為空止。ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B訪問：C(4)中序遍歷非遞歸算法pABCDEFGiP->A訪問：CB(5)ABCDEFGiP->AP->D訪問：CBp(6)ABCDEFGiP->AP->DP->E訪問：CBp(7)ABCDEFGiP->AP->D訪問：CBEp(8)ABCDEFGiP->AP->DP->G訪問：CBEP=NULL(9)ABCDEFGiP->A訪問：CBEGDp(11)ABCDEFGiP->AP->F訪問：CBEGDp(12)ABCDEFGiP->AP->D訪問：CBEGp(10)ABCDEFGiP->A訪問：CBEGDFp=NULL(13)ABCDEFGi訪問：CBEGDFAp(14)ABCDEFGi訪問：CBEGDFAp=NULL(15)算法一：StatusInorderTraverse(BitreeT,Status(*Visit)(TElemTypee)){

InitStack(S);Push(S,T);//根指針進棧

while(!StackEmpty(S)){

while(GetTop(S,p)&&p)Push(S,p->lchild);

//向左走到盡頭

Pop(S,p);

//空指針退棧

if(!StackEmpty(S)){//訪問結點，向右一步

Pop(S,p);if(!Visit(p->data))returnERROR; Push(S,p->rchild); }}returnOK;}StatusInorderTraverse(BitreeT,Status(*Visit)(TElemTypee)){

InitStack(S);p=T;while(p||!StackEmpty(S)){

if(p){Push(S,p);p=p->lchild;}

//根指針進棧，遍歷左子樹

else{//根指針退棧，訪問根結點

Pop(S,p);if(!Visit(p->data))returnERROR; p=p->rchild; }}returnOK;}算法二：六、遍歷算法的應用舉例2、統計二叉樹中葉子結點的個數(先序遍歷)3、求二叉樹的深度(后序遍歷)1、輸入結點值，構造二叉樹(先序遍歷）1、輸入結點值，構造二叉樹算法基本思想:

先序(或中序或后序)遍歷二叉樹，讀入一個字符，若讀入字符為空，則二叉樹為空,若讀入字符非空，則生成一個結點。將算法中“訪問結點”的操作改為：生成一個結點，輸入結點的值。VoidCreateBiTree

(BiTree*T){charch;scanf(“%c”&ch);if(ch＝＝’’)

（*T）=NULL;

else{if(!(（*T）=(BiTNode*)malloc(sizeof(BiTNode)))

exit(0);

（*T）->data=ch;//生成根結點

CreateBiTree(&（*T）->lchild);//構造左子樹

CreateBiTree(&（*T）>rchild);//構造右子樹

}}//CreateBiTree2、統計二叉樹中葉子結點的個數算法基本思想:

先序(或中序或后序)遍歷二叉樹，在遍歷過程中查找葉子結點，并計數。由此，需在遍歷算法中增添一個“計數”的參數，并將算法中“訪問結點”的操作改為：若是葉子，則計數器增1。void

CountLeaf

(BiTreeT,int&count){

if(T){

if

((!T->lchild)&&

(!T->rchild))count++;//對葉子結點計數

CountLeaf(T->lchild,count);

CountLeaf(T->rchild,count);

}}

3、求二叉樹的深度(后序遍歷)算法基本思想:

從二叉樹深度的定義可知，二叉樹的深度應為其左、右子樹深度的最大值加1。由此，需先分別求得左、右子樹的深度，算法中“訪問結點”的操作為：求得左、右子樹深度的最大值，然后加1。

首先分析二叉樹的深度和它的左、右子樹深度之間的關系。int

Depth(BiTreeT){//返回二叉樹的深度

if(!T)depthval=0;else{depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);

depthval=1+(depthLeft>depthRight?depthLeft:depthRight);

}

returndepthval;}6.3.2線索二叉樹

何謂線索二叉樹？線索鏈表的遍歷算法如何建立線索鏈表？一、何謂線索二叉樹？遍歷二叉樹的結果是，求得結點的一個線性序列。ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA指向該線性序列中的“前驅”和“后繼”的指針，稱作“線索”與其相應的二叉樹，稱作“線索二叉樹”包含“線索”的存儲結構，稱作“線索鏈表”ABCDEFGHK^D^

C^^B

E^線索鏈表的結點結構

ltag和rtag是增加的兩個標志域，用來區分結點的左、右指針域是指向其左、右孩子的指針，還是指向其前驅或后繼的線索。

lchildLTagdataRTagrchild例如：ABCDEABDCET中序序列：BCAED中序線索二叉樹00001111^11^ABCDE0A01B00D11C11E1T中序序列：BCAED帶頭結點的中序線索二叉樹

0

1頭結點：ltag=0,lchild指向根結點rtag=1,rchild指向遍歷序列中最后一個結點遍歷序列中第一個結點的lchild域和最后一個結點的rchild域都指向頭結點ABDCET中序序列：BCAED中序線索二叉樹00001111^11^二、線索鏈表的遍歷算法:由于在線索鏈表中添加了遍歷中得到的“前驅”和“后繼”的信息，從而簡化了遍歷的算法。例如:

對中序線索化鏈表的遍歷算法

※中序遍歷的第一個結點？

※在中序線索化鏈表中結點的后繼？左子樹上處于“最左下”（沒有左子樹）的結點。若無右子樹，則為后繼線索所指結點；否則為對其右子樹進行中序遍歷時訪問的第一個結點。voidInOrderTraverse_Thr(BiThrTreeT,

void(*Visit)(TElemTypee))

{p=T->lchild;//p指向根結點

while(p!=T){//空樹或遍歷結束時，p==T

while(p->LTag==Link)p=p->lchild;//先找到中序遍歷起點

if(!Visit(p->data))returnERROR;//訪問其左子樹為空的結點

while(p->RTag==Thread&&p->rchild!=T)

{p=p->rchild;Visit(p->data);}//訪問后繼結點

p=p->rchild;//當前結點右域不空或已經找好了后繼，則一律從結點的右子樹開始重復{}的全部過程

}}//InOrderTraverse_Thr

在中序遍歷過程中修改結點的左、右指針域，以保存當前訪問結點的前驅”和“后繼”信息。遍歷過程中，附設指針pre,并始終保持指針pre指向當前訪問的、指針p所指結點的前驅。三、如何建立線索鏈表？線索二叉樹的生成算法目的：在依某種順序遍歷二叉樹時修改空指針，添加前驅或后繼。注解：為方便添加結點的前驅或后繼，需要設置兩個指針：

p指針→當前結點之指針；pre指針→前驅結點之指針。技巧：當結點p的左/右域為空時，只改寫它的左域（裝入前驅pre），而其右域（后繼）留給下一結點來填寫。或者說，當前結點的指針p應當送到前驅結點的空右域中。若p->lchild＝NULL,則{p->Ltag=1;p->lchild＝pre;}//p的前驅結點指針pre存入左空域若pre->rchild＝NULL,則{pre->Rtag＝1;pre->rchild=p;}//p存入其前驅結點pre的右空域void

InThreading(BiThrTreep)

{

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=p;//保持pre指向p的前驅

InThreading(p->rchild);

//右子樹線索化

}//if}//InThreadingStatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//構建中序線索鏈表

if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))

exit(OVERFLOW);Thrt->LTag=Link;Thrt->RTag=Thread;//建頭結點

Thrt->rchild=Thrt;//右指針回指

if(!T)

Thrt->lchild=Thrt;

//若二叉樹空，則左指針回指else{Thrt->lchild=T;

pre=Thrt;InThreading(T);//中序遍歷進行中序線索化

pre->rchild=Thrt;pre->RTag=Thread;

//最后一個結點線索化

Thrt->rchild=pre;

}

returnOK;}//InOrderThreading

6.4樹和森林樹的三種存儲結構一、雙親表示法二、孩子鏈表表示法三、樹的二叉鏈表(孩子-兄弟）存儲表示法ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5r=0n=7dataparent一、雙親表示法:

typedefstructPTNode{Elemdata;

intparent;//雙親位置域

}PTNode;

dataparent#defineMAX_TREE_SIZE100結點結構:C語言的類型描述:typedefstruct{PTNodenodes[MAX_TREE_SIZE];

int

r,n;//根結點的位置和結點個數

}PTree;樹結構:ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

4r=0n=7dataparentfirstchild123456二、孩子鏈表表示法:-1000224typedefstructCTNode{

intchild;

structCTNode*next;

}*ChildPtr;孩子結點結構:

childnextC語言的類型描述:

typedefstruct{Elemdata;ChildPtrfirstchild;//孩子鏈的頭指針

}CTBox;雙親結點結構

datafirstchildtypedefstruct{CTBoxnodes[MAX_TREE_SIZE];

intn,r;//結點數和根結點的位置

}CTree;樹結構:三、樹的二叉鏈表(孩子-兄弟）存儲表示法ABCDEFGABCEDFGrootABCEDFG

typedefstructCSNode{Elemdata;

struct

CSNode*firstchild,*nextsibling;}CSNode,*CSTree;C語言的類型描述:結點結構:

firstchilddatanextsibling樹與二叉樹轉換ACBED樹ABCDE二叉樹A^^BC^D^^E^A^^BC^D^^E^A^^BC^D^^E^對應存儲存儲解釋解釋將樹轉換成二叉樹加線：在兄弟之間加一連線抹線：對每個結點，除了其左孩子外，去除其與其余孩子之間的關系旋轉：以樹的根結點為軸心，將整樹順時針轉45°ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI樹轉換成的二叉樹其右子樹一定為空樹根結點X的第一個孩子結點X緊鄰的右兄弟二叉樹根結點X的左孩子結點X的右孩子樹與二叉樹的轉換將二叉樹轉換成樹加線：若p結點是雙親結點的左孩子，則將p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都與p的雙親用線連起來抹線：抹掉原二叉樹中雙親與右孩子之間的連線調整：將結點按層次排列，形成樹結構ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI森林轉換成二叉樹將各棵樹分別轉換成二叉樹將每棵樹的根結點用線相連以第一棵樹根結點為二叉樹的根，再以根結點為軸心，順時針旋轉，構成二叉樹型結構ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ二叉樹轉換成森林抹線：將二叉樹中根結點與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹還原：將孤立的二叉樹還原成樹ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ

由此，樹的各種操作均可對應二叉樹的操作來完成。

應當注意的是，和樹對應的二叉樹，其左、右子樹的概念已改變為：

左是孩子，右是兄弟。6.6哈夫曼樹與

哈夫曼編碼

最優樹(哈夫曼樹)的定義

如何構造最優樹

前綴編碼哈夫曼編碼

一、最優樹的定義樹的路徑長度定義為：

樹中每個結點的路徑長度之和。

結點的路徑長度定義為：

從根結點到該結點的路徑上分支的數目。

樹的帶權路徑長度定義為：

樹中所有葉子結點的帶權路徑長度之和

WPL(T)=wklk(對所有葉子結點)。

在所有含n個葉子結點、并帶相同權值的m叉樹中，必存在一棵其帶權路徑長度取最小值的樹，稱為“最優樹”。例如：WPL(T)=72+52+22+42=36WPL(T)=71+52+23+43=35WPL(T)=73+53+42+21=46

根據給定的n個權值{w1,w2,…,wn}，構造n棵二叉樹的集合

F={T1,T2,…,Tn}，其中每棵二叉樹Ti中均只含一個帶權值為wi的根結點，其左、右子樹為空樹；二、如何構造最優樹(1)(哈夫曼算法)以二叉樹為例：

在F中選取其根結點的權值為最小的兩棵二叉樹，分別作為左、右子樹構造一棵新的二叉樹，并置這棵新的二叉樹根結點的權值為其左、右子樹根結點的權值之和；(2)

從F中刪去這兩棵樹，同時加入剛生成的新樹；

重復

(2)

和

(3)

兩步，直至F中只含一棵樹為止。這棵樹便是哈夫曼樹(3)(4)9例如:已知權值W={5,6,2,9,7}562752769767139527952716671329注意：

①n個葉子的哈夫曼樹要經過n-1次合并，產生n-1個新結點。最終求得的哈夫曼樹中共有2n-1個結點。

②哈夫曼樹是嚴格的二叉樹，沒有度數為1的分支結點。前綴編碼

在電文傳輸中，需要將電文中出現的每個字符進行二進制編碼。在設計編碼時需要遵守兩個原則：（1）發送方傳輸的二進制編碼，到接收方解碼后必須具有唯一性，即解碼結果與發送方發送的電文完全一樣；（2）發送的二進制編碼盡可能地短。下面我們介紹兩種編碼的方式。

1.等長編碼

這種編碼方式的特點:

每個字符的編碼長度相同。設字符集只含有4個字符A，B，C，D，用兩位二進制表示的編碼分別為00，01，10，11。若現在電文為：ABACCDA，則應發送二進制序列：00010010101100，總長度為14位。當接收方接收到這段電文后，將按兩位一段進行譯碼。這種編碼的特點:譯碼簡單且具有唯一性，但編碼長度并不是最短的。2.不等長編碼

在傳送電文時，為了使其二進制位數盡可能地少，可以將每個字符的編碼設計為不等長的，使用頻度較高的字符分配一個相對比較短的編碼，使用頻度較低的字符分配一個比較長的編碼。例如，可以為A，B，C，D四個字符分別分配0，00，1，01，并可將上述電文用二進制序列：000011010發送，其長度只有9個二進制位。問題：接收方接到這段電文后無法進行譯碼，因為無法斷定前面4個0是4個A，1個B、2個A，還是2個B，即譯碼不唯一，因此這種編碼方法不可使用。CDBA111000A:0B:10C:110D:111電文為：ABACCDA發送二進制序列：01001101101110

利用哈夫曼樹可以構造一種不等長的二進制編碼，并且構造所得的哈夫曼編碼是一種最優前綴編碼，即使所傳電文的總長度最短。稱為哈夫曼編碼哈夫曼編碼（1）利用字符集中每個字符的使用頻率作為權值構造一個哈夫曼樹；（2）從根結點開始，為到每個葉子結點路徑上的左分支賦予0，右分支賦予1，并從根到葉子方向形成該葉子結點的編碼。哈夫曼編碼的構造方法：例如：

假設有一個電文字符集中有8個字符，每個字符的使用頻率分別為{0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11}，現以此為例設計哈夫曼編碼。為方便計算，將所有字符的頻度乘以100，使其轉換成整型數值集合，得到{5,29,7,8,14,23,3,11}；哈夫曼編碼設計如下圖：115297814233100011558290001118421900011100010011001111110111111010Weightparentlchildrchild12345678910111213141552978142331101234567W529870000000000000000000000000000000000000000000001423311999178101034151111128191414121313151552942581002101161412130HC0cd01234567123456780011↑start00111111111111111000000001求哈夫曼編碼過程的實例:HT數組哈夫曼樹的存儲結構

用一個大小為2n-1的一維數組來存儲哈夫曼樹中的結點，其存儲結構為：

typedefstruct{

//結點類型

intweight；

//權值，不妨設權值均大于零

intlchild，rchild，parent；

//左右孩子及雙親指針

}HTNode，*HuffmanTree;//動態分配數組存儲哈夫曼樹Typedefchar**Huffmancode;//動態分配數組存儲哈夫曼編碼表哈夫曼編碼的存儲結構

if(n<=1)return;

m=2*n-1;

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0號單元未用

求哈夫曼編碼的算法:for(p=HT+1,i=1;i<=n;++i,++p,++w)*p={*w,0,0,0}

for(;i<=m;++i,++p)

*p={0,0,0,0}

for(i=n+1