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

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

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

0a-11b02

c03d14e15f26g47h4

8i43

typedefstructPTNode{Elemdata;

intparent;//雙親位置域

}PTNode;#defineMAX_TREE_SIZE100結點結構:C語言的類型描述:

dataparent4typedefstruct{PTNodenodes[MAX_TREE_SIZE];

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

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

c1c2

…ckdatac1c2c3

…cm(2)每個結點有幾個孩子，就有幾個指針。二、孩子表示法（鏈式存儲）問題：會有太多的空指針！(3)將每個結點的孩子結點排列起來，連接成一個單鏈表。n個結點有n個孩子鏈表，n個孩子鏈表的頭指針可放在數(shù)組中，稱為孩子鏈表。60a12

1b342c53d4e6785f6g7h8i孩子鏈表aedbihgcf0213456787typedefstructCTNode{

intchild;

structCTNode*nextchild;}*ChildPtr;孩子結點結構:

childnextchildC語言的類型描述:8

typedefstruct{Elemdata;ChildPtrfirstchild;//孩子鏈的頭指針}CTBox;雙親結點結構

datafirstchildtypedefstruct{CTBoxnodes[MAX_TREE_SIZE];

intn,r;//結點數(shù)和根結點的位置

}CTree;樹結構:帶雙親的孩子鏈表：將雙親表示法和孩子表示法結合起來。aedbihgcf0

a-112

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

a

b

c

d

e

f

g

h

i

11typedefstructCSNode{Elemdata;

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

firstchilddatanextsibling12ABCDEFGrootABCEDFGABCEDFG

畫出以下存儲結構root13樹ABCED二叉樹ABCEDA^BCDE^^^^^6.4.2森林與二叉樹的轉換

從樹的鏈表表示的定義可知，任何一棵與樹對應的二叉樹，其右子樹必空。若把森林中第二棵樹的根結點看成是第一棵樹的根結點的兄弟，則可導出森林和二叉樹的關系。森林

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

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

樹先根：ABEFCGIJD

后根：EFBIGJCDA二叉樹先序遍歷中序遍歷ABCFEGDJIABCFEGDJI181.森林中第一棵樹的根結點；2.森林中第一棵樹的子樹森林；3.森林中其它樹構成的森林。可以分解成三部分:森林BCDEFGHIJK森林的遍歷19若森林不空，則訪問森林中第一棵樹的根結點;先序遍歷森林中第一棵樹的子樹森林；先序遍歷森林中(除第一棵樹之外)其余樹構成的森林。先序遍歷即：依次從左至右對森林中的每一棵樹進行先根遍歷。20

中序遍歷

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

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

和二叉樹類似，不同的定義相應有不同的算法。

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

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

;

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

CSNode；

p->data=ch;//創(chuàng)建結點

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

if(fa==

)T=p;//所建為根結點

else{

}//非根結點的情況

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

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

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

//鏈接第一個孩子結點else

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

//鏈接其它孩子結點

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例如：對左圖所示的樹，其輸出結果應為：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)實生活中的門牌號碼，可以在紛繁蕪雜的網(wǎng)絡世界里準確無誤地把我們指引到我們要訪問的站點。37結點間的路徑長度：

兩個結點之間的分支數(shù)。結點的權值：

附加在結點上的信息。結點帶權路徑：

結點上權值與該結點到根之間的路徑長度的乘積。6.5哈夫曼樹及其應用6.5.1最優(yōu)二叉樹——哈夫曼樹ABCDEFGHIJ38樹的帶權路徑長度：

(WeightPathLength)

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

(哈夫曼算法)

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

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

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

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

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

，因為：n1=0,n2=n0-1,

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

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

123456789

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

chardata；

intweight；

intparent，lch，rch；

}NodeType；

//huffman樹結點類型

typedefchar**HufCode

；

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

NodeType

HufTree[M+1]；

//靜態(tài)三叉鏈表存儲huffman樹1234hcd例：設有4個結點a、b、c、d，權值分別為(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個字符的權值，生成一棵huffman樹。voidhuff_tree(intw[n],HufTree&ht){//w存放權值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++){

//構造n-1個非葉子結點select(i-1,s1,s2)；

//在ht[1..i-1]中選擇兩個雙親為0并且權值最小的兩個結點,//最小結點位置為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’；//編碼結束符

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

while（f≠0