方案一二叉樹的建立和遍歷

1、1具體內(nèi)容：先生成一棵二叉樹，再用中序遍歷方式打印每個具體內(nèi)容：先生成一棵二叉樹，再用中序遍歷方式打印每個結(jié)點(diǎn)值，并統(tǒng)計(jì)其葉子結(jié)點(diǎn)的個數(shù)結(jié)點(diǎn)值，并統(tǒng)計(jì)其葉子結(jié)點(diǎn)的個數(shù)。具體內(nèi)容：先生成一棵哈夫曼樹，再打印各字符對應(yīng)的哈夫具體內(nèi)容：先生成一棵哈夫曼樹，再打印各字符對應(yīng)的哈夫曼編碼。曼編碼。具體內(nèi)容：參見嚴(yán)題集具體內(nèi)容：參見嚴(yán)題集P149 實(shí)習(xí)實(shí)習(xí)5.2要求，或參見自測卷要求，或參見自測卷（三個方案由易到難，可自選，參見自測題集（三個方案由易到難，可自選，參見自測題集實(shí)驗(yàn)二實(shí)驗(yàn)二資料）資料）2喻信課堂網(wǎng)址：喻信課堂網(wǎng)址：8:8000/海豚之家網(wǎng)址：海豚之家網(wǎng)址：

2、3第第6 6章章 樹和二叉樹樹和二叉樹（Tree & Binary Tree）6.1 樹的基本概念樹的基本概念6.2 二叉樹二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 樹和森林樹和森林6.5 Huffman樹及其應(yīng)用樹及其應(yīng)用4先介紹二叉樹的典型應(yīng)用先介紹二叉樹的典型應(yīng)用平衡樹平衡樹排序樹排序樹字典樹字典樹判定樹判定樹帶權(quán)樹帶權(quán)樹最優(yōu)樹最優(yōu)樹由字符串構(gòu)成的二叉排序樹由字符串構(gòu)成的二叉排序樹特點(diǎn)特點(diǎn)：分支查找樹（例如：分支查找樹（例如1212個球如何只稱個球如何只稱3 3次次便分出輕重）便分出輕重）特點(diǎn)特點(diǎn)：路徑帶權(quán)值（例如長度）：路徑帶權(quán)值（例如長度）是帶權(quán)路徑長

3、度最短的樹，又稱是帶權(quán)路徑長度最短的樹，又稱 HuffmanHuffman樹，樹，用途之一是通信中的壓縮編碼。用途之一是通信中的壓縮編碼。特點(diǎn)特點(diǎn)：所有結(jié)點(diǎn)左右子樹深度差：所有結(jié)點(diǎn)左右子樹深度差11特點(diǎn)特點(diǎn)：所有結(jié)點(diǎn)：所有結(jié)點(diǎn)“左小右大左小右大”5什么是平衡二叉樹什么是平衡二叉樹（ 又稱又稱AVL AVL 樹）樹）？性質(zhì)：性質(zhì)： 所有所有結(jié)點(diǎn)左、右子樹深度之差的絕對值結(jié)點(diǎn)左、右子樹深度之差的絕對值 1若定義結(jié)點(diǎn)的若定義結(jié)點(diǎn)的“平衡因子平衡因子” BF = 左子樹深度左子樹深度 右子樹深度右子樹深度則：平衡二叉樹中所有結(jié)點(diǎn)的則：平衡二叉樹中所有結(jié)點(diǎn)的BF -1, 0, 1 (a) (a) 平衡樹

4、平衡樹 (b) (b) 不平衡樹不平衡樹例：判斷下列二叉樹是否例：判斷下列二叉樹是否AVL樹？樹？0001 11 1-1-10001-16什么是二叉排序樹？什么是二叉排序樹？（a）（b）例：例：下列下列2種圖形中，哪個不是二叉排序樹種圖形中，哪個不是二叉排序樹 ？-或是一棵空樹；或者是具有如下性質(zhì)的非空二叉樹：或是一棵空樹；或者是具有如下性質(zhì)的非空二叉樹： （1 1）左子樹的所有結(jié)點(diǎn)均小于根的值；）左子樹的所有結(jié)點(diǎn)均小于根的值； （2 2）右子樹的所有結(jié)點(diǎn)均大于根的值；）右子樹的所有結(jié)點(diǎn)均大于根的值； （3 3）它的左右子樹也分別為二叉排序樹。）它的左右子樹也分別為二叉排序樹。想一想：對它中序

