6樹和二叉樹

樹形結(jié)構是一類非常重要的非線性數(shù)據(jù)結(jié)構，是以分支關系定義的層次結(jié)構。在計算機領域中有著廣泛的應用。本章重點討論二叉樹的存儲結(jié)構及各種操作、樹和森林與二叉樹之間的轉(zhuǎn)換關系，最后給出一些應用實例。6.1樹的基本概念一、樹的定義

樹是n(n>=0)個結(jié)點的有限集。在任意一棵非空樹中：（1）有且僅有一個根結(jié)點；（2）除根結(jié)點外，其余的結(jié)點可分為m(m>=0)個互不相交的子樹。ABCDEFGHIJKLM子樹根結(jié)點ABCDEFGHIJKLM子樹根結(jié)點二、術語結(jié)點：包含一個數(shù)據(jù)元素及若干指向其子樹的分支結(jié)點的度：子樹個數(shù)樹的度:樹中最大的結(jié)點度數(shù)葉子（K,L,F,G,M,I,J）分枝結(jié)點結(jié)點的層數(shù)、樹的層數(shù)父結(jié)點、孩子結(jié)點兄弟、堂兄弟祖先、子孫樹的高度或深度路徑和路徑長度有序樹與無序樹

森林是m（m>=0）棵互不相交的樹的集合。一、二叉樹的定義

或空，或由根和互不相交的左、右子樹構成。二、基本形態(tài)6.2二叉樹

6.2.1基本概念

二叉樹示例:abcdfgeacdg

思考[1]樹與二叉樹有什么區(qū)別?

畫出3個結(jié)點的樹和3個結(jié)點的二叉樹。abcacd3個結(jié)點的二叉樹:3個結(jié)點的樹abcacdacdacdacd

思考[1]樹與二叉樹有什么區(qū)別?

畫出3個結(jié)點的樹和3個結(jié)點的二叉樹。[2]度為2的樹是二叉樹嗎?反之呢？[3]n個結(jié)點的樹的最大深度是多少?最小深度?[4]n個結(jié)點的二叉樹的最大深度是多少?最小深度?性質(zhì)1：在二叉樹的第i(i>0)層上至多有2i-1個結(jié)點。性質(zhì)2：深度為k的二叉樹中至多有2k-1個結(jié)點(k>0)。性質(zhì)3：對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0,度為2的結(jié)點數(shù)為n2，則n0=n2+1。6.2.2二叉樹的性質(zhì)性質(zhì)3的證明：證明：設n為二叉樹中的結(jié)點總數(shù)，n1為二叉樹中度為1的結(jié)點個數(shù)。則有：

n=n0+n1+n2(1)

考察二叉樹的分支情況:

B=n-1=2n2+n1(2)

由(2)得：n=2n2+n1+1(3)

由（1）和（3）得：n0=n2+1

abcdgefn2=2,n0=3,n1=2

n0+n1+n2=7B=n-1=7-1=6

n0*0+n1*1+n2*2=6

在二叉樹的第i層上有2i-1個結(jié)點,深度為k的二叉樹有2k-1個結(jié)點的二叉樹。則此二叉樹稱為“滿二叉樹”。

滿二叉樹

如果一棵二叉樹只有最下面的兩層結(jié)點度數(shù)可以小于2，并且最下面一層的結(jié)點都集中在該層最左邊的若干位置上，則此二叉樹稱為“完全二叉樹”。

完全二叉樹性質(zhì)4：有n個結(jié)點的完全二叉樹的深度k為:log2n+1。證明：假設深度為k，則根據(jù)性質(zhì)2和完全二叉樹的定義有：

2k-1-1<n<=2k-1

或2k-1<=n<2k

于是

k-1<=log2n<k

因k是整數(shù)，

所以

k=log2n+1性質(zhì)5：

如果對一棵有n個結(jié)點的完全二叉樹按層序從1開始編號，則對任一結(jié)點(i<=i<=n),有：(1)如果i=1，則結(jié)點i是二叉樹的根結(jié)點；如果

