第06章-樹與二叉樹C

第1章緒論第2章線性表第3章棧和隊(duì)列

第4章串第5章數(shù)組和廣義表第6章

樹和二叉樹

第7章圖第9章查找第10章排序目錄1

教

學(xué)

內(nèi)

容1、樹和森林的概念2、二叉樹的定義、性質(zhì)及運(yùn)算；3、二叉樹的存儲(chǔ)結(jié)構(gòu)4、遍歷二叉樹5、線索二叉樹6、樹、森林、森林與二叉樹的轉(zhuǎn)換7、哈夫曼樹、哈夫曼編碼2本周作業(yè)習(xí)題集第一次作業(yè)：6.7，6.8，6.15,6.16,6.29,6.42,6.45.第二次作業(yè)：6.26，6.27,6.29,6.44,6.47，6.656.樹和森林樹和森林與二叉樹的轉(zhuǎn)換樹和森林的存儲(chǔ)方式樹和森林的遍歷4方法：加線—抹線—旋轉(zhuǎn)abeidfhgcabeidfhgc兄弟相連長(zhǎng)兄為父孩子靠左樹和森林與二叉樹的轉(zhuǎn)換回顧1：樹如何轉(zhuǎn)為二叉樹？左孩子—右兄弟表示法5回顧2：二叉樹怎樣還原為樹？abeidfhgc要點(diǎn)：逆操作，把所有右孩子變?yōu)樾值埽?/p>

abdefhgic6法一：①各森林先各自轉(zhuǎn)為二叉樹；②依次連到前一個(gè)二叉樹的右子樹上。討論1：森林如何轉(zhuǎn)為二叉樹？即F={T1,T2,…,Tm}B={root,LB,RB}法二：森林直接變兄弟，再轉(zhuǎn)為二叉樹（參見(jiàn)教材P138圖6.17，兩種方法都有轉(zhuǎn)換示意圖）法一和法二得到的二叉樹是完全相同的、惟一的。7ABCDEFGHJIABCDEFGHJIABCDEFGHJI森林轉(zhuǎn)二叉樹舉例：

（用法二，森林直接變兄弟，再轉(zhuǎn)為二叉樹）兄弟相連長(zhǎng)兄為父頭樹為根孩子靠左A8ABCDEFGHJI討論2：二叉樹如何還原為森林？要點(diǎn)：把最右邊的子樹變?yōu)樯?，其余右子樹變?yōu)樾值?/p>

即B={root,LB,RB}F={T1,T2,…,Tm}ABCDEFGHJIEFABCDGHJI9樹和森林的存儲(chǔ)方式樹有三種常用存儲(chǔ)方式：①雙親表示法②孩子表示法③孩子—兄弟表示法

nextsiblingdatafirstchild指向左孩子指向右兄弟問(wèn)：樹→二叉樹的“連線—抹線—旋轉(zhuǎn)”如何由計(jì)算機(jī)自動(dòng)實(shí)現(xiàn)？答：用“左孩子右兄弟”表示法來(lái)存儲(chǔ)即可。

存儲(chǔ)的過(guò)程就是樹轉(zhuǎn)換為二叉樹的過(guò)程！10abecdfhgbacedfgh例如：11樹和森林的遍歷樹的遍歷例如：abdec先根序列：后根序列：abcdebdcea深度優(yōu)先遍歷（先根、后根）廣度優(yōu)先遍歷（層次）先根遍歷訪問(wèn)根結(jié)點(diǎn)；依次先根遍歷根結(jié)點(diǎn)的每棵子樹。后根遍歷依次后根遍歷根結(jié)點(diǎn)的每棵子樹；訪問(wèn)根結(jié)點(diǎn)。樹沒(méi)有中序遍歷（因子樹不分左右）12討論：樹若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否一樣？abdec先序遍歷：后序遍歷：中序遍歷：decbaabdecabcdebdcea1.

樹的先根遍歷與二叉樹的先序遍歷相同；2.樹的后根遍歷相當(dāng)于二叉樹的中序遍歷；3.樹沒(méi)有中序遍歷，因?yàn)樽訕錈o(wú)左右之分。結(jié)論：樹的先根序列：abcde樹的后根序列：bdcea13先序遍歷若森林為空，返回；訪問(wèn)森林中第一棵樹的根結(jié)點(diǎn)；先根遍歷第一棵樹的根結(jié)點(diǎn)的子樹森林；先根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。森林的遍歷ABCDEFGHJI深度優(yōu)先遍歷（先序、中序）廣度優(yōu)先遍歷（層次）中序遍歷若森林為空，返回；中根遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林；訪問(wèn)第一棵樹的根結(jié)點(diǎn)；中根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。14討論：若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否相同？例如：ABCDEFGHJI先序序列：中序序列：ABCDEFGHIJB