5、遍歷之后是什么效果？想一想：對它中序遍歷之后是什么效果？74110102 26539810216473987什么是判定樹？什么是判定樹？ 舉例：舉例： 1212個球如何用天平只稱個球如何用天平只稱3 3次便分出輕重？次便分出輕重？分析：分析：1212個球中必有一個非輕即重，即共有個球中必有一個非輕即重，即共有2424種種“次品次品”的可能性。的可能性。每次天平稱重的結(jié)果有每次天平稱重的結(jié)果有3 3種，連稱種，連稱3 3次應(yīng)該得到的結(jié)果有次應(yīng)該得到的結(jié)果有3 33 3=27=27種。種。說明僅用說明僅用3 3次就能找出次品的可能性是存在的。次就能找出次品的可能性是存在的。思路：思路：首先，將首先

6、，將1212個球分三組，每組個球分三組，每組4 4個，任意取兩組稱。會有兩種情個，任意取兩組稱。會有兩種情況：平衡，或不平衡。況：平衡，或不平衡。 其次，一定要利用已經(jīng)稱過的那些結(jié)論；即充分利用其次，一定要利用已經(jīng)稱過的那些結(jié)論；即充分利用“舊球舊球”的的標(biāo)準(zhǔn)性作為參考。標(biāo)準(zhǔn)性作為參考。8第第1 1次次: :等分等分3 3組組 第第2 2次次: :3 3舊舊3 3新新第第3 3次次: :1 1舊舊1 1新新 相等相等= =小于小于 (11)(11) 大于大于 相等相等= =小于小于 小于小于 小于小于 相等相等= =(12)(12)小于小于 (12)(12)輕輕大于大于 小于小于 小于小于 小

7、于小于 相等相等= =重重重重重重9什么是帶權(quán)樹？什么是帶權(quán)樹？abdc7524即路徑帶有權(quán)值。例如：即路徑帶有權(quán)值。例如：106.5 Huffman6.5 Huffman樹及其應(yīng)用樹及其應(yīng)用一、一、HuffmanHuffman樹樹二、二、HuffmanHuffman編碼編碼最優(yōu)二叉樹最優(yōu)二叉樹HuffmanHuffman樹樹HuffmanHuffman編碼編碼帶權(quán)路徑帶權(quán)路徑長度最短長度最短的樹的樹不等長編碼不等長編碼是通信是通信中最經(jīng)中最經(jīng)典的壓典的壓縮編碼縮編碼11一、一、 HuffmanHuffman樹樹（最優(yōu)二叉樹）（最優(yōu)二叉樹）路路 徑徑：路徑長度路徑長度：樹的路徑長度樹的路徑長度

8、：帶權(quán)路徑長度帶權(quán)路徑長度：樹的帶權(quán)路徑長度樹的帶權(quán)路徑長度：HuffmanHuffman樹樹：由一結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支所構(gòu)成。由一結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支所構(gòu)成。路徑上的分支數(shù)目。路徑上的分支數(shù)目。從樹根到從樹根到每一結(jié)點(diǎn)每一結(jié)點(diǎn)的路徑長度之和。的路徑長度之和。結(jié)點(diǎn)到根的路徑長度與結(jié)點(diǎn)上權(quán)的乘積（結(jié)點(diǎn)到根的路徑長度與結(jié)點(diǎn)上權(quán)的乘積（WPLWPL）若干術(shù)語：若干術(shù)語：debacf g即樹中所有即樹中所有葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和的帶權(quán)路徑長度之和帶權(quán)路徑長度最小的樹。帶權(quán)路徑長度最小的樹。例如：例如：aeae的路徑長度的路徑長度樹長度樹長度2 21010HuffmanHuffman常譯

9、為常譯為赫夫曼、霍夫曼、哈夫曼等赫夫曼、霍夫曼、哈夫曼等Weighted Path LengthWeighted Path Length12樹的帶權(quán)路徑長度樹的帶權(quán)路徑長度如何計(jì)算？如何計(jì)算？WPLWPL = = w wk kl lk k k=1k=1n nabdc7524(a)cdab2457(b)bdac7524(c)經(jīng)典之例：經(jīng)典之例：WPL=WPL=WPL=Huffman樹是樹是WPL WPL 最小的樹最小的樹樹中所有葉子結(jié)樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長點(diǎn)的帶權(quán)路徑長度之和度之和364635131. 1. 構(gòu)造構(gòu)造HuffmanHuffman樹的基本思想：樹的基本思想：設(shè)有設(shè)有4 4個字

