第6章-樹(shù)與二叉樹(shù)3數(shù)據(jù)結(jié)構(gòu)

第六章樹(shù)和二叉樹(shù)本講主要內(nèi)容：

樹(shù)和森林哈夫曼樹(shù)及其應(yīng)用6.4樹(shù)和森林6.4.1樹(shù)的存儲(chǔ)結(jié)構(gòu)：雙親表示法：除根結(jié)點(diǎn)外的每個(gè)結(jié)點(diǎn)都只有唯一的雙親RABCDEFGHKRDCFHGKABE－1000311666數(shù)組下標(biāo)0123456789樹(shù)的雙親表存儲(chǔ)表示#defineMAX_TREE_SIZE100;Typedef

struct

PTNode{

TElemTypedata;

intpatent;}//PTNode;Typedef

struct{

PTNodenodes[MAX_TREE_SIZE];

intr,n;}//PTree;優(yōu)點(diǎn)：parent(T,x),Root(x)操作容易實(shí)現(xiàn)確定：求結(jié)點(diǎn)的孩子時(shí)需要遍歷整個(gè)結(jié)構(gòu)孩子表示法：datachild1child2child3childd······datadegreechild1child2childd······D為樹(shù)的度，結(jié)點(diǎn)同構(gòu)，空間浪費(fèi)結(jié)點(diǎn)不同構(gòu)，空間不浪費(fèi)，操作不方便RDCFHGKABE012345678935^6^^^^^^^012^789^適用于涉及孩子的操作樹(shù)的孩子鏈表存儲(chǔ)表示Typedef

struct

CTNode{//孩子結(jié)點(diǎn)

intchild;

struct

CTNode*next; }*childptr;Typedef

