1一、雙親表示法二、孩子鏈表表示法三、樹(shù)的二叉鏈表(孩子-兄弟）存儲(chǔ)表示法6.4樹(shù)和森林6.4.1樹(shù)的存儲(chǔ)結(jié)構(gòu)2一、雙親表示法（順序存儲(chǔ)）

用一組連續(xù)空間存儲(chǔ)樹(shù)的結(jié)點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)域指示其雙親的位置。aedbihgcf021345678dataparent

0a-11b02

c03d14e15f26g47h4

8i43

typedefstructPTNode{Elemdata;

intparent;//雙親位置域

}PTNode;#defineMAX_TREE_SIZE100結(jié)點(diǎn)結(jié)構(gòu):C語(yǔ)言的類(lèi)型描述:

dataparent4typedefstruct{PTNodenodes[MAX_TREE_SIZE];

intr,n;//根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)

}PTree;樹(shù)結(jié)構(gòu):5(1)由于樹(shù)中每個(gè)結(jié)點(diǎn)可有多個(gè)孩子，則每個(gè)結(jié)點(diǎn)可設(shè)多個(gè)指針成員，每個(gè)指針指向一個(gè)孩子。對(duì)于度為m的樹(shù)，結(jié)點(diǎn)結(jié)構(gòu)如下：datadegree

c1c2

…ckdatac1c2c3

…cm(2)每個(gè)結(jié)點(diǎn)有幾個(gè)孩子，就有幾個(gè)指針。二、孩子表示法（鏈?zhǔn)酱鎯?chǔ)）問(wèn)題：會(huì)有太多的空指針！(3)將每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來(lái)，連接成一個(gè)單鏈表。n個(gè)結(jié)點(diǎn)有n個(gè)孩子鏈表，n個(gè)孩子鏈表的頭指針可放在數(shù)組中，稱(chēng)為孩子鏈表。60a12

1b342c53d4e6785f6g7h8i孩子鏈表aedbihgcf0213456787typedefstructCTNode{

intchild;

structCTNode*nextchild;}*ChildPtr;孩子結(jié)點(diǎn)結(jié)構(gòu):

childnextchildC語(yǔ)言的類(lèi)型描述:8

typedefstruct{Elemdata;ChildPtrfirstchild;//孩子鏈的頭指針}CTBox;雙親結(jié)點(diǎn)結(jié)構(gòu)

datafirstchildtypedefstruct{CTBoxnodes[MAX_TREE_SIZE];

intn,r;//結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置

}CTree;樹(shù)結(jié)構(gòu):帶雙親的孩子鏈表：將雙親表示法和孩子表示法結(jié)合起來(lái)。aedbihgcf0

a-112

1b0342c053d14e16785f26g47h48i4021345678三、孩子兄弟表示法：又稱(chēng)樹(shù)的二叉鏈表表示法即用二叉鏈表作樹(shù)的存儲(chǔ)結(jié)構(gòu)。結(jié)點(diǎn)中的兩個(gè)指針?lè)謩e指向該結(jié)點(diǎn)的第一個(gè)孩子和下一個(gè)兄弟aedbihgcf

a

b

c

d

e

f

g

h

i