10、符個字符d,i,a,nd,i,a,n，出現(xiàn)的頻度分別為，出現(xiàn)的頻度分別為7,5,2,47,5,2,4， 怎樣編碼才能使它們組成的報(bào)文在網(wǎng)絡(luò)中傳得最快？怎樣編碼才能使它們組成的報(bào)文在網(wǎng)絡(luò)中傳得最快？法法1 1：等長編碼等長編碼（如二進(jìn)制編碼）（如二進(jìn)制編碼）令令d=d=0000，i=i=0101，a=a=1010，n=n=1111，則：，則：WPLWPL1 12bit2bit(7(75 52 24 4）3636法法2 2：不等長編碼不等長編碼（如（如HuffmanHuffman編碼）編碼）令令d=d=0 0;i=;i=1010,a=,a=110110,n=,n=111111，則：，則：明確：要實(shí)

11、現(xiàn)明確：要實(shí)現(xiàn)HuffmanHuffman編碼，就要先構(gòu)造編碼，就要先構(gòu)造HuffmanHuffman樹樹討論：討論：HuffmanHuffman樹有什么用？樹有什么用？權(quán)值大的結(jié)點(diǎn)用短路徑，權(quán)值小的結(jié)點(diǎn)用長路徑。權(quán)值大的結(jié)點(diǎn)用短路徑，權(quán)值小的結(jié)點(diǎn)用長路徑。WPLWPL最小的樹最小的樹頻度高的信息頻度高的信息用短碼，反之用短碼，反之用長碼，傳輸用長碼，傳輸效率肯定高！效率肯定高！WPLWPL2 2= =1bit1bit7 72bit2bit5+5+3bit3bit(2+4)=(2+4)=3535最小冗余編碼、信息高效傳輸最小冗余編碼、信息高效傳輸142. 2. 構(gòu)造構(gòu)造HuffmanHuffm

12、an樹的步驟（即樹的步驟（即HuffmanHuffman算法）：算法）：怎樣證明它就是怎樣證明它就是WPL最小的最優(yōu)二叉樹？最小的最優(yōu)二叉樹？參考參考信源編碼信源編碼Huffman樹的特點(diǎn)：沒有度為樹的特點(diǎn)：沒有度為1的結(jié)點(diǎn)。的結(jié)點(diǎn)。15step1step1：在權(quán)值集合在權(quán)值集合7,5,2,47,5,2,4中，總是合并中，總是合并當(dāng)前值最小當(dāng)前值最小的兩個權(quán)的兩個權(quán)具體操作步驟：具體操作步驟：a. 初始初始方框表示外結(jié)點(diǎn)（葉子，字符）方框表示外結(jié)點(diǎn)（葉子，字符）圓框表示內(nèi)結(jié)點(diǎn)圓框表示內(nèi)結(jié)點(diǎn)（合并后的權(quán)值）（合并后的權(quán)值）b. 合并合并2 4c. 合并合并5 6d. 合并合并7 1116step

13、2step2：d da ai in n1 11 11 10 00 00 0HuffmanHuffman編碼結(jié)果：編碼結(jié)果：d=d=0 0, i=, i=1010, a=, a=110110, n=, n=111111WPL=WPL=1bit1bit7 72bit2bit5+5+3bit3bit(2+4)=(2+4)=3535（小于等長碼的（小于等長碼的WPL=36WPL=36）HuffmanHuffman編碼也稱為編碼也稱為HuffmanHuffman樹樹 與與 HuffmanHuffman編碼編碼 掛鉤掛鉤17二、二、HuffmanHuffman編碼編碼（1 1）由于由于Huffman樹的樹

14、的WPLWPL最小，最小，說明編碼所說明編碼所需要的需要的比特?cái)?shù)最少比特?cái)?shù)最少。（4） Huffman編碼時是從葉子走到根；而譯碼時又要從根走編碼時是從葉子走到根；而譯碼時又要從根走到葉子，因此每個結(jié)點(diǎn)需要增開到葉子，因此每個結(jié)點(diǎn)需要增開雙親雙親指針分量（連同結(jié)點(diǎn)指針分量（連同結(jié)點(diǎn)權(quán)值權(quán)值共要開共要開5個分量）個分量）（5）用計(jì)算機(jī)實(shí)現(xiàn)時，順序和鏈?zhǔn)絻煞N存儲結(jié)構(gòu)都要用到。用計(jì)算機(jī)實(shí)現(xiàn)時，順序和鏈?zhǔn)絻煞N存儲結(jié)構(gòu)都要用到。分析分析Huffman樹和編碼的特點(diǎn)：樹和編碼的特點(diǎn)：霍夫曼霍夫曼編碼的基本思想是編碼的基本思想是出現(xiàn)概率大的信息用短碼，概率小的用長碼出現(xiàn)概率大的信息用短碼，概率小的用長碼,