i>1,

則其雙親結(jié)點是

i/2

。(2)如果2i<=n,則結(jié)點i的左孩

子是結(jié)點2i；否則結(jié)點i無

左孩子。(3)如果2i+1<=n,則結(jié)點i的右

孩子是結(jié)點2i+1；否則結(jié)

點i無右孩子。32個結(jié)點的完全二叉樹，從根開始，按層次從左到右用1-32編號。（1）它共有多少層？（2）各層最左邊的結(jié)點的編號是多少？（3）編號為6的結(jié)點的左孩子的編號是多少？它的右孩子呢？（4）編號為16的結(jié)點的左孩子的編號是多少？它的右孩子呢？（5）對于編號為8的結(jié)點，它的父結(jié)點的編號是多少？編號為13的結(jié)點呢？編號為1的結(jié)點呢？

隨堂練習6.2.3二叉樹的基本運算1.創(chuàng)建一棵空二叉樹；2.判斷某棵二叉樹是否為空；3.求二叉樹中的根結(jié)點；4.求二叉樹中某個指定結(jié)點的父結(jié)點；5.求二叉樹中某個指定結(jié)點的左子女結(jié)點；6.求二叉樹中某個指定結(jié)點的右子女結(jié)點；對于運算3—6，當指定結(jié)點沒有找到時，返回空。7.二叉樹的遍歷，即按某種方式訪問二叉樹中的所有結(jié)點，并使每個結(jié)點恰好被訪問一次。

6.2.4二叉樹的存儲表示

1.順序表示abcfhideg

abcdfge

結(jié)論：順序結(jié)構適用于完全二叉樹。思考：能否將一個順序表視為一個完全二叉樹呢？基于順序表的查找和排序能否在樹表中進行呢？structbtnode{ datatype data; structbtnode *lchild; structbtnode *rchild;};typedefstructbtnode

btnode;2.非順序表示

(1)二叉鏈ABCDEFG

llinkelementrlink

ABCDEFG2000000003456701234567（2）靜態(tài)二叉鏈structsbtnode{datatypedata;intllink,rlink;}tree[n+1];//n：二叉樹的結(jié)點個數(shù)例6-1利用層次遍歷方法建立二叉鏈表以三元組形式輸入(x,p,lr),其中x:data,p:x的父結(jié)點,lr:x是p的左孩子(l)或是右孩子(r)。首先輸入x,建立根結(jié)點。同時讓根結(jié)點入隊。然后，以三元組形式輸入(x,p,lr)，建立一個新結(jié)點，同時該結(jié)點入隊。再找到p的地址，將x以左孩子或右孩子鏈入。重復上述操作。

實現(xiàn)提示：利用data成員作為隊列。intcreate_tree(){intf,r;//f,r:隊尾和隊首指針

scanf(x);tree[1].data=x;tree[1].llink=tree[1].rlink=0;f=1;r=2;//建立根結(jié)點,根結(jié)點入隊

for(r=2;r<=n;r++){scanf(p,x,lr);tree[r].data=x;tree[r].llink=tree[r].rlink=0;//建立結(jié)點

while(tree[f].data!=p)f++;//找根結(jié)點的地址(下標)if(lr==‘l’)tree[f].llink=l;//x是p的左孩子

elsetree[f].rlink=r;//x是p的右孩子

}}以二叉鏈為存儲結(jié)構（靜態(tài)和動態(tài)），完成下列功能。（1）已知一棵完全二叉樹存于順序存儲結(jié)構a[1]..a[n]

中,a[1]..a[n]含結(jié)點值。建立二叉鏈存儲結(jié)構。（2）判別給定二叉樹是否為完全二叉樹。（3）求每一結(jié)點所在的層次。（4）按層次順序(同一層自左至右)遍歷二叉樹。（5）求二叉樹的結(jié)點數(shù)目。（6）求二叉樹的葉子數(shù)

