第06章-樹與二叉樹C

第1章緒論第2章線性表第3章棧和隊列

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

樹和二叉樹

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

教

學

內(nèi)

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

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

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

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

nextsiblingdatafirstchild指向左孩子指向右兄弟問：樹→二叉樹的“連線—抹線—旋轉(zhuǎn)”如何由計算機自動實現(xiàn)？答：用“左孩子右兄弟”表示法來存儲即可。

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

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

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

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

}（即森林），其中每棵二叉樹Ti中只有一個帶權(quán)為wi的根結(jié)點，其左右子樹均空。(2)

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

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

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

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

譯碼的惟一性問題

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

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

結(jié)點引向其左孩子的分支標‘0’，引向其右孩子的分支標‘1’；

每

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

0,1

序列。如

此得到的即為二進制前綴編碼。

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

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

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

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

用哈夫曼樹設(shè)計總長最短的二進制前綴編碼

由哈夫曼樹得到的二進制前綴編碼稱為哈夫曼編碼

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

譯碼

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

00110110

T

;

A

C

S電文為“1101000”譯文只能是“CAT”32嚴習題集6.26：設(shè)通信用的電文由字符集{a,b,c,d,e,f,g,h}中的字母構(gòu)成，這8個字母在電文中出現(xiàn)的概率分別為{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}，試為這8個字母設(shè)計哈夫曼編碼。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;//動態(tài)分配數(shù)組存儲赫夫曼樹typedefchar**HuffmanCode;建立Huffman樹及求Huffman編碼的算法Huffman樹沒有度為1的結(jié)點

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

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

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

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

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

m=2*n-1;

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

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

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

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é)點循環(huán)退出時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é)點

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

//建赫夫曼樹，(建立HT靜態(tài)鏈表中的鏈){Select(HT,i-1,s1,s2);//在HT[1～i-1]中選擇parent//為0且weight最小的兩個結(jié)點，序號分別為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)//逐個字符求赫夫曼編碼

{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復制編碼串到HC}

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

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

從葉結(jié)點開始，找到其雙親，判定是雙親的左孩子或右孩子，確定編碼，直到根結(jié)束。c對應的哈夫曼編碼：符編碼頻率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)+