struct{

TElemTypedata;

childptr

firstchild;//孩子鏈表頭指針 }CTBox;Typedef

struct{

CTBoxnodes[MAX_TREE_SIZE];

intn,r; //結(jié)點(diǎn)數(shù)和根的位置； }//CTree;RDCFHGKABE4440－10266635^6^^^^^^^012^789^0123456789帶雙親的孩子鏈表孩子表示法和雙親表示法結(jié)合起來(lái)，即帶雙親的孩子鏈表孩子兄弟表示法：以二叉鏈表表示每個(gè)結(jié)點(diǎn)有兩個(gè)鏈域：firstchild和nextsibling：第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)Typedef

struct

CSNode{ElemTypedata;Struct

CSNode*firstchild,*nextsibling;}CSNode,*CSTree;R^ADBECFGHK^^^^^^^^RABCDEFGHK6.4.2森林與二叉樹(shù)的轉(zhuǎn)換ABCEDABCED^ABCDE^^^^^任何一棵與樹(shù)對(duì)應(yīng)的二叉樹(shù)，其右子樹(shù)都為空孩子兄弟表示法對(duì)應(yīng)的二叉樹(shù)樹(shù)轉(zhuǎn)換為二叉樹(shù)森林與二叉樹(shù)的對(duì)應(yīng)關(guān)系A(chǔ)BCDEFGIHJEFABCDGIHJABCDEFGIHJ樹(shù)與二叉樹(shù)對(duì)應(yīng)森林與二叉樹(shù)森林/樹(shù)與二叉樹(shù)之間的相互轉(zhuǎn)換森林轉(zhuǎn)換成二叉樹(shù)：若F={T1,T2,···Tm}是森林，則按如下規(guī)則轉(zhuǎn)換成一棵二叉樹(shù)B=(root,LB,RB):(1)若F為空，則m=0,B為空；(2)若F非空，則B的根root是森林中的第一顆樹(shù)的根ROOT(T1);B的左子樹(shù)LB是從T1中根結(jié)點(diǎn)的子樹(shù)森林F1={T11,T12,···,T1m1}轉(zhuǎn)換而成的二叉樹(shù)；B的右子樹(shù)RB是從森林F’={T2,T3,···,Tm}轉(zhuǎn)換而成的二叉樹(shù)二叉樹(shù)轉(zhuǎn)換成森林：6.4.3樹(shù)和森林的遍歷樹(shù)的遍歷：先根遍歷后根遍歷森林的遍歷：先序遍歷森林中序遍歷森林：（1）中序遍歷森林中的第一顆樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林；（2）訪問(wèn)第一顆樹(shù)的根結(jié)點(diǎn)；（3）中序遍歷剩余的樹(shù)構(gòu)成的森林。ABCDEFGIHJ1、樹(shù)的先根次序訪問(wèn)為二叉樹(shù)的先序遍歷。樹(shù)的后根次序訪問(wèn)為二叉樹(shù)的中序遍歷。

2、森林的先根次序訪問(wèn)序列對(duì)應(yīng)為二叉樹(shù)的先序遍歷序列。森林的中根次序訪問(wèn)序列對(duì)應(yīng)為二叉樹(shù)的中序遍歷序列。

兩個(gè)結(jié)論：畫(huà)出和下列已知序列對(duì)應(yīng)的樹(shù)T：樹(shù)的先根次序訪問(wèn)序列為：GFKDAIEBCHJ樹(shù)的后根次序訪問(wèn)序列為：DIAEKFCJHBG畫(huà)出和下列已知序列對(duì)應(yīng)的森林F：森林的先根次序訪問(wèn)序列為：ABCDEFGHIJKL森林的中根次序訪問(wèn)序列為：CBEFDGAJIKLH原則：森林的先序/中序遍歷，即對(duì)應(yīng)二叉樹(shù)的先序/中序遍歷先做二叉樹(shù)：畫(huà)出和下列已知序列對(duì)應(yīng)的森林F:

森林的先序次序訪問(wèn)序列為：ABCDEFGHIJKL

森林的中序次序訪問(wèn)序列為：CBEFDGAJIKLHACBEFDGJIKLHAJIKLBEFDGCHBHCDIAEFGJKLBHCDIAGJEFKL二叉樹(shù)先ABCDEFGHIJKL中CBEFDGAJIKLH森林BHCDIGJEFKLABHCDIAGJEFKL6.6哈夫曼樹(shù)及其應(yīng)用哈夫曼樹(shù)：最優(yōu)樹(shù)，帶權(quán)路徑長(zhǎng)度最短的樹(shù)。6.6.1最優(yōu)二叉樹(shù)（哈夫曼樹(shù)）路徑：從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成兩個(gè)結(jié)點(diǎn)之間的路徑；路徑長(zhǎng)度：路徑上的分支數(shù)目；樹(shù)的路徑長(zhǎng)度：從樹(shù)根到每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和

其中：wk為k個(gè)結(jié)點(diǎn)的權(quán)值最優(yōu)二叉樹(shù)(哈夫曼樹(shù))：帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹(shù)如何構(gòu)造哈夫曼樹(shù)abcd7524abcd7524abcd7524不同帶權(quán)路徑長(zhǎng)度的二叉樹(shù)先看下面的幾棵二叉樹(shù)，考慮他們的區(qū)別WPL=(7+5+2+4)*2=36WPL=46WPL=35再看一個(gè)實(shí)際的問(wèn)題：將百分制轉(zhuǎn)換成五分制的程序if(a<60)b=“bad”;elseif(a<70)b=“pass”;elseif(a<80)b=“general”; elseif(a<90)b=“good”; elseb=“excellent”;a<60不及格a<70及格a<80中等a<90良好優(yōu)良問(wèn)：在成績(jī)分布如下的情況下，程序的操作時(shí)間會(huì)怎樣？分?jǐn)?shù)0~5960~6970~7980~8990~100比例數(shù)0.050.150.400.300.10a<80a<60中等40良好30不及格5優(yōu)秀10及格15a<90a<70YNYYNNNY70≤a<8080≤a<9060≤a<70a<60中等40良好30不及格5優(yōu)秀10及格15YYYYNNNN分別以5，15，40，30，10的權(quán)構(gòu)造一棵有5個(gè)結(jié)點(diǎn)的哈夫曼樹(shù)將兩次比較分開(kāi)WPL=205WPL=220然后，看構(gòu)造哈夫曼樹(shù)的過(guò)程abcd7524cd24ab756cd24b511a7abcd752418最后我們可以總結(jié)一個(gè)哈夫曼算法：(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ù)，且置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和。(3)在F中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入F中。(4)重復(fù)(2)(3),直到F只含一棵樹(shù)為止。這顆樹(shù)就是哈夫曼樹(shù)。abcd7524cd24ab756編碼問(wèn)題：等長(zhǎng)的二進(jìn)制編碼：如：字符A/B/C/D編碼：00011011則：在翻譯電文時(shí)2位一組即可不等長(zhǎng)的二進(jìn)制編碼：如：字符A/B/C/D編碼：000101則：如果收到電文：0000，得到譯文就不是唯一的結(jié)論：若要設(shè)計(jì)長(zhǎng)度不等的編碼，則必須是任一字符的編碼都不是另一個(gè)編碼的前綴——前綴編碼6.6.2哈夫曼編碼ABCD111000編碼A(0)B(10)C(110)D(111)問(wèn)：編碼{00,01,10,11},{0,1,00,11},{0,10,110,111}，哪一組不是前綴碼？前綴編碼示例哈夫曼樹(shù)的特點(diǎn)：沒(méi)有度為1的結(jié)點(diǎn)，稱為嚴(yán)格的二叉樹(shù)哈夫曼樹(shù)與哈夫曼編碼的存儲(chǔ)表示Typedef