（7）求二叉樹深度

思考題

二叉樹的遍歷(TraversingBinaryTree)：按某條搜索路徑訪問二叉樹中每一個結(jié)點，使得每個結(jié)點被訪問一次且僅被訪問一次。

遍歷方法有4種：6.3二叉樹的遍歷和線索二叉樹

6.3.1二叉樹的遍歷先序遍歷中序遍歷后序遍歷層次遍歷1、訪問根結(jié)點

2、先序遍歷左子樹3、先序遍歷右子樹先序遍歷序列：

abcdfge1234567abcdfge先序遍歷二叉樹1、中序遍歷左子樹

2、訪問根結(jié)點3、中序遍歷右子樹中序遍歷序列：

bafgdceabcdfge1234567中序遍歷二叉樹1、后序遍歷左子樹

2、后序遍歷右子樹3、訪問根結(jié)點后序遍歷序列：

bgfdecaabcdfge1234567后序遍歷二叉樹abcdfge1234567按層次（1-k層)，每層從左到右依次訪問二叉樹中的每一個結(jié)點。

層次遍歷序列：

abcdefg

層次遍歷二叉樹已知完全二叉樹結(jié)點的前序序列是abcdefghi，請畫出這棵完全二叉樹的邏輯結(jié)構圖。

隨堂練習abcdefghi例6.1已知二叉樹先序遍歷序列是:abcdefg;

中序遍歷序列是:cbdaefg;

（1）畫出該二叉樹;

（2）寫出后序遍歷序列。

（1）（2）寫出后序遍歷序列：cdbgfeaabcdefg1234567a例6.2畫出所有中序遍歷序列和后序遍歷序列一致的

二叉樹的所有形態(tài).分析：中序遍歷:LDR---LD

后序遍歷:LRD---LDabadefgffn個結(jié)點….....二、二叉樹的遍歷算法1、先序遍歷voidOrder(btnode*T){//先序遍歷以T為根的二叉樹

if(T!=NULL){Visite(T->data);//訪問根結(jié)點

Order(T->lchild);//先序遍歷左子樹

Order(T->rchild);//先序遍歷右子樹

}}T(n)=O(n)1234567abcdfge判斷一個結(jié)點，（1）不空?

訪問該結(jié)點;

把它推入棧中;

遍歷它的左子樹.

(2)空?

棧頂結(jié)點出棧;

找到這個結(jié)點的右子樹，然后遍歷它的右子樹。

先序遍歷二叉樹非遞歸算法的思想voidpreOrder(btnode*T){//先序遍歷以T為根的二叉樹

initstack(s);//設置一個空棧

while(T!=NULL

||!empty(s))

if(T!=NULL)//若T不空，則訪問結(jié)點Ｔ｛Visite(T->data);//訪問根結(jié)點

push(s,T);//Ｔ入棧Ｔ＝Ｔ－>lchild;//沿左子樹遍歷

}

else{pop(s,T);//棧頂元素Ｔ出棧

T=T->rchild；//沿右子樹遍歷

}}2、中序遍歷voidOrder(btnode*T){//中序遍歷以T為根的二叉樹

if(T){Order(T->lchild);//中序遍歷左子樹

Visite(T->data);//訪問根結(jié)點

Order(T->rchild);//中序遍歷右子樹

}}voidinOrder(btnode*T){//中序遍歷以T為根的二叉樹

initstack(s);//設置一個空棧

while(T||!empty(s))

if(T)//若T不空，則訪問結(jié)點Ｔ｛push(s,T);Ｔ＝Ｔ－>lchild;｝

//Ｔ入棧，沿左子樹遍歷

else{pop(s,T);//棧頂結(jié)點T出棧

visite(T->data);//訪問根結(jié)點

T=T->rchild;//遍歷右子樹

}}3、后序遍歷voidOrder(btnode*T){//后序遍歷以T為根的二叉樹

if(T){Order(T->lchild);//后序遍歷左子樹

Order(T->rchild);//后序遍歷右子樹

Visite(T->data);//訪問根結(jié)點

}}思考：后序遍歷非遞歸算法的設計?structnode{datatypedata;intllink,rlink;}tree[n+1];//n：二叉樹的結(jié)點個數(shù)例6.3