15、,最小冗余最小冗余這種編碼已廣泛應(yīng)這種編碼已廣泛應(yīng)用于網(wǎng)絡(luò)通信中。用于網(wǎng)絡(luò)通信中。（2） Huffman樹樹肯定沒有度為肯定沒有度為1的結(jié)點(diǎn)；的結(jié)點(diǎn)；（3）一棵有一棵有n 0個葉子結(jié)點(diǎn)的個葉子結(jié)點(diǎn)的Huffman樹，共有樹，共有2n0-1個結(jié)點(diǎn)；個結(jié)點(diǎn)；（因?yàn)椋ㄒ驗(yàn)閚=n0+n1+n2=2n0-1)18如何編程實(shí)現(xiàn)如何編程實(shí)現(xiàn)HuffmanHuffman編碼？編碼？建議建議1 1：HuffmanHuffman樹中結(jié)點(diǎn)的結(jié)構(gòu)可設(shè)計(jì)成樹中結(jié)點(diǎn)的結(jié)構(gòu)可設(shè)計(jì)成5 5分量形式：分量形式：charweightparentlchildrchild將整個將整個HuffmanHuffman樹的樹的結(jié)點(diǎn)結(jié)點(diǎn)存儲在

16、一個數(shù)組存儲在一個數(shù)組HTHT1.n.m1.n.m中中; ; 各葉子結(jié)點(diǎn)的各葉子結(jié)點(diǎn)的編碼編碼存儲在另一存儲在另一“復(fù)合復(fù)合”數(shù)組數(shù)組HCHC1.n1.n中。中。 請參見教材請參見教材P149P149圖圖6.276.27的（的（a)a)和（和（c)c)建議建議2 2： HuffmanHuffman樹的樹的存儲結(jié)構(gòu)可采用存儲結(jié)構(gòu)可采用順序存儲順序存儲結(jié)構(gòu)：結(jié)構(gòu)：(1)(1)教材教材P147P147149149內(nèi)容；內(nèi)容；(2)(2)嚴(yán)蔚敏嚴(yán)蔚敏“數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)”演示程序演示程序；(3)(3)習(xí)題集習(xí)題集P149 P149 實(shí)習(xí)實(shí)習(xí)5.25.2要求；要求；(4)(4)自測卷第自測卷第6 6章上機(jī)

17、方案二的源程序。章上機(jī)方案二的源程序。19typedef structunsigned int weight；/權(quán)值分量（可放大取整）權(quán)值分量（可放大取整）unsigned int parent，lchild，rchild； /雙親和孩子分量雙親和孩子分量HTNode，*HuffmanTree；/用動態(tài)數(shù)組存儲用動態(tài)數(shù)組存儲Huffman樹樹typedef char*HuffmanCode； /動態(tài)數(shù)組存儲動態(tài)數(shù)組存儲Huffman編碼表編碼表Huffman樹和樹和Huffman樹編碼的存儲表示：樹編碼的存儲表示：000r0920019007lpw321雙親雙親* *HuffmanTreeHu

18、ffmanTree或或 HTHT向量向量HT3.parent=9HT3.parent=9指針型指針指針型指針20如何編程實(shí)現(xiàn)如何編程實(shí)現(xiàn)HuffmanHuffman編碼？編碼？參見教材參見教材P147先構(gòu)造先構(gòu)造Huffman樹樹HT， 再求出再求出N個字符的個字符的Huffman編碼編碼HC。Void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)if (n=1)return;m=2*n-1; /n 0個葉子的個葉子的HuffmanTree共有共有2n0-1個結(jié)點(diǎn)；個結(jié)點(diǎn)；HT=(HuffmanTr

19、ee)malloc(m+1)*sizeof(HTNode); /0單元未用單元未用*w存放存放n個字符的權(quán)值個字符的權(quán)值for(p=HT,i=1; i=n; +i,+p,+w)*p=*w,0,0,0; /給前給前n0個單元個單元初始化初始化for(；i=m; +i,+p)*p =0,0,0,0; /對葉子之后的存儲單元清零對葉子之后的存儲單元清零for(i=n+1;i=m; +i) /建建Huffman樹樹(從從葉子后開始存內(nèi)結(jié)點(diǎn)葉子后開始存內(nèi)結(jié)點(diǎn)) Select(HT, i-1, s1, s2); /在在HT1i-1選擇選擇parent為為0且且weight最小最小的的兩個結(jié)點(diǎn)，其序號分別為