11typedefstructCSNode{Elemdata;

structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;C語(yǔ)言的類(lèi)型描述:結(jié)點(diǎn)結(jié)構(gòu):

firstchilddatanextsibling12ABCDEFGrootABCEDFGABCEDFG

畫(huà)出以下存儲(chǔ)結(jié)構(gòu)root13樹(shù)ABCED二叉樹(shù)ABCEDA^BCDE^^^^^6.4.2森林與二叉樹(shù)的轉(zhuǎn)換

從樹(shù)的鏈表表示的定義可知，任何一棵與樹(shù)對(duì)應(yīng)的二叉樹(shù)，其右子樹(shù)必空。若把森林中第二棵樹(shù)的根結(jié)點(diǎn)看成是第一棵樹(shù)的根結(jié)點(diǎn)的兄弟，則可導(dǎo)出森林和二叉樹(shù)的關(guān)系。森林

二叉樹(shù)ABCDEFGHIJABCFEGDIHJ15森林與二叉樹(shù)互相轉(zhuǎn)換的方法：一.森林轉(zhuǎn)換成二叉樹(shù)①將森林中的每棵樹(shù)轉(zhuǎn)換為二叉樹(shù)；②將第i+1棵樹(shù)作為第i棵樹(shù)的右子樹(shù)，依次連接成一棵二叉樹(shù)；二.二叉樹(shù)轉(zhuǎn)換成森林①將二叉樹(shù)根的右子樹(shù)作為另一棵二叉樹(shù)，將新分出的二叉樹(shù)轉(zhuǎn)換成森林；②將二叉樹(shù)轉(zhuǎn)換成森林；1247356891016

樹(shù)的遍歷1.按層次：先訪問(wèn)第一層的結(jié)點(diǎn)，之后訪問(wèn)第二層的結(jié)點(diǎn)。2.先根遍歷：先訪問(wèn)根結(jié)點(diǎn)，依次先根遍歷其各子樹(shù)。3.后根遍歷：依次后根遍歷其各子樹(shù),再訪問(wèn)根結(jié)點(diǎn)。6.4.3樹(shù)和森林的遍歷17

樹(shù)先根：ABEFCGIJD

后根：EFBIGJCDA二叉樹(shù)先序遍歷中序遍歷ABCFEGDJIABCFEGDJI181.森林中第一棵樹(shù)的根結(jié)點(diǎn)；2.森林中第一棵樹(shù)的子樹(shù)森林；3.森林中其它樹(shù)構(gòu)成的森林?？梢苑纸獬扇糠?森林BCDEFGHIJK森林的遍歷19若森林不空，則訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn);先序遍歷森林中第一棵樹(shù)的子樹(shù)森林；先序遍歷森林中(除第一棵樹(shù)之外)其余樹(shù)構(gòu)成的森林。先序遍歷即：依次從左至右對(duì)森林中的每一棵樹(shù)進(jìn)行先根遍歷。20

中序遍歷