CDAFEHJIGABCDEFGHJI先序序列：中序序列：ABCDEFGHIJBCDAFEHJIG結(jié)論：森林的先序和中序遍歷在兩種方式下的結(jié)果相同。15什么是帶權(quán)樹？abdc7524即葉子帶有權(quán)值。例如：最優(yōu)二叉樹(哈夫曼樹)如果是帶權(quán)路徑長(zhǎng)度最短的樹167.二叉樹的應(yīng)用與哈弗曼編碼7.Huffman樹及其應(yīng)用一、Huffman樹的構(gòu)建二、Huffman編碼三、算法實(shí)現(xiàn)最優(yōu)二叉樹Huffman樹Huffman編碼帶權(quán)路徑長(zhǎng)度最短的樹不等長(zhǎng)編碼是通信中最經(jīng)典的壓縮編碼17樹的帶權(quán)路徑長(zhǎng)度如何計(jì)算？WPL=

wklkk=1nabdc7524(a)cdab2457(b)bdac7524(c)WPL=WPL=WPL=Huffman樹是WPL最小的樹樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和36463518構(gòu)造Huffman樹的基本思想：權(quán)值大的結(jié)點(diǎn)用短路徑，權(quán)值小的結(jié)點(diǎn)用長(zhǎng)路徑。一、Huffman樹（最優(yōu)二叉樹）路徑：路徑長(zhǎng)度：樹的路徑長(zhǎng)度：帶權(quán)路徑長(zhǎng)度：樹的帶權(quán)路徑長(zhǎng)度：Huffman樹：由一結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支所構(gòu)成。路徑上的分支數(shù)目。從樹根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。結(jié)點(diǎn)到根的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積（WPL）若干術(shù)語(yǔ)：debacfg即樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和帶權(quán)路徑長(zhǎng)度最小的樹。例如：a→e的路徑長(zhǎng)度＝樹長(zhǎng)度＝210Huffman常譯為赫夫曼、霍夫曼、哈夫曼等WeightedPathLength19構(gòu)造Huffman樹的步驟（即Huffman算法）：由給定的n個(gè)權(quán)值{w1,w2,…,wn}構(gòu)成n棵二叉樹的集合F={T1,T2,…,Tn

}（即森林），其中每棵二叉樹Ti中只有一個(gè)帶權(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中刪去這兩棵樹，同時(shí)將新得到的二叉樹加入F中。(4)重復(fù)(2)和(3),直到F只含一棵樹為止。這棵樹便是Huffman樹。20對(duì)權(quán)值進(jìn)行合并、刪除與替換——在權(quán)值集合{7,5,2,4}中，總是合并當(dāng)前值最小的兩個(gè)權(quán)具體操作步驟：a.初始b.合并{2}{4}c.合并{5}{6}d.合并{7}{11}誰(shuí)左誰(shuí)右？不規(guī)定就不會(huì)惟一219例題：已知權(quán)值W={5,6,2,9,7},建立對(duì)應(yīng)的Huffman樹562792571667132922Huffman樹的應(yīng)用：例：設(shè)有4個(gè)字符d,i,a,n，出現(xiàn)的頻度分別為7,5,2,4，怎樣編碼才能使它們組成的報(bào)文長(zhǎng)度最短？法1：等長(zhǎng)編碼（如二進(jìn)制編碼）令d=00，i=01，a=10，n=11，則：WPL1＝2bit×(7＋5＋2＋4）＝36法2：不等長(zhǎng)編碼（如Huffman編碼）令d=0;i=10,a=110,n=111，則：WPL2=1bit×7＋2bit×5+3bit×(2+4)=35明確：要實(shí)現(xiàn)Huffman編碼，就要先構(gòu)造Huffman樹討論：Huffman樹有什么用？頻度高的信息用短碼，低的用長(zhǎng)碼，傳輸效率肯定高！最小冗余編碼、信息高效傳輸23按左“0”右“1”

對(duì)Huffman樹的所有分支編號(hào)dain111000Huffman編碼結(jié)果：d=0,i=10,a=110,n=111WPL=1bit×7＋2bit×5+3bit×(2+4)=35（小于等長(zhǎng)碼的WPL=36）特征：每一碼不會(huì)是另一碼的前綴，譯碼時(shí)可惟一復(fù)原Huffman編碼也稱為前綴碼Huffman編碼24哈夫曼編碼

哈夫曼樹的應(yīng)用很廣，哈夫曼編碼就是其在電訊通信中的應(yīng)用之一。在電訊通信業(yè)務(wù)中，通常用二進(jìn)制編碼來(lái)表示字母或其他字符，并用這樣的編碼來(lái)表示字符序列。例：如果需傳送的電文為‘ABACCDA’，它只用到四種字符，用兩位二進(jìn)制編碼便可分辨。假設(shè)A,B,C,D的編碼分別為00,01,10,11，則上述電文便為‘00010010101100’（共14位），譯碼員按兩位進(jìn)行分組譯碼，便可恢復(fù)原來(lái)的電文。能否使編碼總長(zhǎng)度更短呢？

25實(shí)際應(yīng)用中各字符的出現(xiàn)頻度不相同數(shù)據(jù)的最小冗余編碼問(wèn)題用短（長(zhǎng)）編碼表示頻率大（小）的字符使得編碼序列的總長(zhǎng)度最小，使所需總空間量最少若假設(shè)A,B,C,D的編碼分別為0，00，1，01，則電文‘ABACCDA’便為‘000011010’（共9位）?？勺g為‘BBCCDA’、‘ABACCDA’、‘AAAACCACA’存在多義性26要求任一字符的編碼都不能是另一字符編碼的前綴！這種編碼稱為前綴編碼（其實(shí)是非前綴碼）。

譯碼的惟一性問(wèn)題

利用最優(yōu)二叉樹可以很好地解決上述兩個(gè)問(wèn)題在編碼過(guò)程要考慮兩個(gè)問(wèn)題數(shù)據(jù)的最小冗余編碼問(wèn)題譯碼的惟一性問(wèn)題27

以電文中的字符作為葉子結(jié)點(diǎn)構(gòu)造二叉樹。然后將二叉樹中

結(jié)點(diǎn)引向其左孩子的分支標(biāo)‘0’，引向其右孩子的分支標(biāo)‘1’；

每

個(gè)字符的編碼即為從根到每個(gè)葉子的路徑上得到的

0,1

序列。如

此得到的即為二進(jìn)制前綴編碼。

用二叉樹設(shè)計(jì)二進(jìn)制前綴編碼例：

ABCD010101編碼：A：0B：10C：110D：111任意一個(gè)葉子結(jié)點(diǎn)都不可能在其它葉子結(jié)點(diǎn)的路徑中。28假設(shè)各個(gè)字符在電文中出現(xiàn)的次數(shù)（或頻率）為wi

，其編碼長(zhǎng)度為li，電文中只有n種字符，編碼總長(zhǎng)為：葉子結(jié)點(diǎn)的權(quán)從根到葉子的路徑長(zhǎng)度設(shè)計(jì)電文總長(zhǎng)最短的編碼設(shè)計(jì)哈夫曼樹（以n

種字符出現(xiàn)的頻率作權(quán)）

用哈夫曼樹設(shè)計(jì)總長(zhǎng)最短的二進(jìn)制前綴編碼

由哈夫曼樹得到的二進(jìn)制前綴編碼稱為哈夫曼編碼

29解：

ACBD000111編碼：A：0C：10B：110D：111例：如果需傳送的電文為‘ABACCDA’，即：A,B,C,D

的頻率（即權(quán)值）分別為0.43,0.14,0.29,0.14，試構(gòu)造哈夫曼編碼。則電文‘ABACCDA’便為‘0110010101110’（共13位）。30解：

EBD編碼：A：11C：10E：00B：010D：011例：如果需傳送的電文為‘ABCACCDAEAE’，即：A,B,C,D,E的頻率（即權(quán)值）分別為

0.36,0.1,0.27,0.1,0.18，試構(gòu)造哈夫曼編碼。則電文‘ABCACCDAEAE’便為‘110101011101001111001100’（共24位，比33位短）。CA1111000031

譯碼

從哈夫曼樹根開(kāi)始，對(duì)待譯碼電文逐位取碼。若編碼是“0”，則向左走；若編碼是“1”，則向右走，一旦到達(dá)葉子結(jié)點(diǎn)，則譯出一個(gè)字符；再重新從根出發(fā)，直到電文結(jié)束。

00110110

T

;

A

C

S電文為“1101000”譯文只能是“CAT”32嚴(yán)習(xí)題集6.26：設(shè)通信用的電文由字符集{a,b,c,d,e,f,g,h}中的字母構(gòu)成，這8個(gè)字母在電文中出現(xiàn)的概率分別為{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}，試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。330.070.190.020.060.320.030.210.100.070.190.020.060.320.030.210.100.050.070.190.020.060.320.030.210.100.050.110.070.190.020.060.320.030.210.100.050.110.17340.070.190.020.060.320.030.210.100.050.110.170.280.070.190.020.060.320.030.210.100.050.110.170.280.40350.070.190.020.060.320.030.210.100.050.110.170.280.400.60a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.100.050.110.170.280.400.601.0000000001111111a=1010b=00c=10000d=1001e

=11f=10001g=01h=101136WPL=2.61typedefstruct{ unsignedintweight; unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼樹typedefchar**HuffmanCode;建立Huffman樹及求Huffman編碼的算法Huffman樹沒(méi)有度為1的結(jié)點(diǎn)

一棵有n0個(gè)葉子結(jié)點(diǎn)的Huffman樹共有2n0-1個(gè)結(jié)點(diǎn)設(shè)共有n個(gè)節(jié)點(diǎn)，則n=n0+n2;(沒(méi)有度為1的節(jié)點(diǎn)，n1=0)度之和=n-1=2n2

n-1=2(n-n0)n=2n0-1

可以存儲(chǔ)在一個(gè)大小為2n-1的一維數(shù)組中。

節(jié)點(diǎn)權(quán)值，父節(jié)點(diǎn)，左孩子節(jié)點(diǎn)和右孩子節(jié)點(diǎn)37voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){//w存放n個(gè)字符的權(quán)值，構(gòu)造赫夫曼樹HT,并求出n個(gè)字符的赫夫曼編碼HC

if(n<=1)return;//n為字符數(shù)目，

m=2*n-1;

//m為結(jié)點(diǎn)數(shù)目

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//HT存放Huffman樹結(jié)構(gòu)，0號(hào)單元未用,其余前n個(gè)單元

//存放樹的葉子結(jié)點(diǎn)，n-1個(gè)單元存放內(nèi)部結(jié)點(diǎn)

for(p=HT,i=1;i<=n;++i,++p,++w)

{p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;}

//*p={*w,0,0,0}；初始化HT中的葉結(jié)點(diǎn)循環(huán)退出時(shí)i=n+1;38for(;i<=m;++i,++p){p->weight=0;p->parent=0;p->lchild=0;p->rchild=0;}

//*p={0,0,0,0};初始化HT中的內(nèi)部結(jié)點(diǎn)

for(i=n+1;i<=m;++i)

//建赫夫曼樹，(建立HT靜態(tài)鏈表中的鏈){Select(HT,i-1,s1,s2);//在HT[1～i-1]中選擇parent//為0且weight最小的兩個(gè)結(jié)點(diǎn)，序號(hào)分別為s1和s2 HT[s1].parent=i;HT[s2].parent=i; HT[i].lchild=s1;HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight;}39

//從葉子到根逆向求赫夫曼編碼

HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char));cd[n-1]=‘\0’;//編碼結(jié)束符

for(i=1;i<=n;++i)//逐個(gè)字符求赫夫曼編碼

{start=n-1;//編碼結(jié)束符位置

for(c=i,f=HT[c].parent;f!=0;c=f,f=HT[f].parent)//從葉子到根逆向求編碼

if(HT[f].lchild==c)cd[--start]='0';

elsecd[--start]='1';HC[i]=(char*)malloc((n-start)*sizeof(char));strcpy(HC[i],&cd[start]);//從cd復(fù)制編碼串到HC}

free(cd);//釋放工作空間}//HuffanCoding40Huffman編碼舉例解：先將概率放大100倍，以方便構(gòu)造哈夫曼樹。放大后的權(quán)值集合w={7,19,2,6,32,3,21,10}，按哈夫曼樹構(gòu)造規(guī)則（合并、刪除、替換），可得到哈夫曼樹。例1【嚴(yán)題集6.26③】：假設(shè)用于通信的電文僅由8個(gè)字母{a,b,c,d,e,f,g,h}構(gòu)成，它們?cè)陔娢闹谐霈F(xiàn)的概率分別為{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10

}，試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。如果用0～7的二進(jìn)制編碼方案又如何？【類同P148例2】0000—00—2810010717000—000—000—000—000—-00000000r0010002100300320060020019007lpw13121011987654321116235211940bcadegfh√√599√√111010491728√√√√√√40√√60100361811111212101132602713131515√√141451213141415w={7,19,2,6,32,3,21,10}請(qǐng)注意：哈夫曼樹樣式不惟一！w={7,19,2,6,32,3,21,10}在機(jī)內(nèi)存儲(chǔ)形式為:2810010717000—000—000—000—000—-00000000r0010002100300320060020019007lpw13121011987654321116235211940badegfh√√599√√111010491728√√√√√√40√√60100361811111212101132602713131515√√1414512131401415如何形成編碼?例如:c的編碼:

從葉結(jié)點(diǎn)開(kāi)始，找到其雙親，判定是雙親的左孩子或右孩子，確定編碼，直到根結(jié)束。c對(duì)應(yīng)的哈夫曼編碼：符編碼頻率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10符編碼頻率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.101110001101011001011011011111000001010011100101110111Huffman碼的WPL＝2(0.19+0.32+0.21)+