以靜態(tài)二叉鏈為存儲結(jié)構,實現(xiàn)二叉樹的遍歷。1、先序遍歷

voidpreorder(intp){//前序遍歷以p為根的二叉樹

if(p>0){cout<<tree[p].data;//訪問根結(jié)點

preorder(tree[p].llink);//前序遍歷左子樹

preorder(tree[p].rlink);//前序遍歷右子樹

}}2、中序遍歷

voidinorder(intp){//中序遍歷以p為根的二叉樹

if(p>0){inorder(tree[p].llink);//中序遍歷左子樹

cout<<tree[p].data;//訪問根結(jié)點

inorder(tree[p].rlink);//中序遍歷右子樹

}}3、后序遍歷

voidpostorder(intp){//后序遍歷以p為根的二叉樹

if(p>0){postorder(tree[p].llink);//后序遍歷左子樹

postorder(tree[p].rlink);//后序遍歷右子樹

cout<<tree[p].data;//訪問根結(jié)點

}}voidlevelorder(intp){//層次遍歷以p為根的二叉樹

}四、層次遍歷intq[n+1],r=1,f=1;//設置一個空隊列if(p!=0)q[r++]=p;//根結(jié)點入隊列while(f!=r){//當隊列不空時

}p=q[f++];//隊首元素出隊列cout<<tree[p].data);//

訪問根結(jié)點if(tree[p].llink>0)q[r++]=tree[p].llink;//左子樹入隊if(tree[p].rlink>0)q[r++]=tree[p].rlink;//右子樹入隊例6.4算法分析intfib(intn){intf；

if(n<=1)f=n;elsef=fin(n-2)+fin(n-1)；

returnf;}

思考1：出結(jié)果是什么？思考2：該算法的時間復雜性是多少？500011111111223結(jié)論：由二叉樹性質(zhì)2可知，該算法的時間復雜性是

O(2n)例6.5

以二叉鏈為存儲結(jié)構，編寫算法實現(xiàn)：（1）求二叉樹中的結(jié)點數(shù)目。（2）求二叉樹中的葉子數(shù)目。（3）求二叉樹中的高度（深度）。（4）將二叉樹中所有結(jié)點的左孩子和右孩子互換。（1）求二叉樹中的結(jié)點數(shù)目。算法1：voidnodes(btnode*bt){

//求二叉樹中的結(jié)點數(shù)目。n:全程變量，初值為0

if(bt!=NULL){n++;//計數(shù)

nodes(bt->lchild);//求左子樹的結(jié)點數(shù)

nodes(bt->rchild);//

求右子樹的結(jié)點數(shù)

}}（1）求二叉樹中的結(jié)點數(shù)目。算法2：intnodes(btnode*bt){

//求二叉樹中的結(jié)點數(shù)目

if(bt==NULL)return0;//空的二叉樹中結(jié)點個數(shù)為0elsereturnnodes(bt->lchild)+nodes(bt->rchild)+1;

//左子樹上的結(jié)點數(shù)+右子樹上的結(jié)點數(shù)+1（根）}abcdfe1240000100106（2）求二叉樹中的葉子結(jié)點數(shù)目。abcdfe1120000100103intleafs(btnode*bt){

//求二叉樹中的葉子結(jié)點數(shù)目

if(bt==NULL)return0;

//空的二叉樹，其葉子結(jié)點個數(shù)為0elseif(bt->lchild==NULL&&bt->rchild==NULL)return1;//葉子

elsereturnleafs(bt->lchild)+leafs(bt->rchild);

//左子樹上的葉子數(shù)+右子樹上的葉子數(shù)}（3）求二叉樹中的深度。abcdfe1230000100104算法1：intdepth(btnode*bt){

//求二叉樹中的深度

if(bt==NULL)return0;

//空的二叉樹深度為0elsereturn1+max(depth(bt->lchild),depth(bt->rchild)）;//二叉樹的深度是：1（根）+左、右子樹的較大深度}abcdfe232341intdepth_2(btnode*bt){

//求二叉樹中的深度,采用???遍歷方法進行

high=level=0;//計二叉樹的高度和層次

t=bt;initstack(s);while(t!=NULL||!empty(S))if(t!=NULL){push(s,(t,++level));t=t->lchild;}else{(t,level)=pop(s);if(level>high)high=level;t=t->rchild;}returnhigh;}算法2：high=0level=0,2,2,3