若森林不空，則中序遍歷森林中第一棵樹(shù)的子樹(shù)森林;訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn);中序遍歷森林中(除第一棵樹(shù)之外)其余樹(shù)構(gòu)成的森林。即：依次從左至右對(duì)森林中的每一棵樹(shù)進(jìn)行后根遍歷。例如：先序遍歷：ABCDEFGHIJ中序遍歷：BCDAFEHJIG結(jié)論：二叉樹(shù)森林先序遍歷先序遍歷中序遍歷中序遍歷ABCDEFGHIJABCFEGDIHJ22設(shè)樹(shù)的存儲(chǔ)結(jié)構(gòu)為孩子兄弟鏈表typedefstructCSNode{Elemdata;

structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;一、建樹(shù)的存儲(chǔ)結(jié)構(gòu)二、先序遍歷樹(shù)（森林）三、求樹(shù)(森林)的深度四、輸出樹(shù)中所有從根到葉子的路徑一、建樹(shù)的存儲(chǔ)結(jié)構(gòu)的算法:

和二叉樹(shù)類(lèi)似，不同的定義相應(yīng)有不同的算法。

假設(shè)以二元組(F,C)的形式自上而下、自左而右依次輸入樹(shù)的各邊，建立樹(shù)的孩子-兄弟鏈表。ABCDEFG例如:對(duì)下列所示樹(shù)的輸入序列應(yīng)為:(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)(‘C’,‘F’)(‘E’,‘G’)ABCD(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)可見(jiàn)，算法中需要一個(gè)隊(duì)列保存已建好的結(jié)點(diǎn)的指針voidCreatTree(CSTree&T){T=NULL;

for(scanf(&fa,&ch);ch!=

;

scanf(&fa,&ch);){ p=New

CSNode；

p->data=ch;//創(chuàng)建結(jié)點(diǎn)

EnQueue(Q,p);//指針入隊(duì)列

if(fa==

)T=p;//所建為根結(jié)點(diǎn)

else{

}//非根結(jié)點(diǎn)的情況

}//for}//CreateTree ……GetHead(Q,s);//取隊(duì)列頭元素(指針值)while(s->data!=fa){//查詢雙親結(jié)點(diǎn)

DeQueue(Q,s);GetHead(Q,s);}if(!(s->firstchild))

{s->firstchild=p;r=p;}

//鏈接第一個(gè)孩子結(jié)點(diǎn)else

{r->nextsibling=p;r=p;}

//鏈接其它孩子結(jié)點(diǎn)

27ABCEDA^BCDE^^^^^二、先序遍歷樹(shù)（森林）的遞歸算法：28voidpre_order_tree(CSTreeT){

for(p=T;p;p=p→nextsibling){printf(p→data)；

if(p→firstchild≠NULL)pre_order_tree(p→firstchild)；

}}//preorder遞歸算法：29voidOutPath(BitreeT){

while(T){printf(p→data)；

if(T->firstchild)

OutPath(T->firstchild);

T=T->nextsibling;

}//while}//OutPath//while循環(huán)寫(xiě)的遍歷算法30ABCEDA^BCDE^^^^^三、求樹(shù)的深度的算法：31intDepth(CSTreeT){if(T==NULL)return0;else{d1=Depth(T->firstchild);d2=Depth(T->nextsibling);returnmax(d1+1,d2)}三、求樹(shù)的深度的算法：32四、輸出樹(shù)中所有從根到葉子的路徑的算法:ABCDEFGHIJK例如：對(duì)左圖所示的樹(shù)，其輸出結(jié)果應(yīng)為：ABEABFACADGHIADGHJADGHK33voidOutPath(BitreeT){

while(T){printf(p→data)；

if(T->firstchild)

OutPath(T->firstchild);

T=T->nextsibling;

}//while}//OutPath//原有遍歷算法34voidOutPath(BitreeT,Stack*S){

while(T){

Push(*S,T->data);

if(!T->firstchild)Printstack(*S);

elseOutPath(T->firstchild,S);

Pop(*S);

T=T->nextsibling;

}//while}//OutPath//輸出森林中所有從根到葉的路徑3536互聯(lián)網(wǎng)上的域名如同我們現(xiàn)實(shí)生活中的門(mén)牌號(hào)碼，可以在紛繁蕪雜的網(wǎng)絡(luò)世界里準(zhǔn)確無(wú)誤地把我們指引到我們要訪問(wèn)的站點(diǎn)。37結(jié)點(diǎn)間的路徑長(zhǎng)度：

兩個(gè)結(jié)點(diǎn)之間的分支數(shù)。結(jié)點(diǎn)的權(quán)值：

附加在結(jié)點(diǎn)上的信息。結(jié)點(diǎn)帶權(quán)路徑：

結(jié)點(diǎn)上權(quán)值與該結(jié)點(diǎn)到根之間的路徑長(zhǎng)度的乘積。6.5哈夫曼樹(shù)及其應(yīng)用6.5.1最優(yōu)二叉樹(shù)——哈夫曼樹(shù)ABCDEFGHIJ38樹(shù)的帶權(quán)路徑長(zhǎng)度：

(WeightPathLength)

樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。WPL=(葉到根的平均路徑長(zhǎng)度)哈夫曼(huffman)樹(shù)：使WPL取最小值的二叉樹(shù)，又稱(chēng)最優(yōu)二叉樹(shù)ABCDEFGHIJ203050例：有n個(gè)葉子結(jié)點(diǎn)，第i個(gè)葉子結(jié)點(diǎn)的權(quán)值為Wi，根到該結(jié)點(diǎn)的路徑長(zhǎng)度為L(zhǎng)i，則：39例如，給定權(quán)值{5,4,7,2,5}，可生成多棵二叉樹(shù)WPL=2*1+7*3+4*3+5*3+5*3=6557254(a)57254(b)WPL=2*1+4*2+5*3+7*4+5*4=7340WPL=(2+4)*3+(7+5+5)*2=52WPL=(5+5+7)*2+(2+4)*3=5257254(c)57254(d)41如何構(gòu)成一棵最優(yōu)二叉樹(shù)？

(哈夫曼算法)

(1)根據(jù)n個(gè)權(quán)值{w1,w2,…,wn}構(gòu)成n棵二叉樹(shù)的集合F={T1,T2,…,Tn}，其中每棵二叉樹(shù)Ti只有一個(gè)帶權(quán)為Wi的根結(jié)點(diǎn)，其左右子樹(shù)均空。(2)在F中選兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為左右子樹(shù)構(gòu)成一棵新的二叉樹(shù)，且根結(jié)點(diǎn)的權(quán)值為其左右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和。(3)在F中刪除這兩棵樹(shù)，同時(shí)將新的二叉樹(shù)加入F(4)重復(fù)(2)、(3)，直到F只含一棵樹(shù)為止。9例如:已知權(quán)值W={5,6,2,9,7}5627257697671392576713925792571667132944哈夫曼樹(shù)的應(yīng)用:在解決某些判定問(wèn)題時(shí)的最佳判定算法。例:將學(xué)生百分成績(jī)按分?jǐn)?shù)段分級(jí)的程序。若學(xué)生成績(jī)分布是均勻的，可用二叉樹(shù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。a<60a<70a<80a<90不及格中等良好優(yōu)秀及格YNYNYNYN輸入10000個(gè)數(shù)據(jù)，則需進(jìn)行28000次比較。讀入一個(gè)a值平均判斷：(1+2+3+4+4)*0.2=2.8(次)45分?jǐn)?shù)0—5960—6970—7980—8990—99比例0.050.150.40.30.10學(xué)生成績(jī)分布不是均勻的情況：構(gòu)造一棵哈夫曼樹(shù)：再將每一比較框的兩次比較改為一次：WPL=0.4*1+0.3*2+0.15*3+(0.05+0.1)*4=2.05WPL=(0.4+0.3+0.1)*2+(0.05+0.15)*3=2.20輸入10000個(gè)數(shù)據(jù)，僅需進(jìn)行22000次比較。0.40.050.10.150.150.30.30.670≤a<80a<60及格中等良好80≤a<9060≤a<70不及格優(yōu)秀YNYNYNYN