20、兩個結(jié)點(diǎn)，其序號分別為S1和和s2（教材未給出此函數(shù)源碼）教材未給出此函數(shù)源碼）HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+ HTs2.weight;21(續(xù)前續(xù)前)再求出再求出n個字符的個字符的Huffman編碼編碼HCHC=(HuffmanCode)malloc(n+1)*sizeof(char*); /分配分配n個字符個字符編碼的頭指針向量（一維數(shù)組）編碼的頭指針向量（一維數(shù)組）cd=(char*) malloc(n*sizeof(char); /分配求編碼的工作空間

21、分配求編碼的工作空間(n) cdn-1=“0”; /編碼結(jié)束符（從編碼結(jié)束符（從cd0cdn-1為合法空間）為合法空間）for(i=1;i=n;+i) /逐個字符求逐個字符求Huffman編碼編碼 start=n-1; /編碼結(jié)束符位置編碼結(jié)束符位置 for(c=i,f=HTi.parent; f!=0; c=f, f=HTf.parent)/從葉子到從葉子到根逆向求編碼根逆向求編碼if(HTf.lchild=c) cd-start=“0”;else cd-start=“1”;HCi=(char*)malloc(n-start)*sizeof(char);/為第為第i個字個字符編碼分配空間符編

22、碼分配空間strcpy(HCi,&cdstart); /從從cd復(fù)制編碼串到復(fù)制編碼串到HCfree(cd); /釋放工作空間釋放工作空間/HuffmanCoding22HuffmanHuffman編碼舉例編碼舉例解：解：先將概率先將概率放大放大100100倍倍，以方便構(gòu)造哈夫曼樹。，以方便構(gòu)造哈夫曼樹。放大后的權(quán)值集合放大后的權(quán)值集合 w= 7, 19, 2, 6, 32, 3, 21, 10 w= 7, 19, 2, 6, 32, 3, 21, 10 ，按哈夫曼樹構(gòu)造規(guī)則按哈夫曼樹構(gòu)造規(guī)則（合并、刪除、替換）（合并、刪除、替換），可得到哈夫曼樹。，可得到哈夫曼樹。例例1【嚴(yán)題集【嚴(yán)

23、題集6.26】：假設(shè)用于通信的電文僅由：假設(shè)用于通信的電文僅由8個字母個字母 a, b, c, d, e, f, g, h 構(gòu)成，它們在電文中出現(xiàn)的概率分別為構(gòu)成，它們在電文中出現(xiàn)的概率分別為 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 ，試為這，試為這8個字母設(shè)計(jì)哈夫曼個字母設(shè)計(jì)哈夫曼編編碼。如果用碼。如果用07的二進(jìn)制編碼方案又如何？的二進(jìn)制編碼方案又如何？ 【類同【類同P148例例2】2310107 71717000000000000000-00000000r0010002100300320060020019007lpw131210119

24、8765432111116 6w= 7, 19, 2, 6, 32, 3, 21, 10 w= 7, 19, 2, 6, 32, 3, 21, 10 在機(jī)內(nèi)存儲形式為在機(jī)內(nèi)存儲形式為: :2 23 35 5282821211919404032326060100100b bc ca ad de eg gf fh h請注意：哈夫曼請注意：哈夫曼樹樣式不惟一！樹樣式不惟一！5991110104917284060100雙親雙親左右孩子左右孩子362410107 7171711116 62 23 35 5282821211919404032326060100100b bc ca ad de eg gf

25、fh h對應(yīng)的哈夫曼編碼：對應(yīng)的哈夫曼編碼：符符編碼編碼頻率頻率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10符符編碼編碼頻率頻率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.100000010100111001011101110 00 00 00 00 00 00 01 11 11 11 11 11 11 1Huffman碼的碼的WPL2(0.19+0.32+0.21) + 4(0.07+0.06+0.10) +5(0.02+0.03) =1.44+0.92+0.25=2.61 3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 二進(jìn)制等長碼的二進(jìn)制等長碼的WPL按左按左0右右1標(biāo)注標(biāo)注25另另一一種種表表示示：26