struct{ unsignedintweight; unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹(shù)Typedefchar*HuffmanCode;//動(dòng)態(tài)分配哈夫曼編碼表ABCD1110007700560025004500663411725170161234567例如：70005000200040000000000000001234567abcd7524cd24ab756cd24b511a7abcd752418700050002500450060340000000012345677000560025004500663411025000012345677700560025004500663411725180161234567哈夫曼樹(shù)的構(gòu)造過(guò)程構(gòu)造哈夫曼樹(shù)，求哈夫曼編碼的算法voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){//w存放n個(gè)字符的權(quán)值，構(gòu)造哈夫曼樹(shù)HT,求n個(gè)字符的哈夫曼編碼表if(n<=1)return;m=2*n-1;//n個(gè)字符的哈夫曼樹(shù)有（2*n-1）個(gè)結(jié)點(diǎn)HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(p=HT,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;i<=m;++i){//構(gòu)造哈夫曼樹(shù) select(HT,i-1,s1,s2);//選擇parent為0且權(quán)值最小的兩個(gè)結(jié)點(diǎn)：s1,s2 HT[s1].parnet=i;HT[s2].parent=i; HT[i].child=s1;HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s1].weight; }*****//從葉子到根逆向求每個(gè)字符的哈夫曼編碼HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char));cd[n-1]=“\0”；for(i=1;i<=n;++i){ start=n-1; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) if(HT[f].lchild==c)cd[--start]=“0”; elsecd[--start]=“1”;

Hc[i]=(chat*)malloc((n-start)*sizeof(char));

atrcpy(HC[i],&cd[start]);}free(cd);}//HuffmanCoding7700560025004500663411725170161234567*****從根結(jié)點(diǎn)遍歷哈夫曼樹(shù)，求哈夫曼編碼7700560025004500663411725170161234567ABCD111000*****算法：HC=(HuffmanCode)malloc((n+1)*sizeof(char*));P=m;cdlen=0;For(i=1;i<=m;++i)HT[i].weight=0;While(p){ if(HT[p].weight==0){ HT[p].weight=1; if(HT[p].lchild!=0){p=HT[p].lchild;cd[cdlen++]=“0”;} elseif(HT[p].rchild==0){ HC[p]=(char*)malloc((cdlen+1)*sizeof(char));

cd[cdlen]=“\0”;atrcpy(HC[p],cd);} }elseif(HT[p].weight==1{

HT[p].weight=2; if(HT[p].rchild!=0){p=HT[p].rchild;cd[cdlen++]=“1”;} }else{HT[p].weight=0;p=HT[p].parent;--cdlen;}}//while*****例1：電文的譯碼：分解電文中字符串，從根結(jié)點(diǎn)出發(fā)，按字符0/1確定左、右孩子，直到葉子結(jié)點(diǎn)。分析：假設(shè)電文為：101110110111A700B600C500D500663411725170161234567j=1;i=1While(j<=code.len){P=m;while(p->lchild)||(p->rchild){ ifcode[j]=0p=p->lchild

elsep=p->rchild; j=j+1}

ABCD111000例2：已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符，其概率分布為0.05,0.