不及格Ya<90a<80a<70a<60優(yōu)秀中等及格良好YNNNYYYN46

哈夫曼編碼是二進(jìn)制編碼形式，用于(網(wǎng)絡(luò))通信中，它作為一種最常用無(wú)損壓縮編碼方法，在數(shù)據(jù)壓縮程序中具有非常重要的應(yīng)用。

如需傳送字符串‘ABACCDA’，只有4種字符:A、B、C、D，只需兩位編碼。如分別編碼為00、01、10、11，上述字符串的二進(jìn)制總長(zhǎng)度為14位。

在傳送信息時(shí)，希望總長(zhǎng)度盡可能短，可對(duì)每個(gè)字符進(jìn)行不等長(zhǎng)度的編碼，且出現(xiàn)頻率高的字符編碼盡量短。如A、B、C、D的編碼分別為0、00、1、01時(shí)，上述電文長(zhǎng)度會(huì)縮短，但可能有多種譯法。如‘0000’可能是‘AAAA’,‘ABA’,‘BB’。6.5.2哈夫曼編碼47若要設(shè)計(jì)不等長(zhǎng)編碼，任一字符的編碼都不是另一個(gè)字符編碼的前綴。這種編碼稱(chēng)為前綴編碼。

可利用二叉樹(shù)來(lái)設(shè)計(jì)二進(jìn)制的前綴編碼，將每個(gè)字符出現(xiàn)的頻率作為權(quán)，設(shè)計(jì)一棵哈夫曼樹(shù)，左分支為0，右分之為1，就得到每個(gè)葉子結(jié)點(diǎn)的編碼。95271667132900001111000111100101例如：編碼：0、00、1、01就不是前綴編碼。[結(jié)論1]存儲(chǔ)結(jié)構(gòu)：#defineN字符數(shù)目；#defineM結(jié)點(diǎn)數(shù)目；//m=2n-1huffman樹(shù)用靜態(tài)三叉鏈表做存儲(chǔ)結(jié)構(gòu)，且0號(hào)單元不用huffman編碼用指向字符的指針數(shù)組來(lái)動(dòng)態(tài)管理存儲(chǔ)；且0號(hào)單元不用[證]：m=n0+n1+n2

