樹和二叉樹4(樹和森另)

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

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

0a-11b02

c03d14e15f26g47h4

8i43

typedefstructPTNode{Elemdata;

intparent;//雙親位置域

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

dataparent4typedefstruct{PTNodenodes[MAX_TREE_SIZE];

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

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

c1c2

…ckdatac1c2c3

…cm(2)每個結(jié)點(diǎn)有幾個孩子，就有幾個指針。二、孩子表示法（鏈?zhǔn)酱鎯Γ﹩栴}：會有太多的空指針！(3)將每個結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來，連接成一個單鏈表。n個結(jié)點(diǎn)有n個孩子鏈表，n個孩子鏈表的頭指針可放在數(shù)組中，稱為孩子鏈表。60a12

1b342c53d4e6785f6g7h8i孩子鏈表aedbihgcf0213456787typedefstructCTNode{

intchild;

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

childnextchildC語言的類型描述: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;樹結(jié)構(gòu):帶雙親的孩子鏈表：將雙親表示法和孩子表示法結(jié)合起來。aedbihgcf0

a-112

1b0342c053d14e16785f26g47h48i4021345678三、孩子兄弟表示法：又稱樹的二叉鏈表表示法即用二叉鏈表作樹的存儲結(jié)構(gòu)。結(jié)點(diǎn)中的兩個指針分別指向該結(jié)點(diǎn)的第一個孩子和下一個兄弟aedbihgcf

a

b

c

d

e

f

g

h

i

11typedefstructCSNode{Elemdata;

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

firstchilddatanextsibling12ABCDEFGrootABCEDFGABCEDFG

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

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

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

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

樹先根：ABEFCGIJD

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

中序遍歷

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

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

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

假設(shè)以二元組(F,C)的形式自上而下、自左而右依次輸入樹的各邊，建立樹的孩子-兄弟鏈表。ABCDEFG例如:對下列所示樹的輸入序列應(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’)可見，算法中需要一個隊(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;}

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

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

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

27ABCEDA^BCDE^^^^^二、先序遍歷樹（森林）的遞歸算法：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)寫的遍歷算法30ABCEDA^BCDE^^^^^三、求樹的深度的算法：31intDepth(CSTreeT){if(T==NULL)return0;else{d1=Depth(T->firstchild);d2=Depth(T->nextsibling);returnmax(d1+1,d2)}三、求樹的深度的算法：32四、輸出樹中所有從根到葉子的路徑的算法:ABCDEFGHIJK例如：對左圖所示的樹，其輸出結(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í)生活中的門牌號碼，可以在紛繁蕪雜的網(wǎng)絡(luò)世界里準(zhǔn)確無誤地把我們指引到我們要訪問的站點(diǎn)。37結(jié)點(diǎn)間的路徑長度：

兩個結(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)到根之間的路徑長度的乘積。6.5哈夫曼樹及其應(yīng)用6.5.1最優(yōu)二叉樹——哈夫曼樹ABCDEFGHIJ38樹的帶權(quán)路徑長度：

(WeightPathLength)

樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和。WPL=(葉到根的平均路徑長度)哈夫曼(huffman)樹：使WPL取最小值的二叉樹，又稱最優(yōu)二叉樹ABCDEFGHIJ203050例：有n個葉子結(jié)點(diǎn)，第i個葉子結(jié)點(diǎn)的權(quán)值為Wi，根到該結(jié)點(diǎn)的路徑長度為Li，則：39例如，給定權(quán)值{5,4,7,2,5}，可生成多棵二叉樹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)二叉樹？

(哈夫曼算法)

(1)根據(jù)n個權(quán)值{w1,w2,…,wn}構(gòu)成n棵二叉樹的集合F={T1,T2,…,Tn}，其中每棵二叉樹Ti只有一個帶權(quán)為Wi的根結(jié)點(diǎn)，其左右子樹均空。(2)在F中選兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)成一棵新的二叉樹，且根結(jié)點(diǎn)的權(quán)值為其左右子樹根結(jié)點(diǎn)的權(quán)值之和。(3)在F中刪除這兩棵樹，同時將新的二叉樹加入F(4)重復(fù)(2)、(3)，直到F只含一棵樹為止。9例如:已知權(quán)值W={5,6,2,9,7}5627257697671392576713925792571667132944哈夫曼樹的應(yīng)用:在解決某些判定問題時的最佳判定算法。例:將學(xué)生百分成績按分?jǐn)?shù)段分級的程序。若學(xué)生成績分布是均勻的，可用二叉樹結(jié)構(gòu)來實(shí)現(xiàn)。a<60a<70a<80a<90不及格中等良好優(yōu)秀及格YNYNYNYN輸入10000個數(shù)據(jù)，則需進(jìn)行28000次比較。讀入一個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é)生成績分布不是均勻的情況：構(gòu)造一棵哈夫曼樹：再將每一比較框的兩次比較改為一次：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個數(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ò))通信中，它作為一種最常用無損壓縮編碼方法，在數(shù)據(jù)壓縮程序中具有非常重要的應(yīng)用。

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

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

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

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

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

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

123456789

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

chardata；

intweight；

intparent，lch，rch；

}NodeType；

//huffman樹結(jié)點(diǎn)類型

typedefchar**HufCode

；

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

NodeType

HufTree[M+1]；

//靜態(tài)三叉鏈表存儲huffman樹1234hcd例：設(shè)有4個結(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個字符的權(quán)值，生成一棵huffman樹。voidhuff_tree(intw[n],HufTree&ht){//w存放權(quán)值for(i=1；i≤n；i++){//哈夫曼樹初始化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個非葉子結(jié)點(diǎn)select(i-1,s1,s2)；

//在ht[1..i-1]中選擇兩個雙親為0并且權(quán)值最小的兩個結(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；

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

hcd;char*cd;‘\0’start0start

‘\0’0

算法2：由huffman樹求n個字符的haffman編碼voidhuf_code(HufCode

&hcd，HufTree

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

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

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

while（f≠0