,3,4,4abcdfe232341intdepth_3(btnode*bt){

//求二叉樹中的深度,借助隊列實現(xiàn)

initqueue(Q);enqueue(Q,（bt,1）);while(!empty(Q)){(f,h)=delqueue(Q);if(f->lchild!=NULL){p=f->lchild;enququq(Q,（p,h+1）);}if(f->rchild!=NULL){p=f->rchild;enququq(Q,（p,h+1）);}};retuern(h);}算法3：（4）將二叉樹中所有結(jié)點的左孩子和右孩子互換。voidexchang(btnode*bt){

if(bt!=NULL){p=bt->lchild;bt->lchild=bt->rchild;bt->rchild=p;excheng(bt->lchild);excheng(bt->rchild);}}思考：采用后序遍歷方法可以實現(xiàn)嗎?思考：采用中序遍歷方法呢?思考題：

以二叉鏈為存儲結(jié)構，（1）求二叉樹中所有結(jié)點的子孫個數(shù)。（2）判斷一個二叉樹是否為正則二叉樹。（3）判斷一個二叉樹是否為滿二叉樹。（4）判斷一個二叉樹是否為完全二叉樹。（5）刪除二叉樹中以x為根結(jié)點的子樹。（6）算術表達式求值。

遍歷二叉樹是按一定的規(guī)則將二叉樹中結(jié)點排列成一個線性序列；這實際上是把一個非線性結(jié)構進行線性化的操作。6.3.2線索二叉樹先序遍歷序列:abcdefghi中序遍歷序列:dcebfahgi后序遍歷序列:decfbhiga層次遍歷序列:abgcfhide若ltag=0,lchild指向左子樹，否則指向前趨結(jié)點；若rtag=0,rchild指向右子樹，否則指向后繼結(jié)點；structThrTreeNode{//線索二叉樹中每個結(jié)點的結(jié)構

DataTypedata;ThrTreeNode*lchild,*rchild;

intltag,rtag;};

利用結(jié)構中的空鏈域，并設立標志。以上結(jié)構構成的二叉鏈表作為二叉樹的存儲結(jié)構，叫做線索二叉鏈。指向結(jié)點前驅(qū)或后繼的指針叫做線索。加上線索的二叉樹叫線索二叉樹。對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程叫做線索化。例：先序線索二叉樹和先序線索二叉樹鏈

(先序遍歷序列：abcdfge)一、遍歷線索二叉樹1、先序遍歷

從根開始，找每個結(jié)點的后繼結(jié)點。

voidpreOrder(structThrTreeNode*p){

//先序遍歷以p為根的線索二叉樹

while(p!=NULL){

visite(p->data);//訪問根結(jié)點

p=next(p);//按先序遍歷順序找每個結(jié)點的后繼結(jié)點

}

}if(p->ltag==0)p=p->lchildelsep=p->rchild2、中序遍歷（1）從根開始，沿著左子樹找到一個無前驅(qū)的結(jié)點；（2）再找每個結(jié)點的后繼結(jié)點。

