樹和二叉樹哈夫曼樹及其應(yīng)用樹和二叉樹哈夫曼樹及其應(yīng)用11.相關(guān)概念路徑：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)所經(jīng)過的分支序列或者說結(jié)點(diǎn)序列。如結(jié)點(diǎn)A到結(jié)點(diǎn)F的路徑為：A-B-E-FABCDEFG1.相關(guān)概念A(yù)BCDEFG2路徑長度：路徑上面的分支個(gè)數(shù)。如A-F的路徑長度為3。ABCDEFGABCDEFG3樹的路徑長度：從樹根到每一個(gè)結(jié)點(diǎn)的路徑長度之和。如左邊樹的路徑長度為：Len(A-B)+Len(A-C)+Len(A-D)+Len(A-E)+Len(A-F)+Len(A-G) =1+1+2+2+3+3=12ABCDEFG樹的路徑長度：從樹根到每一個(gè)結(jié)點(diǎn)的路徑長度之和。ABCDEF4結(jié)點(diǎn)的權(quán)值：在某些應(yīng)用中，樹中結(jié)點(diǎn)往往要和一定的數(shù)值聯(lián)系起來，那么這個(gè)數(shù)值通常稱為該結(jié)點(diǎn)的權(quán)值，簡稱權(quán)。如左圖。ABCDEFG412537結(jié)點(diǎn)的權(quán)值：在某些應(yīng)用中，樹中結(jié)點(diǎn)往往要和一定的數(shù)值聯(lián)系起來5結(jié)點(diǎn)的帶權(quán)路徑長度：該結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長度與該結(jié)點(diǎn)上權(quán)的乘積。如結(jié)點(diǎn)E的帶權(quán)路徑長度為:Len(E-A)*3=2*3=6ABCDEFG412537結(jié)點(diǎn)的帶權(quán)路徑長度：該結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長度與該結(jié)點(diǎn)上權(quán)的乘6樹的帶權(quán)路徑長度： 樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和。記作：WPL=w1*L1+w2*L2+……+wn*LnABCDEFGw1w2w3w4樹的帶權(quán)路徑長度：ABCDEFGw1w2w3w47從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。這種編碼方式也可以對應(yīng)到二叉樹，如右圖所式這樣,這些編碼恢復(fù)成二叉樹的形式時(shí),不會形成A,B,C,D恰好為二叉樹的葉子結(jié)點(diǎn),如右圖當(dāng)A、B、C、D按照如下形式進(jìn)行編碼時(shí)。從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。當(dāng)A、B、C、D按照如下形式進(jìn)行編碼時(shí)。從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。其中A、B、C、D出現(xiàn)的次數(shù)分別為3、1、2、1。重復(fù)②和③，直到F只含一棵樹為止。下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右分支上面標(biāo)0。采取這種變長編碼方式，需要遵循一個(gè)原則，即每一個(gè)字符的編碼都不應(yīng)該是另一個(gè)字符編碼的前綴。15的雙親結(jié)點(diǎn)為0，所以可以判斷15就是根結(jié)點(diǎn)，那么第一個(gè)結(jié)點(diǎn)編碼完畢，編碼應(yīng)該從棧頂向棧底讀，為“0110”。這樣,這些編碼恢復(fù)成二叉樹的形式時(shí),不會形成A,B,C,D恰好為二叉樹的葉子結(jié)點(diǎn),如右圖以第一個(gè)葉子結(jié)點(diǎn)為例：從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。這樣,這些編碼恢復(fù)成二叉樹的形式時(shí),不會形成A,B,C,D恰好為二叉樹的葉子結(jié)點(diǎn),如右圖這八個(gè)權(quán)值作為葉子結(jié)點(diǎn)，最終形成的哈夫曼樹應(yīng)共有2*8-1=15個(gè)結(jié)點(diǎn)。9的雙親結(jié)點(diǎn)為11，且9是11的右孩子，故分支應(yīng)該標(biāo)“1”，所以編碼“1”入棧。從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。最優(yōu)二叉樹（哈夫曼樹）：給定n個(gè)權(quán)值{w1,w2,…,wn}，試構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子結(jié)點(diǎn)帶權(quán)為wi。構(gòu)造出來的二叉樹的形態(tài)可以有多個(gè)，我們把其中帶權(quán)路徑長度WPL最小的二叉樹稱作最優(yōu)二叉樹或者哈夫曼樹。ABCDEFGw1w2w3w4從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子82.哈夫曼算法（1）如何構(gòu)造一棵哈夫曼樹。我們首先通過一個(gè)例子來演示一下構(gòu)造過程。2.哈夫曼算法（1）如何構(gòu)造一棵哈夫曼樹。9當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。7524當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。752410從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。從葉子結(jié)點(diǎn)開始，向根回溯，來對葉子結(jié)點(diǎn)所代表的字符進(jìn)行編碼。（2）哈夫曼算法的語言描述如左邊樹的路徑長度為：這樣,這些編碼恢復(fù)成二叉樹的形式時(shí),不會形成A,B,C,D恰好為二叉樹的葉子結(jié)點(diǎn),如右圖11的雙親結(jié)點(diǎn)為13，且11是13的右孩子，故分支應(yīng)該標(biāo)“1”，所以編碼“1”入棧。以第一個(gè)葉子結(jié)點(diǎn)為例：13的雙親結(jié)點(diǎn)為15，且13是15的左孩子，故分支應(yīng)該標(biāo)“0”，所以編碼“0”入棧。也可以看出，每一個(gè)可用的編碼都可以轉(zhuǎn)化成二叉樹的形式，這樣編碼理論便可以與二叉樹的一些性質(zhì)結(jié)合起來，就可以應(yīng)用二叉樹的理論知識來解決編碼問題。這種編碼方式也可以對應(yīng)到二叉樹，如右圖所式以第一個(gè)葉子結(jié)點(diǎn)為例：下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右分支上面標(biāo)0。以第一個(gè)葉子結(jié)點(diǎn)為例：當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右分支上面標(biāo)0。對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。根據(jù)權(quán)值{3，1，2，1}構(gòu)造哈夫曼樹路徑長度：路徑上面的分支個(gè)數(shù)。從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。這樣,這些編碼恢復(fù)成二叉樹的形式時(shí),不會形成A,B,C,D恰好為二叉樹的葉子結(jié)點(diǎn),如右圖當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。75246從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子11當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。72465當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。7246512當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。7246511當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。724651113當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。7246511當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。724651114當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。724651118當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。7246511115（2）哈夫曼算法的語言描述根據(jù)給定的n個(gè)權(quán)值{w1,w2,…,wn}構(gòu)成n棵二叉樹的集合F={T1,T2,…,Tn},其中每棵二叉樹Ti中只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹為空。在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹上根結(jié)點(diǎn)的權(quán)值之和。在F中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入F中。重復(fù)②和③，直到F只含一棵樹為止。這棵樹便是哈夫曼樹。（2）哈夫曼算法的語言描述根據(jù)給定的n個(gè)權(quán)值{w1,w2,…16對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。其中A、B、C、D出現(xiàn)的次數(shù)分別為3、1、2、1。 現(xiàn)在要對字符串進(jìn)行0、1編碼，有哪些方法？哪一種編碼的長度最短？對于字符串“ABACCDA”，共有7個(gè)字171.各種編碼方式（1）定長編碼---根據(jù)出現(xiàn)的字符種數(shù)進(jìn)行編碼 字符串“ABACCDA”中共出現(xiàn)4種字符，那么可以用2位表示。ABCD000110111.各種編碼方式（1）定長編碼---根據(jù)出現(xiàn)的字符種數(shù)進(jìn)行編181.各種編碼方式（1）定長編碼---根據(jù)出現(xiàn)的字符種數(shù)進(jìn)行編碼 這種編碼方式可以對應(yīng)到二叉樹，如右圖所式ABCD00011011ABCD0001111.各種編碼方式（1）定長編碼---根據(jù)出現(xiàn)的字符種數(shù)進(jìn)行編191.各種編碼方式（2）變長編碼 當(dāng)A、B、C、D按照如下形式進(jìn)行編碼時(shí)。ABCD011010111采取這種變長編碼方式，需要遵循一個(gè)原則，即每一個(gè)字符的編碼都不應(yīng)該是另一個(gè)字符編碼的前綴。否則就會出現(xiàn)二義性。1.各種編碼方式（2）變長編碼ABCD011010111201.各種編碼方式（2）變長編碼這種編碼方式也可以對應(yīng)到二叉樹，如右圖所式 ABCD011010111ABC0011D011.各種編碼方式（2）變長編碼ABCD011010111AB21N個(gè)權(quán)值構(gòu)造的哈夫曼樹，樹中結(jié)點(diǎn)總數(shù)是多少？下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右分支上面標(biāo)0。重復(fù)②和③，直到F只含一棵樹為止。從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。這樣,這些編碼恢復(fù)成二叉樹的形式時(shí),不會形成A,B,C,D恰好為二叉樹的葉子結(jié)點(diǎn),如右圖如結(jié)點(diǎn)E的帶權(quán)路徑長度為:Len(E-A)*3=2*3=6以第一個(gè)葉子結(jié)點(diǎn)為例：WPL=w1*L1+w2*L2+w3*L3+w4*L4當(dāng)A、B、C、D按照如下形式進(jìn)行編碼時(shí)。以第一個(gè)葉子結(jié)點(diǎn)為例：哈夫曼樹中，權(quán)值越大的結(jié)點(diǎn)越靠近根結(jié)點(diǎn)。Len(A-B)+Len(A-C)+Len(A-D)+Len(A-E)+Len(A-F)+Len(A-G)如結(jié)點(diǎn)E的帶權(quán)路徑長度為:Len(E-A)*3=2*3=6可以看出，該公式與哈夫曼樹滿足的公式一模一樣，那么我們可以采取構(gòu)造哈夫曼樹的方式來求編碼的長度。下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右分支上面標(biāo)0。這樣,這些編碼恢復(fù)成二叉樹的形式時(shí),不會形成A,B,C,D恰好為二叉樹的葉子結(jié)點(diǎn),如右圖采取這種變長編碼方式，需要遵循一個(gè)原則，即每一個(gè)字符的編碼都不應(yīng)該是另一個(gè)字符編碼的前綴。其中A、B、C、D出現(xiàn)的次數(shù)分別為3、1、2、1。那么總的編碼長度為：從上面的分析可以看出，一個(gè)可用的編碼必須滿足每個(gè)字符的編碼不能是其他編碼的前綴。這八個(gè)權(quán)值作為葉子結(jié)點(diǎn)，最終形成的哈夫曼樹應(yīng)共有2*8-1=15個(gè)結(jié)點(diǎn)。其中A、B、C、D出現(xiàn)的次數(shù)分別為3、1、2、1。1.各種編碼方式（2）變長編碼 如當(dāng)A、B、C、D按照如下形式進(jìn)行編碼時(shí)。ABCD01101111請將“0111”翻譯成字符串。試一試，有哪些翻譯方式。之所以會出現(xiàn)二義性，是因?yàn)槌霈F(xiàn)了A的編碼是C的編碼的前綴；B的編碼是D的編碼的前綴.N個(gè)權(quán)值構(gòu)造的哈夫曼樹，樹中結(jié)點(diǎn)總數(shù)是多少？1.各種編碼方式221.各種編碼方式（2）變長編碼這樣,這些編碼恢復(fù)成二叉樹的形式時(shí),不會形成A,B,C,D恰好為二叉樹的葉子結(jié)點(diǎn),如右圖

