1、二叉樹的一個重要應(yīng)用最優(yōu)樹問題給定一組權(quán)w1,w2,wt,不妨設(shè)w1w2wt。設(shè)有一棵二叉樹，共有t片樹葉，分別帶權(quán)w1,w2,wt,該二叉樹稱為帶權(quán)二叉樹。定義1 在帶權(quán)二叉樹中，若帶權(quán)為wi的樹葉，其通路長度為L(wi)，我們把w(T)=wiL(wi)稱為該帶權(quán)二叉樹的權(quán)。在所有帶權(quán)w1,w2,wt的二叉樹中，w(T)最小的那棵樹，稱為最優(yōu)樹。ti=1定理3 設(shè)T為帶權(quán)w1w2wt的最優(yōu)樹，則 a）帶權(quán)w1,w2,wt的樹葉vw1,vw2是兄弟。 b）以樹葉vw1,vw2為兒子的分枝點，其通路長度最長。代之以w1+w2w2w1例1：設(shè)有一組權(quán) 2、3、5、7、11、13、 17、19、23

2、、29、 31、37、41。求相應(yīng)的最優(yōu)樹。二叉樹的另一個應(yīng)用前綴碼問題定義2 給定一個序列的集合，若沒有一個序列是另一個序列的前綴，該序列集合稱為前綴碼。例如：000，001，01，10，11是前綴碼，而1，0001， 000就不是前綴碼。定理5 任意一棵二叉樹的樹葉可對應(yīng)一個前綴碼。證明 給定一棵二叉樹，從每一個分枝點引出兩條邊，對左側(cè)邊標以0，對右側(cè)邊標以1，則每片樹葉將可標定一個0和1的序列，它是由樹根到這片樹葉的通路上各邊標號所組成的序列，定理6 任何一個前綴碼都對應(yīng)一棵二叉樹。證明 設(shè)給定一個前綴碼，h表示前綴碼中最長序列的長度。我們畫出一棵高度為h的正則二叉樹，并給每一分枝點射出

3、的兩條邊標以0和1，對應(yīng)于前綴碼中的每一序列的結(jié)點，給予一個標記，并將標記結(jié)點的所有后裔和射出的邊全部刪去，這樣得到一棵二叉樹，再刪去其中未加標記的樹葉，得到一棵新的二叉樹，它的樹葉就對應(yīng)給定的前綴碼。圖（b）中所對應(yīng)的前綴碼00，001，01，1。設(shè)有二進制序列00010011011101001可譯為000，1，001，1，01，1，1，01，001。 我們知道，在遠距離通訊中，常常用0和 1的字符串作為英文字母的傳送信息，因為英文字母共有26個，故如用不等長的H進制序列表示 26個英文字母時，由于長度為 1的序列有 2個，長度為2的H進制序列有 2個，長度為 3的有 2個，依此類推，我們有

4、 22，226 ZI12P26， 474因此，用長度不超過四的二進制序列就可表達26個不同英文字母。但是由于字母使用的頻繁程度不同，為了減少信息量，人們希望用較短的序列去表示頻繁使用的字母。當(dāng)使用不同長度的序列表示字母時，我們要考慮的另一個問題是如何對接收到的字符串進行詳碼？ 證明設(shè)在帶權(quán)W，創(chuàng)b，。的最優(yōu)樹中，0是通路長度最長的分校點，用的兒子分別帶權(quán)Wi和。0，故有 LtheDeL（Wi L（叫L（W） 若L枷JLJ，將叩與一對調(diào)，得到新材T。則 。許一叫n一（LedW十Ltw叨J 一（L（叫W十L（W卜W） 一L0wih一。干L（。1）tw一心 一（w一w）（L（W）一 L （w）0即。

5、叨）。w，與T是最優(yōu)樹的假定矛盾。故工ho一L（心。 同理可證LboL（W）。因此 Ltw）一石功一LedL。）分別將o七，。與o七，。對調(diào)得到一棵最優(yōu)樹，其中帶權(quán)創(chuàng)h和以。的樹葉是兄弟?；?證明根據(jù)題設(shè)，有 一。（萬一。W卜。1W。若T不是最優(yōu)樹，則必有另一棵帶權(quán)地十。，。a，。；的最優(yōu)樹P。對y中帶權(quán)地十創(chuàng)會的樹葉。生成兩個兒子，得到新樹分，則一 。（f一叫p）。l十一。 因為T”是帶權(quán)。1Wb，W，。t的最優(yōu)樹，故 ho（”）。（T。如果。W）。仔，則。曲。側(cè)，與Y是帶權(quán)。，。最優(yōu)樹的假設(shè)矛盾，因此”、“ 。卜。們，er是帶權(quán)Ww，w，W的最優(yōu)樹。回 根據(jù)上述兩條定理，要畫一棵帶有：個權(quán)的最優(yōu)裕，可簡化為畫一棵帶有t一1個權(quán)的最優(yōu)樹，而這又可簡化為畫一棵帶有t一2