voidinOrder(ThrTreeNode*p){//中序遍歷以p為根的線索二叉樹

while(p->ltag==0)p=p->lchild;//（1）從根開始，沿著左子樹找到一個無前驅(qū)的結(jié)點p；

while(p!=NULL){visite(p->data);//訪問根結(jié)點

p=next(p);//按中序遍歷順序找每個結(jié)點的后繼結(jié)點

}}思考：中序遍歷順序找每個結(jié)點的后繼結(jié)點?ThrTreeNode*next(ThrTreeNode

*p){//求p的后繼結(jié)點tt=p->.rchild;if(p->rtag==0)while(t->ltag==0)t=t->lchild;return(t);}

在中序線索二叉樹上求p的后繼結(jié)點3、后序遍歷（1）從根開始，沿著左子樹找到一個無前驅(qū)的結(jié)點；（2）再找每個結(jié)點的后繼結(jié)點。

voidPostOrder(ThrTreeNode*p){//后序遍歷以p為根的線索二叉樹

while(p->ltag==0)p=p->lchild;//（1）從根開始，沿著左子樹找到一個無前驅(qū)的結(jié)點p；

while(p!=NULL){visite(p->data);//訪問根結(jié)點

p=next(p);//按后序遍歷順序找每個結(jié)點的后繼結(jié)點

}}思考：后序遍歷順序找每個結(jié)點的后繼結(jié)點?二、靜態(tài)線索二叉鏈

+：左、右孩子；-：前驅(qū)、后繼線索中序線索二叉樹中序（靜態(tài)）線索二叉鏈中序遍歷序列（bafdgce)6.4樹和森林6.4.1樹和森林的定義

樹（Tree)是n(n>=0)個結(jié)點的有限集。在任意一棵非空樹中：

(1)有且僅有一個根結(jié)點；

(2)除根結(jié)點外，其余結(jié)點可分為m(m>=0)個互不相交的子樹。

森林是m（m>=0）棵互不相交的樹的集合。6.4.2樹的存儲結(jié)構

1、雙親表示法Oacgbdef2、孩子鏈表Oacgbdef3、孩子—兄弟鏈(左孩子-右兄弟)Oacgbdef6.4.3樹、森林與二叉樹的轉(zhuǎn)換

1、樹轉(zhuǎn)換成二叉樹OacgbdefOacgbdef

(左孩子-右兄弟)

2、森林轉(zhuǎn)換成二叉樹Oacgbdef(2)沿右兄弟鏈將多個樹鏈在一起abOcgdef(1)將每一個樹轉(zhuǎn)換成二叉樹6.4.4樹和森林的遍歷

1、樹的遍歷Oacgbdef

先序遍歷：

（1）訪問根結(jié)點

（2）先序遍歷每一個子樹

先序遍歷序列：

oabcdfeg

OacgbdefOacgbdef先序遍歷序列：

oabcdfeg6.4.4樹和森林的遍歷

1、樹的遍歷Oacgbdef

后序遍歷：

（1）后序遍歷每一個子樹

（2）訪問根結(jié)點

后序遍歷序列：

bafdecgo

OacgbdefOacgbdef后序遍歷序列：

bafdecgo

2、森林的遍歷Oacgbdef先序遍歷----先序遍歷每一個樹(abocdfeg)abOcgdef

2、森林的遍歷Oacgbdef中序遍歷----后序遍歷每一個樹(bafdecgo)abOcgdef習題三：以左孩子-右兄弟鏈表為存儲結(jié)構，（一）求樹中的結(jié)點數(shù)目。（二）求樹中的樹葉數(shù)目。（三）求樹的高（深）度。（四）求樹的度。（五）無重復地輸出以孩子-兄弟鏈表中的所有邊，形式為(k1,k2),...,ABCDEFG

llinkelementrlink

ABCDEFG2000000003456701234567靜態(tài)二叉鏈structsbtnode{datatypedata;intllink,rlink;}tree[n+1];//n：二叉樹的結(jié)點個數(shù)6.6huffman樹及應用6.6.1二叉樹的帶權路徑長度

二叉樹的帶權路徑長度：

n