ABCD01101111ACB0111D11.各種編碼方式（2）變長編碼ABCD01101111ACB231.各種編碼方式從上面的分析可以看出，一個(gè)可用的編碼必須滿足每個(gè)字符的編碼不能是其他編碼的前綴。也可以看出，每一個(gè)可用的編碼都可以轉(zhuǎn)化成二叉樹的形式，這樣編碼理論便可以與二叉樹的一些性質(zhì)結(jié)合起來，就可以應(yīng)用二叉樹的理論知識來解決編碼問題。1.各種編碼方式從上面的分析可以看出，一個(gè)可用的編碼必須滿足241.各種編碼方式（3）哈夫曼編碼 假設(shè)編碼過程中有以下對應(yīng)關(guān)系：字符ABCD權(quán)重（字符出現(xiàn)次數(shù)）w1w2w3w4編碼長度L1L2L3L4那么總的編碼長度為：WPL=w1*L1+w2*L2+w3*L3+w4*L4那么如何選擇L1、L2、L3、L4的值，使得WPL最小呢？1.各種編碼方式（3）哈夫曼編碼字符ABCD權(quán)重（字符出現(xiàn)次251.各種編碼方式（3）哈夫曼編碼 可以看出，該公式與哈夫曼樹滿足的公式一模一樣，那么我們可以采取構(gòu)造哈夫曼樹的方式來求編碼的長度。1.各種編碼方式（3）哈夫曼編碼 可以看出，該公式與哈26對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。其中A、B、C、D出現(xiàn)的次數(shù)分別為3、1、2、1。根據(jù)權(quán)值{3，1，2，1}構(gòu)造哈夫曼樹1231ABCD對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。其中27對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。其中A、B、C、D出現(xiàn)的次數(shù)分別為3、1、2、1。根據(jù)權(quán)值{3，1，2，1}構(gòu)造哈夫曼樹3211BDCA對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。其中28對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。其中A、B、C、D出現(xiàn)的次數(shù)分別為3、1、2、1。根據(jù)權(quán)值{3，1，2，1}構(gòu)造哈夫曼樹3211BDCA2對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。其中29對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。其中A、B、C、D出現(xiàn)的次數(shù)分別為3、1、2、1。根據(jù)權(quán)值{3，1，2，1}構(gòu)造哈夫曼樹3211BDCA2對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。其中30對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。其中A、B、C、D出現(xiàn)的次數(shù)分別為3、1、2、1。根據(jù)權(quán)值{3，1，2，1}構(gòu)造哈夫曼樹3211BDCA24對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。其中31對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。其中A、B、C、D出現(xiàn)的次數(shù)分別為3、1、2、1。根據(jù)權(quán)值{3，1，2，1}構(gòu)造哈夫曼樹3211BDCA24對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。其中32對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。其中A、B、C、D出現(xiàn)的次數(shù)分別為3、1、2、1。根據(jù)權(quán)值{3，1，2，1}構(gòu)造哈夫曼樹3211BDCA247對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。其中33根據(jù)給定的n個(gè)權(quán)值{w1,w2,…,wn}構(gòu)成n棵二叉樹的集合F={T1,T2,…,Tn},其中每棵二叉樹Ti中只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹為空。以第一個(gè)葉子結(jié)點(diǎn)為例：如結(jié)點(diǎn)A到結(jié)點(diǎn)F的路徑為：從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。重復(fù)②和③，直到F只含一棵樹為止。以第一個(gè)葉子結(jié)點(diǎn)為例：11的雙親結(jié)點(diǎn)為13，且11是13的右孩子，故分支應(yīng)該標(biāo)“1”，所以編碼“1”入棧。15的雙親結(jié)點(diǎn)為0，所以可以判斷15就是根結(jié)點(diǎn)，那么第一個(gè)結(jié)點(diǎn)編碼完畢，編碼應(yīng)該從棧頂向棧底讀，為“0110”。從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。這種編碼方式也可以對應(yīng)到二叉樹，如右圖所式下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)0，右分支上面標(biāo)1。根據(jù)權(quán)值{3，1，2，1}構(gòu)造哈夫曼樹當(dāng)A、B、C、D按照如下形式進(jìn)行編碼時(shí)。從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。13的雙親結(jié)點(diǎn)為15，且13是15的左孩子，故分支應(yīng)該標(biāo)“0”，所以編碼“0”入棧。可以看出，該公式與哈夫曼樹滿足的公式一模一樣，那么我們可以采取構(gòu)造哈夫曼樹的方式來求編碼的長度。WPL=w1*L1+w2*L2+w3*L3+w4*L4這八個(gè)權(quán)值作為葉子結(jié)點(diǎn)，最終形成的哈夫曼樹應(yīng)共有2*8-1=15個(gè)結(jié)點(diǎn)。當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。可以看出，該公式與哈夫曼樹滿足的公式一模一樣，那么我們可以采取構(gòu)造哈夫曼樹的方式來求編碼的長度。當(dāng)A、B、C、D按照如下形式進(jìn)行編碼時(shí)。下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)0，右分支上面標(biāo)1。3211BDCA247根據(jù)給定的n個(gè)權(quán)值{w1,w2,…,wn}構(gòu)成n棵二叉樹的集34下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右分支上面標(biāo)0。3211BDCA2470下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右35下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右分支上面標(biāo)0。3211BDCA24701下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右36下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右分支上面標(biāo)0。3211BDCA247010下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右37下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右分支上面標(biāo)0。3211BDCA2470101下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右38下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右分支上面標(biāo)0。3211BDCA24701010下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右39下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右分支上面標(biāo)0。3211BDCA247101010下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右4011的雙親結(jié)點(diǎn)為13，且11是13的右孩子，故分支應(yīng)該標(biāo)“1”，所以編碼“1”入棧。9的雙親結(jié)點(diǎn)為11，且9是11的右孩子，故分支應(yīng)該標(biāo)“1”，所以編碼“1”入棧。最優(yōu)二叉樹（哈夫曼樹）：給定n個(gè)權(quán)值{w1,w2,…,wn}，試構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子結(jié)點(diǎn)帶權(quán)為wi。從上面的分析可以看出，一個(gè)可用的編碼必須滿足每個(gè)字符的編碼不能是其他編碼的前綴。對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。可以看出，該公式與哈夫曼樹滿足的公式一模一樣，那么我們可以采取構(gòu)造哈夫曼樹的方式來求編碼的長度。這樣,這些編碼恢復(fù)成二叉樹的形式時(shí),不會形成A,B,C,D恰好為二叉樹的葉子結(jié)點(diǎn),如右圖當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。這種編碼方式也可以對應(yīng)到二叉樹，如右圖所式當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。采取這種變長編碼方式，需要遵循一個(gè)原則，即每一個(gè)字符的編碼都不應(yīng)該是另一個(gè)字符編碼的前綴。這八個(gè)權(quán)值作為葉子結(jié)點(diǎn)，最終形成的哈夫曼樹應(yīng)共有2*8-1=15個(gè)結(jié)點(diǎn)。以第一個(gè)葉子結(jié)點(diǎn)為例：從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。（1）如何構(gòu)造一棵哈夫曼樹。對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。根據(jù)權(quán)值{3，1，2，1}構(gòu)造哈夫曼樹這樣,這些編碼恢復(fù)成二叉樹的形式時(shí),不會形成A,B,C,D恰好為二叉樹的葉子結(jié)點(diǎn),如右圖其中A、B、C、D出現(xiàn)的次數(shù)分別為3、1、2、1。從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。3211BDCA24710101011的雙親結(jié)點(diǎn)為13，且11是13的右孩子，故分支應(yīng)該標(biāo)“141從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。3211BDCA247101010A：0從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序42從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。3211BDCA247101010A：0B：1從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序43從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。A：0B：113211BDCA247101010從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序44從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。A：0B：1103211BDCA247101010從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序45從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。A：0B：110C：13211BDCA247101010從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序46從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。A：0B：110C：103211BDCA247101010從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序47從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。A：0B：110C：10D：13211BDCA247101010從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序48從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。A：0B：110C：10D：113211BDCA247101010從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序49從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。A：1B：110C：10D：1113211BDCA247101010從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序50思考N個(gè)權(quán)值構(gòu)造的哈夫曼樹，樹中結(jié)點(diǎn)總數(shù)是多少？哈夫曼樹中，權(quán)值越大的結(jié)點(diǎn)越靠近根結(jié)點(diǎn)。該論斷是否正確？思考N個(gè)權(quán)值構(gòu)造的哈夫曼樹，樹中結(jié)點(diǎn)總數(shù)是多少？512.哈夫曼編碼的具體實(shí)現(xiàn)輸入字符及其權(quán)重根據(jù)權(quán)重構(gòu)造哈夫曼樹根據(jù)哈夫曼樹編碼2.哈夫曼編碼的具體實(shí)現(xiàn)輸入字符及其權(quán)重52下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右分支上面標(biāo)0。從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。根據(jù)給定的n個(gè)權(quán)值{w1,w2,…,wn}構(gòu)成n棵二叉樹的集合F={T1,T2,…,Tn},其中每棵二叉樹Ti中只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹為空。路徑：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)所經(jīng)過的分支序列或者說結(jié)點(diǎn)序列。可以看出，該公式與哈夫曼樹滿足的公式一模一樣，那么我們可以采取構(gòu)造哈夫曼樹的方式來求編碼的長度。路徑長度：路徑上面的分支個(gè)數(shù)。下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右分支上面標(biāo)0。我們首先通過一個(gè)例子來演示一下構(gòu)造過程。如結(jié)點(diǎn)A到結(jié)點(diǎn)F的路徑為：以第一個(gè)葉子結(jié)點(diǎn)為例：Len(A-B)+Len(A-C)+Len(A-D)+Len(A-E)+Len(A-F)+Len(A-G)根據(jù)權(quán)值{3，1，2，1}構(gòu)造哈夫曼樹最優(yōu)二叉樹（哈夫曼樹）：給定n個(gè)權(quán)值{w1,w2,…,wn}，試構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子結(jié)點(diǎn)帶權(quán)為wi。對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。當(dāng)A、B、C、D按照如下形式進(jìn)行編碼時(shí)。以第一個(gè)葉子結(jié)點(diǎn)為例：如當(dāng)A、B、C、D按照如下形式進(jìn)行編碼時(shí)。從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。以第一個(gè)葉子結(jié)點(diǎn)為例：15的雙親結(jié)點(diǎn)為0，所以可以判斷15就是根結(jié)點(diǎn)，那么第一個(gè)結(jié)點(diǎn)編碼完畢，編碼應(yīng)該從棧頂向棧底讀，為“0110”。下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右分支上面標(biāo)0。算法6.12的動(dòng)態(tài)演示（1）存儲結(jié)構(gòu)的選擇權(quán)值分別如下：ABCDEFGH529781423311這八個(gè)權(quán)值作為葉子結(jié)點(diǎn)，最終形成的哈夫曼樹應(yīng)共有2*8-1=15個(gè)結(jié)點(diǎn)。采用雙親孩子表示法來存儲哈夫曼樹。下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右分支上53（2）初始化（2）初始化54weightparentlchildrchild150002290003700048000514000623000730008110009-00010-00011-00012-00013-00014-00015-000weightparentlchildrchild15000255(3)建樹過程(3)建樹過程56weightparentlchildrchild150002290003700048000514000623000730008110009-00010-00011-00012-00013-00014-00015-000第一步weightparentlchildrchild15000257weightparentlchildrchild159002290003700048000514000623000730008110009-00010-00011-00012-00013-00014-00015-000weightparentlchildrchild15900258weightparentlchildrchild159002290003700048000514000623000739008110009-00010-00011-00012-00013-00014-00015-000weightparentlchildrchild15900259weightparentlchildrchild159002290003700048000514000623000739008110009800010-00011-00012-00013-00014-00015-000weightparentlchildrchild15900260weightparentlchildrchild159002290003700048000514000623000739008110009801010-00011-00012-00013-00014-00015-000weightparentlchildrchild1590026115的雙親結(jié)點(diǎn)為0，所以可以判斷15就是根結(jié)點(diǎn)，那么第一個(gè)結(jié)點(diǎn)編碼完畢，編碼應(yīng)該從棧頂向棧底讀，為“0110”。以第一個(gè)葉子結(jié)點(diǎn)為例：對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)0，右分支上面標(biāo)1。當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右分支上面標(biāo)0。下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右分支上面標(biāo)0。從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。以第一個(gè)葉子結(jié)點(diǎn)為例：其中A、B、C、D出現(xiàn)的次數(shù)分別為3、1、2、1。對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。其中A、B、C、D出現(xiàn)的次數(shù)分別為3、1、2、1。以第一個(gè)葉子結(jié)點(diǎn)為例：這樣,這些編碼恢復(fù)成二叉樹的形式時(shí),不會形成A,B,C,D恰好為二叉樹的葉子結(jié)點(diǎn),如右圖對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右分支上面標(biāo)0。如結(jié)點(diǎn)E的帶權(quán)路徑長度為:Len(E-A)*3=2*3=6以第一個(gè)葉子結(jié)點(diǎn)為例：以第一個(gè)葉子結(jié)點(diǎn)為例：從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。其中A、B、C、D出現(xiàn)的次數(shù)分別為3、1、2、1。以第一個(gè)葉子結(jié)點(diǎn)為例：weightparentlchildrchild159002290003700048000514000623000739008110009801710-00011-00012-00013-00014-00015-00015的雙親結(jié)點(diǎn)為0，所以可以判斷15就是根結(jié)點(diǎn)，那么第一個(gè)結(jié)62weightparentlchildrchild159002290003700048000514000623000739008110009801710-00011-00012-00013-00014-00015-000第二步weightparentlchildrchild15900263weightparentlchildrchild1590022900037100048000514000623000739008110009801710-00011-00012-00013-00014-00015-000weightparentlchildrchild15900264weightparentlchildrchild15900229000371000481000514000623000739008110009801710-00011-00012-00013-00014-00015-000weightparentlchildrchild15900265weightparentlchildrchild159002290003710004810005140006230007390081100098017101500011-00012-00013-00014-00015-000weightparentlchildrchild15900266weightparentlchildrchild159002290003710004810005140006230007390081100098017101503011-00012-00013-00014-00015-000weightparentlchildrchild15900267weightparentlchildrchild159002290003710004810005140006230007390081100098017101503411-00012-00013-00014-00015-000weightparentlchildrchild15900268weightparentlchildrchild159002290003710004810005140006230007390081100098017101503411-00012-00013-00014-00015-000第三步weightparentlchildrchild15900269weightparentlchildrchild1590022900037100048100051400062300073900811110098017101503411-00012-00013-00014-00015-000weightparentlchildrchild15900270weightparentlchildrchild15900229000371000481000514000623000739008111100981117101503411-00012-00013-00014-00015-000weightparentlchildrchild15900271其中A、B、C、D出現(xiàn)的次數(shù)分別為3、1、2、1。從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。這樣,這些編碼恢復(fù)成二叉樹的形式時(shí),不會形成A,B,C,D恰好為二叉樹的葉子結(jié)點(diǎn),如右圖那么如何選擇L1、L2、L3、L4的值，使得WPL最小呢？如結(jié)點(diǎn)A到結(jié)點(diǎn)F的路徑為：從葉子結(jié)點(diǎn)開始，向根回溯，來對葉子結(jié)點(diǎn)所代表的字符進(jìn)行編碼。我們首先通過一個(gè)例子來演示一下構(gòu)造過程。之所以會出現(xiàn)二義性，是因?yàn)槌霈F(xiàn)了A的編碼是C的編碼的前綴；其中A、B、C、D出現(xiàn)的次數(shù)分別為3、1、2、1。下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右分支上面標(biāo)0。這樣,這些編碼恢復(fù)成二叉樹的形式時(shí),不會形成A,B,C,D恰好為二叉樹的葉子結(jié)點(diǎn),如右圖其中A、B、C、D出現(xiàn)的次數(shù)分別為3、1、2、1。根據(jù)權(quán)值{3，1，2，1}構(gòu)造哈夫曼樹對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。這樣,這些編碼恢復(fù)成二叉樹的形式時(shí),不會形成A,B,C,D恰好為二叉樹的葉子結(jié)點(diǎn),如右圖下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右分支上面標(biāo)0。以第一個(gè)葉子結(jié)點(diǎn)為例：當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。從上面的分析可以看出，一個(gè)可用的編碼必須滿足每個(gè)字符的編碼不能是其他編碼的前綴。對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。weightparentlchildrchild159002290003710004810005140006230007390081111009811171015034111900012-00013-00014-00015-000其中A、B、C、D出現(xiàn)的次數(shù)分別為3、1、2、1。weigh72weightparentlchildrchild159002290003710004810005140006230007390081111009811171015034111908012-00013-00014-00015-000weightparentlchildrchild15900273weightparentlchildrchild159002290003710004810005140006230007390081111009811171015034111908912-00013-00014-00015-000weightparentlchildrchild15900274weightparentlchildrchild159002290003710004810005140006230007390081111009811171015034111908912-00013-00014-00015-000第四步weightparentlchildrchild15900275weightparentlchildrchild1590022900037100048100051412006230007390081111009811171015034111908912-00013-00014-00015-000weightparentlchildrchild15900276weightparentlchildrchild15900229000371000481000514120062300073900811110098111710151234111908912-00013-00014-00015-000weightparentlchildrchild15900277weightparentlchildrchild159002290003710004810005141200623000739008111100981117101512341119089122900013-00014-00015-000weightparentlchildrchild15900278weightparentlchildrchild159002290003710004810005141200623000739008111100981117101512341119089122905013-00014-00015-000weightparentlchildrchild15900279weightparentlchildrchild1590022900037100048100051412006230007390081111009811171015123411190891229051013-00014-00015-000weightparentlchildrchild15900280weightparentlchildrchild1590022900037100048100051412006230007390081111009811171015123411190891229051013-00014-00015-000第五步weightparentlchildrchild15900281weightparentlchildrchild15900229000371000481000514120062313007390081111009811171015123411190891229051013-00014-00015-000weightparentlchildrchild15900282weightparentlchildrchild159002290003710004810005141200623130073900811110098111710151234111913891229051013-00014-00015-000weightparentlchildrchild15900283對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。這種編碼方式也可以對應(yīng)到二叉樹，如右圖所式其中A、B、C、D出現(xiàn)的次數(shù)分別為3、1、2、1。從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。根據(jù)權(quán)值{3，1，2，1}構(gòu)造哈夫曼樹當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。請將“0111”翻譯成字符串。如結(jié)點(diǎn)E的帶權(quán)路徑長度為:Len(E-A)*3=2*3=6采取這種變長編碼方式，需要遵循一個(gè)原則，即每一個(gè)字符的編碼都不應(yīng)該是另一個(gè)字符編碼的前綴。從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右分支上面標(biāo)0。其中A、B、C、D出現(xiàn)的次數(shù)分別為3、1、2、1。對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右分支上面標(biāo)0。其中A、B、C、D出現(xiàn)的次數(shù)分別為3、1、2、1。對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。其中A、B、C、D出現(xiàn)的次數(shù)分別為3、1、2、1。WPL=w1*L1+w2*L2+……+wn*Ln這種編碼方式也可以對應(yīng)到二叉樹，如右圖所式重復(fù)②和③，直到F只含一棵樹為止。weightparentlchildrchild1590022900037100048100051412006231300739008111100981117101512341119138912290510134200014-00015-000對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。wei84weightparentlchildrchild1590022900037100048100051412006231300739008111100981117101512341119138912290510134206014-00015-000weightparentlchildrchild15900285weightparentlchildrchild15900229000371000481000514120062313007390081111009811171015123411191389122905101342061114-00015-000weightparentlchildrchild15900286weightparentlchildrchild15900229000371000481000514120062313007390081111009811171015123411191389122905101342061114-00015-000第六步weightparentlchildrchild15900287weightparentlchildrchild159002291400371000481000514120062313007390081111009811171015123411191389122905101342061114-00015-000weightparentlchildrchild15900288weightparentlchildrchild1590022914003710004810005141200623130073900811110098111710151234111913891229145101342061114-00015-000weightparentlchildrchild15900289weightparentlchildrchild15900229140037100048100051412006231300739008111100981117101512341119138912291451013420611145800015-000weightparentlchildrchild15900290weightparentlchildrchild15900229140037100048100051412006231300739008111100981117101512341119138912291451013420611145802015-000weightparentlchildrchild15900291weightparentlchildrchild159002291400371000481000514120062313007390081111009811171015123411191389122914510134206111458021215-000weightparentlchildrchild15900292weightparentlchildrchild159002291400371000481000514120062313007390081111009811171015123411191389122914510134206111458021215-000第七步weightparentlchildrchild15900293weightparentlchildrchild1590022914003710004810005141200623130073900811110098111710151234111913891229145101342156111458021215-000weightparentlchildrchild15900294weightparentlchildrchild15900229140037100048100051412006231300739008111100981117101512341119138912291451013421561114581521215-000weightparentlchildrchild15900295weightparentlchildrchild15900229140037100048100051412006231300739008111100981117101512341119138912291451013421561114581521215100000weightparentlchildrchild15900296weightparentlchildrchild159002291400371000481000514120062313007390081111009811171015123411191389122914510134215611145815212151000130weightparentlchildrchild15900297weightparentlchildrchild1590022914003710004810005141200623130073900811110098111710151234111913891229145101342156111458152121510001314weightparentlchildrchild15900298（4）編碼過程從葉子結(jié)點(diǎn)開始，向根回溯，來對葉子結(jié)點(diǎn)所代表的字符進(jìn)行編碼。（4）編碼過程從葉子結(jié)點(diǎn)開始，向根回溯，來對葉子99weightparentlchildrchild1590022914003710004810005141200623130073900811110098111710151234111913891229145101342156111458152121510001314weightparentlchildrchild159002100以第一個(gè)葉子結(jié)點(diǎn)為例：1的雙親結(jié)點(diǎn)為9，且1是9的左孩子，故分支應(yīng)該標(biāo)“0”，所以編碼“0”入棧。以第一個(gè)葉子結(jié)點(diǎn)為例：1的雙親結(jié)點(diǎn)為9，且1是9的左孩101以第一個(gè)葉子結(jié)點(diǎn)為例：0以第一個(gè)葉子結(jié)點(diǎn)為例：0102以第一個(gè)葉子結(jié)點(diǎn)為例：9的雙親結(jié)點(diǎn)為11，且9是11的右孩子，故分支應(yīng)該標(biāo)“1”，所以編碼“1”入棧。0以第一個(gè)葉子結(jié)點(diǎn)為例：9的雙親結(jié)點(diǎn)為11，且9是11的103以第一個(gè)葉子結(jié)點(diǎn)為例：01以第一個(gè)葉子結(jié)點(diǎn)為例：01104以第一個(gè)葉子結(jié)點(diǎn)為例：11的雙親結(jié)點(diǎn)為13，且11是13的右孩子，故分支應(yīng)該標(biāo)“1”，所以編碼“1”入棧。01以第一個(gè)葉子結(jié)點(diǎn)為例：11的雙親結(jié)點(diǎn)為13，且11是1105以第一個(gè)葉子結(jié)點(diǎn)為例：011以第一個(gè)葉子結(jié)點(diǎn)為例：011106以第一個(gè)葉子結(jié)點(diǎn)為例：13的雙親結(jié)點(diǎn)為15，且13是15的左孩子，故分支應(yīng)該標(biāo)“0”，所以編碼“0”入棧。011以第一個(gè)葉子結(jié)點(diǎn)為例：13的雙親結(jié)點(diǎn)為15，且13是1107以第一個(gè)葉子結(jié)點(diǎn)為例：0110以第一個(gè)葉子結(jié)點(diǎn)為例：0110108以第一個(gè)葉子結(jié)點(diǎn)為例：15的雙親結(jié)點(diǎn)為0，所以可以判斷15就是根結(jié)點(diǎn)，那么第一個(gè)結(jié)點(diǎn)編碼完畢，編碼應(yīng)該從棧頂向棧底讀，為“0110”。0110以第一個(gè)葉子結(jié)點(diǎn)為例：15的雙親結(jié)點(diǎn)為0，所以可以判斷109同理可以寫出其他葉子結(jié)點(diǎn)的編碼。同理可以寫出其他葉子結(jié)點(diǎn)的編碼。110樹和二叉樹哈夫曼樹及其應(yīng)用樹和二叉樹哈夫曼樹及其應(yīng)用1111.相關(guān)概念路徑：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)所經(jīng)過的分支序列或者說結(jié)點(diǎn)序列。如結(jié)點(diǎn)A到結(jié)點(diǎn)F的路徑為：A-B-E-FABCDEFG1.相關(guān)概念A(yù)BCDEFG112路徑長度：路徑上面的分支個(gè)數(shù)。如A-F的路徑長度為3。ABCDEFGABCDEFG113樹的路徑長度：從樹根到每一個(gè)結(jié)點(diǎn)的路徑長度之和。如左邊樹的路徑長度為：Len(A-B)+Len(A-C)+Len(A-D)+Len(A-E)+Len(A-F)+Len(A-G) =1+1+2+2+3+3=12ABCDEFG樹的路徑長度：從樹根到每一個(gè)結(jié)點(diǎn)的路徑長度之和。ABCDEF114結(jié)點(diǎn)的權(quán)值：在某些應(yīng)用中，樹中結(jié)點(diǎn)往往要和一定的數(shù)值聯(lián)系起來，那么這個(gè)數(shù)值通常稱為該結(jié)點(diǎn)的權(quán)值，簡稱權(quán)。如左圖。ABCDEFG412537結(jié)點(diǎn)的權(quán)值：在某些應(yīng)用中，樹中結(jié)點(diǎn)往往要和一定的數(shù)值聯(lián)系起來115結(jié)點(diǎn)的帶權(quán)路徑長度：該結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長度與該結(jié)點(diǎn)上權(quán)的乘積。如結(jié)點(diǎn)E的帶權(quán)路徑長度為:Len(E-A)*3=2*3=6ABCDEFG412537結(jié)點(diǎn)的帶權(quán)路徑長度：該結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長度與該結(jié)點(diǎn)上權(quán)的乘116樹的帶權(quán)路徑長度： 樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和。記作：WPL=w1*L1+w2*L2+……+wn*LnABCDEFGw1w2w3w4樹的帶權(quán)路徑長度：ABCDEFGw1w2w3w4117從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。這種編碼方式也可以對應(yīng)到二叉樹，如右圖所式這樣,這些編碼恢復(fù)成二叉樹的形式時(shí),不會形成A,B,C,D恰好為二叉樹的葉子結(jié)點(diǎn),如右圖當(dāng)A、B、C、D按照如下形式進(jìn)行編碼時(shí)。從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。當(dāng)A、B、C、D按照如下形式進(jìn)行編碼時(shí)。從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。其中A、B、C、D出現(xiàn)的次數(shù)分別為3、1、2、1。重復(fù)②和③，直到F只含一棵樹為止。下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右分支上面標(biāo)0。采取這種變長編碼方式，需要遵循一個(gè)原則，即每一個(gè)字符的編碼都不應(yīng)該是另一個(gè)字符編碼的前綴。15的雙親結(jié)點(diǎn)為0，所以可以判斷15就是根結(jié)點(diǎn)，那么第一個(gè)結(jié)點(diǎn)編碼完畢，編碼應(yīng)該從棧頂向棧底讀，為“0110”。這樣,這些編碼恢復(fù)成二叉樹的形式時(shí),不會形成A,B,C,D恰好為二叉樹的葉子結(jié)點(diǎn),如右圖以第一個(gè)葉子結(jié)點(diǎn)為例：從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。這樣,這些編碼恢復(fù)成二叉樹的形式時(shí),不會形成A,B,C,D恰好為二叉樹的葉子結(jié)點(diǎn),如右圖這八個(gè)權(quán)值作為葉子結(jié)點(diǎn)，最終形成的哈夫曼樹應(yīng)共有2*8-1=15個(gè)結(jié)點(diǎn)。9的雙親結(jié)點(diǎn)為11，且9是11的右孩子，故分支應(yīng)該標(biāo)“1”，所以編碼“1”入棧。從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。最優(yōu)二叉樹（哈夫曼樹）：給定n個(gè)權(quán)值{w1,w2,…,wn}，試構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子結(jié)點(diǎn)帶權(quán)為wi。構(gòu)造出來的二叉樹的形態(tài)可以有多個(gè)，我們把其中帶權(quán)路徑長度WPL最小的二叉樹稱作最優(yōu)二叉樹或者哈夫曼樹。ABCDEFGw1w2w3w4從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子1182.哈夫曼算法（1）如何構(gòu)造一棵哈夫曼樹。我們首先通過一個(gè)例子來演示一下構(gòu)造過程。2.哈夫曼算法（1）如何構(gòu)造一棵哈夫曼樹。119當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。7524當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。7524120從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。從葉子結(jié)點(diǎn)開始，向根回溯，來對葉子結(jié)點(diǎn)所代表的字符進(jìn)行編碼。（2）哈夫曼算法的語言描述如左邊樹的路徑長度為：這樣,這些編碼恢復(fù)成二叉樹的形式時(shí),不會形成A,B,C,D恰好為二叉樹的葉子結(jié)點(diǎn),如右圖11的雙親結(jié)點(diǎn)為13，且11是13的右孩子，故分支應(yīng)該標(biāo)“1”，所以編碼“1”入棧。以第一個(gè)葉子結(jié)點(diǎn)為例：13的雙親結(jié)點(diǎn)為15，且13是15的左孩子，故分支應(yīng)該標(biāo)“0”，所以編碼“0”入棧。也可以看出，每一個(gè)可用的編碼都可以轉(zhuǎn)化成二叉樹的形式，這樣編碼理論便可以與二叉樹的一些性質(zhì)結(jié)合起來，就可以應(yīng)用二叉樹的理論知識來解決編碼問題。這種編碼方式也可以對應(yīng)到二叉樹，如右圖所式以第一個(gè)葉子結(jié)點(diǎn)為例：下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右分支上面標(biāo)0。以第一個(gè)葉子結(jié)點(diǎn)為例：當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。下面對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)1，右分支上面標(biāo)0。對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。根據(jù)權(quán)值{3，1，2，1}構(gòu)造哈夫曼樹路徑長度：路徑上面的分支個(gè)數(shù)。從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)所代表字符的編碼。這樣,這些編碼恢復(fù)成二叉樹的形式時(shí),不會形成A,B,C,D恰好為二叉樹的葉子結(jié)點(diǎn),如右圖當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。75246從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子121當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。72465當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。72465122當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。7246511當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。7246511123當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。7246511當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。7246511124當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。724651118當(dāng)權(quán)值為{7，5，2，4}時(shí)，構(gòu)造哈夫曼樹。72465111125（2）哈夫曼算法的語言描述根據(jù)給定的n個(gè)權(quán)值{w1,w2,…,wn}構(gòu)成n棵二叉樹的集合F={T1,T2,…,Tn},其中每棵二叉樹Ti中只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹為空。在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹上根結(jié)點(diǎn)的權(quán)值之和。在F中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入F中。重復(fù)②和③，直到F只含一棵樹為止。這棵樹便是哈夫曼樹。（2）哈夫曼算法的語言描述根據(jù)給定的n個(gè)權(quán)值{w1,w2,…126對于字符串“ABACCDA”，共有7個(gè)字符，4種字符。其中A、B、C、D出現(xiàn)的次數(shù)分別為3、1、2、1。 現(xiàn)在要對字符串進(jìn)行0、1編碼，有哪些方法？哪一種編碼的長度最短？對于字符串“ABACCDA”，共有7個(gè)字1271.各種編碼方式（1）定長編碼---根據(jù)出現(xiàn)的字符種數(shù)進(jìn)行編碼 字符串“ABACCDA”中共出現(xiàn)4種字符，那么可以用2位表示。ABCD000110111.各種編碼方式（1）定長編碼---根據(jù)出現(xiàn)的字符種數(shù)進(jìn)行編1281.各種編碼方式（1）定長編碼---根據(jù)出現(xiàn)的字符種數(shù)進(jìn)行編碼 這種編碼方式可以對應(yīng)到二叉樹，如右圖所式ABCD00011011ABCD0001111.各種編碼方式（1）定長編碼---根據(jù)出現(xiàn)的字符種數(shù)進(jìn)行編1291.各種編碼方式（2）變長編碼 當(dāng)A、B、C、D按照如下形式進(jìn)行編碼時(shí)。ABCD011010111采取這種變長編碼方式，需要遵循一個(gè)原則，即每一個(gè)字符的編碼都不應(yīng)該是另一個(gè)字符編碼的前綴。否則就會出現(xiàn)二義性。1.各種編碼方式（2）變長編碼ABCD0110101111301.各種編碼方式（2）變長編碼這種編碼方式也可以對應(yīng)到二叉樹，如右圖所式 ABCD011010111ABC0011D011.各種編碼方式（2）變長編碼ABCD011010111AB131N個(gè)權(quán)值構(gòu)造的哈夫曼