，因?yàn)椋簄1=0,n2=n0-1,

所以：m=2n0–1,即m=2n-1.huffman樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)。[結(jié)論2]有n個(gè)葉子結(jié)點(diǎn)的huffman樹(shù)中共有m=2n-1個(gè)結(jié)點(diǎn)。49Data

ABDCENFGI...lchild245070000...rchild306089000...

123456789

FAHDBCGFEI123456789補(bǔ)充：靜態(tài)鏈表存儲(chǔ)typedefstruct{

chardata；

intweight；

intparent，lch，rch；

}NodeType；

//huffman樹(shù)結(jié)點(diǎn)類(lèi)型

typedefchar**HufCode

；

//動(dòng)態(tài)分配指針數(shù)組存儲(chǔ)huffman編碼typedef

NodeType

HufTree[M+1]；

//靜態(tài)三叉鏈表存儲(chǔ)huffman樹(shù)1234hcd例：設(shè)有4個(gè)結(jié)點(diǎn)a、b、c、d，權(quán)值分別為(0.4，0.3，0.1，0.2)。dataweightparentlchrcha

0.4000

b

0.3000

c

0.1000

d

0.20000.303450.6

0

2561.0016770123456750‘\0’10‘\0’110‘\0’111‘\0’61.0

01

0.4

01

0.3

01

0.10.21.0a0.6b0.3cd算法1：已知n個(gè)字符的權(quán)值，生成一棵huffman樹(shù)。voidhuff_tree(intw[n],HufTree&ht){//w存放權(quán)值for(i=1；i≤n；i++){//哈夫曼樹(shù)初始化ht[i].weight=w[i-1]；ht[i].parent=0；ht[i].lch=0；ht[i].rch=0

}；ht[n+1..m].parent=0；for(i=n+1；i≤m；i++){

//構(gòu)造n-1個(gè)非葉子結(jié)點(diǎn)select(i-1,s1,s2)；

//在ht[1..i-1]中選擇兩個(gè)雙親為0并且權(quán)值最小的兩個(gè)結(jié)點(diǎn),//最小結(jié)點(diǎn)位置為s1,次小的位置為s2。

ht[i].weight=ht[s1].weight+ht[s2].weightht[i].lch=s1；ht[i].rch=s2；

ht[s1].parent=i；ht[s2].parent=i；}；}//huff_tree5301234

cd0123dataweightparentlchrcha

0.4000

b

0.3000

c

0.1000

d

0.20000.30

3450.6

0

2561.00

167701234567561234hcd0‘\0’10‘\0’110‘\0’111‘\0’hcdtypedef

char**

HufCode；

//動(dòng)態(tài)分配指針數(shù)組存儲(chǔ)huffman編碼HufCode

hcd;char*cd;‘\0’start0start

‘\0’0

算法2：由huffman樹(shù)求n個(gè)字符的haffman編碼voidhuf_code(HufCode

&hcd，HufTree

ht，intn){hcd=(hufcode)malloc((n+1)*sizeof(char*))；//指針數(shù)組空間cd=(char*)malloc(n*sizeof(char)）；//求編碼的臨時(shí)空間for(i=1；i≤n；i++){

cd[n-1]=‘\0’；//編碼結(jié)束符

start=n-1；c=i；f=ht[c].parent；

while（f≠0