WPL=wklkk=1其中，n:葉子結(jié)點個數(shù)，wk:第k個葉子的權，

lk:第k個葉子到根的路徑長度。

6.6.2Huffman樹

對于有n個葉子，可以構造出多個二叉樹。

Huffman樹是一個帶權路徑長度最小的二叉樹，又稱最優(yōu)二叉樹。一、Huffman樹的構造方法

（1）將{w1,w2,…….,wn}看成n個二叉樹；

（2）選擇2個根結(jié)點的值最小的二叉樹，構造1個新的二叉樹；…….；直至剩1個樹止。二、示例例1：給定權值7,5,2和4，構造哈夫曼樹。1.75242462.3.115246524674.5.71152467115246186.

例：設包含8個字符的字符集中各字符使用的相對頻率分別為5,29,7,8,14,23,3,11,試設計哈夫曼編碼（教材第146頁例6-2）。1.以給定頻率為權構造哈夫曼樹；5142987311232.在哈夫曼樹的所有左分支上編上號碼“0”,右分支上編上號碼“1”；8735112314293.將根結(jié)點到每個葉子結(jié)點的路徑編碼串起來,得到字符集的哈夫曼編碼。111111100000001(5):01102(29):103(7):11104(8):11115(14):1106(23):007(3):01118(11):010例3某系統(tǒng)在通信聯(lián)絡中只可能出現(xiàn)8個字符，其出現(xiàn)概率分別為

ZKFC U D L E27 2432 37 42 42 120

構造huffman樹。12345678914235067weightllinkrlinkplink14000230007000600050000

0

0

0

0

三、存儲結(jié)構

——

靜態(tài)三叉鏈#definen5structhnode{floatweight;intllink;intrlink;intplink;};hnodehuftree[2*n];123456789（1）初值：將n個樹葉看作n個二叉樹在靜態(tài)三叉鏈中構造huffman樹14235067weightllinkrlinkplink14000230007000600050000

0

0

0

0

123456789(2)找兩個根結(jié)點的值最小的二叉樹6和7構造一個新的二叉樹。在靜態(tài)三叉鏈中構造huffman樹1423506713weightllinkrlinkplink1400023000700660065000013430

0

0

0

slsr123456789(2)找兩個根結(jié)點的值最小的二叉樹13和14構造一個新的二叉樹。在靜態(tài)三叉鏈中構造huffman樹142350671327weightllinkrlinkplink140072300070066006500001343727610

0

0

slsr123456789(2)找兩個根結(jié)點的值最小的二叉樹23和27構造一個新的二叉樹。在靜態(tài)三叉鏈中構造huffman樹14235067132750weightllinkrlinkplink14007230087006600650000134372761850270

0

slsrweightllinkrlinkplink1400723008700660065000913437276185027958010014235067132750(2)找兩個根結(jié)點的值最小的二叉樹50和

50構造一個新的二叉樹。100在靜態(tài)三叉鏈中構造huffman樹123456789slsr四、算法設計

voidset_haffmantree(){

for(i=1;i<=m;++i)ht[i].plink=ht[i]->llink=ht[i]->rlink=0;//m=2*n-1for(i=1;i<=n;++i)ht[i].weight=w[i];//初始化

for(i=n+1;i<=m,++i)//建哈夫曼樹

{select(i-1,sl,sr);//在ht[k](1<=k<=i-1)中選擇兩個雙親域為零的最小的

//結(jié)點:sl和sr(sl和sr為最小值所在的下標)ht[sl].plink=ht[sr].plink=i;ht[i].llink=sl;ht[i].rlink=sr;ht[i].weight=ht[sl].weight+ht[sr].weight；

}}

Huffman編碼是用于數(shù)據(jù)文件壓縮的有效的編碼方法。其壓縮率通常在20%～90%之間。Huffman編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個用0，1串表示各字符的最優(yōu)表示方式。

6.6.3哈夫曼編碼

前綴編碼:對每一個字符規(guī)定一個0,1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。