第五章樹本章內(nèi)容：

*樹的定義和基本操作；

*

二叉樹的定義及遍歷、存儲(chǔ)結(jié)構(gòu)；

*樹的應(yīng)用；重點(diǎn)：

*樹的定義

*二叉樹的定義及遍歷序列

內(nèi)容§5.1樹的定義和基本術(shù)語§5.2二叉樹的定義及存儲(chǔ)結(jié)構(gòu)§5.3二叉樹的遍歷§5.4樹的存儲(chǔ)§5.5樹的應(yīng)用

§5.1樹的定義和基本術(shù)語一、樹的定義樹是由n個(gè)結(jié)點(diǎn)構(gòu)成的有限集合。

當(dāng)n=0時(shí)，稱為空樹。在一棵非空樹中（n>0）中，有且僅有一個(gè)特定的結(jié)點(diǎn)，稱根的結(jié)點(diǎn)；其余結(jié)點(diǎn)可分為m個(gè)（m≥0）互不相交的集合T1，T2……Tm，其中，每一個(gè)集合本身又是一棵樹,且稱為根的子樹?！?/p>

特點(diǎn)：樹中至少有一個(gè)結(jié)點(diǎn)—根,它沒有前驅(qū)結(jié)點(diǎn)，除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)；樹中各子樹是互不相交的集合，樹中所有結(jié)點(diǎn)可以有零個(gè)或多個(gè)后繼結(jié)點(diǎn)。有限集合T1，T2……Tm應(yīng)該“互不相交”，即任意兩個(gè)集合不能有相重的結(jié)點(diǎn)。

※樹的各個(gè)結(jié)點(diǎn)有不同層次關(guān)系，這種關(guān)系通常用圖形表示，但與自然界的樹木相反，習(xí)慣上將整棵樹的根畫在最上層，如圖5.1所示ABCDEFGHIJKLM有子樹的樹根子樹A只有根結(jié)點(diǎn)的樹圖5.1二、樹的相關(guān)術(shù)語結(jié)點(diǎn)(node)——表示樹中的元素，包括數(shù)據(jù)項(xiàng)及若干指向其子樹的分支結(jié)點(diǎn)的度(degree)——結(jié)點(diǎn)擁有的子樹個(gè)數(shù)葉子(leaf)——度為0的結(jié)點(diǎn)孩子(child)——結(jié)點(diǎn)子樹的根稱為該結(jié)點(diǎn)的孩子雙親(parents)——孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的~兄弟(sibling)——同一雙親的孩子樹的度——一棵樹中最大的結(jié)點(diǎn)度數(shù)※結(jié)點(diǎn)的層次(level)——從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層……※深度(depth)——樹中結(jié)點(diǎn)的最大層次數(shù)※森林(forest)——m(m0)棵互不相交的樹的集合※有序樹－

樹中結(jié)點(diǎn)的各子樹從左到右是有次序的，否則為無序樹。例：

如下圖5.2所示，回答問題：ABCDEFGHIJKLM結(jié)點(diǎn)A的度：3結(jié)點(diǎn)B的度：2結(jié)點(diǎn)M的度：0樹的度：3結(jié)點(diǎn)A的孩子：B，C，D結(jié)點(diǎn)B的孩子：E，F(xiàn)結(jié)點(diǎn)A的層次：1結(jié)點(diǎn)M的層次：4葉子：K，L，F(xiàn)，G，M，I，J結(jié)點(diǎn)I的雙親：D結(jié)點(diǎn)L的雙親：E結(jié)點(diǎn)B，C，D為兄弟結(jié)點(diǎn)K，L為兄弟結(jié)點(diǎn)F，G為堂兄弟結(jié)點(diǎn)A是結(jié)點(diǎn)F，G的祖先樹的深度：4圖5.2三、樹的表示方法

1、直觀表示法：圖5.3表示法

2、文氏圖法：hbacgdefijijdfghabe3、嵌套括號(hào)法

4、凹入表示法a(b(d,e(i,j),c(g,h)))abdeijfcgh四、樹的基本操作

見書上P68§5.2二叉樹一、二叉樹的定義和基本操作

1、二叉樹的定義一個(gè)二叉樹是n個(gè)結(jié)點(diǎn)的有限集合（n≥0），此集合或者是空集（n=0），或者是由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成。由上述定義可知，二叉樹可以是空集，其根可以有空的左子樹或右子樹，或者左、右子樹皆為空。

※特點(diǎn)：

(1)每個(gè)結(jié)點(diǎn)至多有二棵子樹(即不存在度大于2的結(jié)點(diǎn));(2)二叉樹的子樹有左、右之分，且其次序不能任意顛倒;一般地，二叉樹有五種基本形態(tài)，如圖5.3所示。A只有根結(jié)點(diǎn)的二叉樹空二叉樹AB右子樹為空AB左子樹為空ABC左、右子樹均非空?qǐng)D5.3

2、二叉樹的基本操作

見書上P70

3、幾種特殊的二叉樹

(1)滿二叉樹：

定義1：在一個(gè)二叉樹中，若第i層的結(jié)點(diǎn)數(shù)為2i-1，則稱此層的結(jié)點(diǎn)數(shù)是滿的，當(dāng)樹中的每一層都是滿的，則稱此二叉樹為滿二叉樹。

定義2：如果一個(gè)二叉樹中，除最下一層的各結(jié)點(diǎn)度數(shù)為0以外，其它各層結(jié)點(diǎn)的度數(shù)均等于2，則此二叉樹為滿二叉樹。

特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)。1231145891213671014151234567123114589126710123456滿二叉樹完全二叉樹(2)完全二叉樹：

定義：一顆深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)（自左而右）從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為~。

特點(diǎn)：※深度為k的完全二叉樹，其前k-1層是一顆滿二叉樹；※最后第k層的結(jié)點(diǎn)都盡量排在靠左的位置上。二、二叉樹的性質(zhì)

1、性質(zhì)1：證明：用歸納法證明之

i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)，是對(duì)的假設(shè)對(duì)所有j(1j<i)命題成立，即第j層上至多有個(gè)結(jié)點(diǎn)那么，第i-1層至多有個(gè)結(jié)點(diǎn)又二叉樹每個(gè)結(jié)點(diǎn)的度至多為2第i層上最大結(jié)點(diǎn)數(shù)是第i-1層的2倍，即故命題得證2、性質(zhì)2一顆深度為k的二叉樹中，最多有2k-1個(gè)結(jié)點(diǎn)(k1)證明：由性質(zhì)1，可得深度為k的二叉樹最大結(jié)點(diǎn)數(shù)是：3、性質(zhì)3：

對(duì)任何一棵二叉樹，如果其葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1證明：n1為二叉樹T中度為1的結(jié)點(diǎn)數(shù)因?yàn)椋憾鏄渲兴薪Y(jié)點(diǎn)的度均小于或等于2所以：其結(jié)點(diǎn)總數(shù)n=n0+n1+n2

又二叉樹中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都只有一個(gè)分支進(jìn)入設(shè)B為分支總數(shù)，則n=B+1

又：分支由度為1和度為2的結(jié)點(diǎn)射出，B=n1+2n2

于是，n=B+1=n1+2n2+1=n0+n1+n2n0=n2+14、性質(zhì)4：5、性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號(hào)，則對(duì)任一結(jié)點(diǎn)i(1in)，有：(1)如果i=1，則結(jié)點(diǎn)i是二叉樹的根，無雙親；如果i>1，則其雙親是i/2(2)如果2in，則其左孩子是2i；如果2i>n，則結(jié)點(diǎn)i無左孩子；(3)如果2i+1n，則其右孩子是2i+1；如果2i+1>n，則結(jié)點(diǎn)i無右孩子；作業(yè)1:書上P871、4、5三、二叉樹的存儲(chǔ)結(jié)構(gòu)

1、順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)：按滿二叉樹的結(jié)點(diǎn)層次編號(hào)（從上至下，從左至右），依次存放二叉樹中的數(shù)據(jù)元素，即將編號(hào)為i的結(jié)點(diǎn)存入一維數(shù)組的第i個(gè)單元。例如：一般二叉樹的存儲(chǔ)abcdefgabcde^^^^fg1234567891011特點(diǎn)：結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中,即這種次序應(yīng)能反映結(jié)點(diǎn)間的邏輯關(guān)系;浪費(fèi)空間，適于存儲(chǔ)滿二叉樹和完全二叉樹.●應(yīng)用：

◆由二叉樹，畫出此二叉樹的存儲(chǔ)結(jié)構(gòu)

◆由二叉樹的存儲(chǔ)結(jié)構(gòu)畫出此二叉樹Exercise1:Key:Exercise2:12345678910111213abc^de^^^f^^gabcedfgKey:

2、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)對(duì)于非完全二叉樹，可以采用鏈?zhǔn)?，鏈表的頭指針均指向根結(jié)點(diǎn)?！穸骀湵?/p>

結(jié)點(diǎn)結(jié)構(gòu)：

通常每個(gè)結(jié)點(diǎn)中設(shè)置三個(gè)域,即數(shù)據(jù)（值）域、左指針域和右指針域，其結(jié)點(diǎn)結(jié)構(gòu)如下：typedefstructnode{datatypedata;

structnode*lchild,*rchild;}JD;結(jié)點(diǎn)定義：ABCDEFG在n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指針域lchilddatarchild

A^B^C^

D^E^F^^G^例如：●三叉鏈表結(jié)點(diǎn)結(jié)構(gòu)：lchilddataparentrchildABCDEFG

A^^

B

C^

D

E^F^^G^

§5.3二叉樹的遍歷一、遍歷的概念1、遍歷(Traversal)是指按一定的規(guī)律訪問樹的每個(gè)結(jié)點(diǎn)，且每個(gè)結(jié)點(diǎn)只被訪問一次的過程，即找一個(gè)完整而有規(guī)律的走法，將非線性結(jié)構(gòu)的樹中的結(jié)點(diǎn)排列成一個(gè)線性序列的過程。2、遍歷的常用方法：先根（序）遍歷：先訪問樹的根結(jié)點(diǎn)，然后依次先根遍歷根的每棵子樹；后根（序）遍歷：先依次遍歷每棵子樹，然后訪問根結(jié)點(diǎn)；●中序遍歷：先依次訪問樹的左子樹，根結(jié)點(diǎn)，然后訪問樹的右子樹；按層次遍歷：先訪問第一層上的結(jié)點(diǎn)，然后依次遍歷第二層，……第n層的結(jié)點(diǎn)。二、二叉樹的遍歷

一個(gè)非空的二叉樹由根結(jié)點(diǎn)及左、右子樹這三個(gè)基本部分組成，因此若能依次遍歷這三部分，便是遍歷了整個(gè)二叉樹?？梢园茨撤N次序執(zhí)行三個(gè)操作：訪問結(jié)點(diǎn)本身，遍歷該結(jié)點(diǎn)左子樹，遍歷該結(jié)點(diǎn)右子樹，操作排列次序：①左、根、右；③

根、左、右；⑤

左、右、根；②右、根、左；④

根、右、左；⑥

右、左、根；

◆由于實(shí)際問題一般都是要求左子樹較右子樹先遍歷，故只采用其中①、③、⑤三種遍歷次序，分別稱為中序遍歷、先序遍歷和后序遍歷。

◆對(duì)于用順序法表示的二叉樹，各結(jié)點(diǎn)在數(shù)組中的編號(hào)很有規(guī)律，其遍歷較容易進(jìn)行，但對(duì)于用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示的二叉樹，進(jìn)行遍歷就復(fù)雜一些。

◆三種遍歷次序以遞歸的形式定義：1、先序（Preorder）遍歷若遍歷的二叉樹不為空，則依次執(zhí)行下列操作：訪問根結(jié)點(diǎn)；先序遍歷左子樹；先序遍歷右子樹。

2、中序（Inorder）遍歷若遍歷的二叉樹不為空，則依次執(zhí)行下列操作：中序遍歷左子樹；訪問根結(jié)點(diǎn)；中序遍歷右子樹。

3、后序（Postorder）遍歷若遍歷的二叉樹為空，執(zhí)行空操作；否則依次執(zhí)行下列操作：后序遍歷左子樹；后序遍歷右子樹；訪問根結(jié)點(diǎn)。例：按不同的遍歷方法，寫出二叉樹遍歷所得到的結(jié)點(diǎn)序列。ADBC>>DDLRADLRDLR>B>>CDLR◆先序遍歷:◆先序遍歷序列：ABDC◆中序遍歷:◆中序遍歷序列：BDACLDRBLDRLDR>A>>D>>CLDRADBCADBC◆后序遍歷:◆后序遍歷序列：DBCA

LRDLRDLRDA>>D>>CLRDExercise1:-+/a*b-efcdKey:

先序：-+a*b-cd/ef

中序：a+b*c-d-e/f

后序：abcd-*+ef/-寫出下列二叉樹的三種序列。Exercise2:書上，P87Exercise3:

已知一個(gè)二叉樹的前序和中序分別為ABCDEFGH和BDCEAFHG，請(qǐng)畫出此二叉樹。Key3:三、二叉樹遍歷的算法typedefstructnode{datatypedata;

structnode*left,*right;}btree;鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的結(jié)點(diǎn)定義如下：◆先序遍歷遞歸算法：voidpreorder(JD*bt){if(bt!=NULL){printf("%d\t",bt->data);preorder(bt->lchild);preorder(bt->rchild);}}返回pre(TR);返回T>右是空返回返回返回返回pre(TR);T>左是空返回T>左是空返回TDprintf(D);pre(TL);Dpre(TR);TBprintf(B);pre(TL);BTCprintf(C);pre(TL);C主程序Pre(T)TAprintf(A);pre(TL);AT>左是空返回T>右是空返回pre(TR);先序序列：ABDC◆中序遍歷遞歸算法：voidinorder(btree*p){if(p！=NULL){

inorder(p->left);

printf("%d",p->data);

inorder(p->right);}}作業(yè)2:

1、有一顆二叉樹如下圖，分別寫出其先序、中序、后序遍歷序列。abcdehifg2、書上，P87

33、有一顆二叉樹如下圖，分別寫出其先序、中序、后序遍歷序列。4、采用順序存儲(chǔ)方法和鏈?zhǔn)酱鎯?chǔ)方法分別畫出如下圖所示二叉樹的存儲(chǔ)結(jié)構(gòu)。Key1:

先序：abdehcfgi

中序：dbheafcig

后序：dhebfIgcaKey3:中序遍歷序列：H，D，I，B，E，A，F(xiàn)，C，G先序遍歷序列：A，B，D，H，I，E，C，F(xiàn)，G后序遍歷序列：H，I，D，E，B，F(xiàn)，G，C，AKey4:§5.4樹的存儲(chǔ)一、樹的存儲(chǔ)方式1、雙親表示法實(shí)現(xiàn)：定義一組連續(xù)的結(jié)構(gòu)數(shù)組存放樹的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)含兩個(gè)域：數(shù)據(jù)域：存放結(jié)點(diǎn)本身信息雙親域：指示本結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中的位置typedefstructnode{datatypedata;

intparent;}JD;JDt[M];◆結(jié)點(diǎn)定義如下：特點(diǎn)：找雙親容易，找孩子難abcdefhgiacdefghib012235551096012345789dataparent0號(hào)單元不用或存結(jié)點(diǎn)個(gè)數(shù)如何找孩子結(jié)點(diǎn)例：2、孩子表示法多重鏈表：每個(gè)結(jié)點(diǎn)有多個(gè)指針域，分別指向其子樹的根定長(zhǎng)結(jié)點(diǎn)的多重鏈表：取樹的度D作為每個(gè)結(jié)點(diǎn)的指針域個(gè)數(shù)，即結(jié)點(diǎn)的指針個(gè)數(shù)相等；不定長(zhǎng)結(jié)點(diǎn)的多重鏈表：樹中每個(gè)結(jié)點(diǎn)都取它自己的度d作為指針域的個(gè)數(shù)，而終端結(jié)點(diǎn)不設(shè)指針域。datachild1child2……….childDdatadegreechild1child2……….childd孩子結(jié)點(diǎn)：typedefstructnode{intchild;/*該結(jié)點(diǎn)在表頭數(shù)組中下標(biāo)*/

structnode*next;/*指向下一孩子結(jié)點(diǎn)*/

}JD;表頭結(jié)點(diǎn)：typedefstructtnode

{datatypedata;/*數(shù)據(jù)域*/

structnode*fc;/*指向第一個(gè)孩子結(jié)點(diǎn)*/}TD;TDt[M];/*t[0]不用*/●孩子鏈表：每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)用單鏈表存儲(chǔ)，再用含n個(gè)元素的結(jié)構(gòu)數(shù)組指向每個(gè)孩子鏈表.例1:見P76abcdefhgi6012345789acdefghibdatafc23^45^978^6^如何找雙親結(jié)點(diǎn)例2：

3、帶雙親的孩子表示法abcdefhgi612345789acdefghibdatafc23459786^^^^^^^^^012235551parent4、孩子兄弟表示法實(shí)現(xiàn)：用二叉鏈表作樹的存儲(chǔ)結(jié)構(gòu)，鏈表中每個(gè)結(jié)點(diǎn)的兩個(gè)指針域分別指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)特點(diǎn)操作容易破壞了樹的層次typedefstructnode{datatypedata;

structnode*fch,*nsib;}JD;abcdefhgi例：

a^b

c^^d

e^

f^^g

h

i^二、普通樹與二叉樹的轉(zhuǎn)換

普通樹可用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來表示，每個(gè)結(jié)點(diǎn)包括數(shù)據(jù)域以及指向它各個(gè)兒子結(jié)點(diǎn)的指針域。若同一樹的各結(jié)點(diǎn)有相同數(shù)據(jù)結(jié)構(gòu)，則只能按結(jié)點(diǎn)度數(shù)最大值（該樹的度數(shù)）給每個(gè)結(jié)點(diǎn)設(shè)置指針。這樣較浪費(fèi)存儲(chǔ)空間。按照一定的原則將普通樹用二叉樹來表示，是較好的表示方法。

將所有兄弟結(jié)點(diǎn)之間加一連線；對(duì)每個(gè)結(jié)點(diǎn)，保留與其左兒子結(jié)點(diǎn)的連線，去掉該結(jié)點(diǎn)與其它兒子結(jié)點(diǎn)的連線；將樹向順時(shí)針方向旋轉(zhuǎn)45°

把普通樹轉(zhuǎn)換成相應(yīng)的二叉樹，具體方法如下：例1：把普通樹轉(zhuǎn)換成相應(yīng)的二叉樹書上P77

圖5.18例2：樹經(jīng)過變換，可得下面的形式：得到的已是一棵二叉樹，若按順時(shí)針方向?qū)⑺D(zhuǎn)就更清楚地變?yōu)橄旅嫠镜亩鏄洹Ｓ捎跇涓鶝]有兄弟，所以樹轉(zhuǎn)換為二叉樹后，二叉樹的根結(jié)點(diǎn)的右子樹必為空。Exercise:

把普通樹轉(zhuǎn)換成相應(yīng)的二叉樹1、2、abcdabcedf§5.5樹的應(yīng)用一、二叉排序樹1、二叉排序樹的定義所謂排序，就是將一組雜亂無序的數(shù)據(jù)按一定的規(guī)律順序排列起來。對(duì)一個(gè)二叉樹若規(guī)定：任一結(jié)點(diǎn)如果有左子樹，其左子樹各結(jié)點(diǎn)的數(shù)據(jù)必須小于該結(jié)點(diǎn)的數(shù)據(jù)；任一結(jié)點(diǎn)如果有右子樹，其右子樹各結(jié)點(diǎn)的數(shù)據(jù)必須等于或大于該結(jié)點(diǎn)的數(shù)據(jù)，按這樣規(guī)定構(gòu)成的二叉樹叫做二叉排序樹。在一個(gè)二叉排序樹中，其結(jié)點(diǎn)是按左子樹、根和右子樹的次序有序的，故對(duì)二叉排序樹進(jìn)行中序遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。以整數(shù)類型的數(shù)據(jù)排列為例，設(shè)要求將一批正整數(shù)按遞增的次序排列，若有相同的數(shù)據(jù)，則按先后次序列出。按二叉排序樹要求可將這批正整數(shù)構(gòu)成一個(gè)二叉排序樹，每個(gè)參加排序的數(shù)據(jù)對(duì)應(yīng)二叉樹的一個(gè)結(jié)點(diǎn)，然后，對(duì)這種樹進(jìn)行一次中序遍歷，按訪問各結(jié)點(diǎn)的順序輸出所有結(jié)點(diǎn)的數(shù)據(jù)，這些數(shù)據(jù)就是按排序所要求的次序排列的。中序遍歷序列：1，2，3，4，5，6，7，8，9，10，112、二叉排序樹的生成設(shè)已知一組待排序的數(shù)據(jù)，若要構(gòu)造出對(duì)應(yīng)的二叉排序樹，一般是采取從空樹開始，陸續(xù)插入一系列結(jié)點(diǎn)的辦法，逐步生成對(duì)應(yīng)的二叉排序樹。即首先以第一個(gè)數(shù)據(jù)構(gòu)成根結(jié)點(diǎn)，以后對(duì)應(yīng)每個(gè)數(shù)據(jù)插入一個(gè)結(jié)點(diǎn)，在插入過程中，原有的結(jié)點(diǎn)位置均不再變動(dòng)，只是將新數(shù)據(jù)結(jié)點(diǎn)作為一個(gè)端結(jié)點(diǎn)插入到合適的位置處，使樹中任何結(jié)點(diǎn)與其左、右子樹結(jié)點(diǎn)數(shù)據(jù)之間的關(guān)系都符合二叉排序樹的要求例：待排序的數(shù)據(jù)為一組正整數(shù)：10,15,20,5,10,30,9,7下圖二叉排序樹生成過程假設(shè)一組待排序的數(shù)據(jù)均為正整數(shù)，并以－1為結(jié)束輸入的標(biāo)志，生成二叉排序樹函數(shù)如下：

voidcreat(btree*b){

intx;b=NULL;do{

scanf("%d",&x);/*讀入一個(gè)整數(shù)*/

insert(x,b);/*插入該結(jié)點(diǎn)*/}while(x!=-1);}生成二叉排序樹算法:二、哈夫曼樹Huffman1、哈夫曼樹基本術(shù)語：

1)路徑：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。2)路徑長(zhǎng)度：路徑上的分支數(shù)稱為這兩點(diǎn)之間的路徑長(zhǎng)度。3)樹的路徑長(zhǎng)度：樹的路徑長(zhǎng)度是從樹的根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和，一般記作pl。在結(jié)點(diǎn)數(shù)目相同的二叉樹中，完全二叉樹或滿二叉樹的路徑長(zhǎng)度最短。

4)結(jié)點(diǎn)的權(quán)：在許多實(shí)際應(yīng)用中，常常將樹中結(jié)點(diǎn)賦予一個(gè)有某種意義的實(shí)數(shù)，稱為該結(jié)點(diǎn)的權(quán)。5)帶權(quán)路徑長(zhǎng)度：從樹的根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)上權(quán)的乘積，稱為該結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度。樹的帶權(quán)路徑長(zhǎng)度：是樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，通常記為：

其中n表示葉子結(jié)點(diǎn)個(gè)數(shù)，wi和li分別表示葉子結(jié)點(diǎn)ki的權(quán)值和根到ki之間的路徑長(zhǎng)度。給定一組n個(gè)實(shí)數(shù)，以它們作為各個(gè)葉子結(jié)點(diǎn)的權(quán)，可構(gòu)成不同的有n個(gè)葉子結(jié)點(diǎn)的二叉樹，這些二叉樹的帶權(quán)路徑長(zhǎng)度wpl可能不同。P832、哈夫曼樹哈夫曼樹又稱為最優(yōu)二叉樹，它是這樣定義的：設(shè)有n個(gè)權(quán)值{w1，w2，…，wn}，以這些權(quán)值為各個(gè)葉子結(jié)點(diǎn)的權(quán)所構(gòu)成的二叉樹中，帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹叫做哈夫曼樹。哈夫曼(Huffman)于1952年提出了得到這種樹的算法，因此相應(yīng)的算法稱為哈夫曼算法。將n個(gè)權(quán)值{w1，w2，…，wn}按遞增次序排列，設(shè)其順序?yàn)閣1，w2，…，wn，取出最小的兩個(gè)w1和w2，分別作為根結(jié)點(diǎn)的左、右兒子結(jié)點(diǎn)的權(quán)組成一個(gè)二叉樹，并認(rèn)為其根結(jié)點(diǎn)的權(quán)w12=w1+w2；將w12按其數(shù)值大小插入到w3至wn之間，使數(shù)值仍保持為遞增的次序；3、哈夫曼算法再取出最小的兩個(gè)作為根的左、右兒子的權(quán)組成二叉樹，也令根的權(quán)等于此兩數(shù)值之和，并同樣將此根結(jié)點(diǎn)按權(quán)值大小插入到剩下的數(shù)據(jù)中，保持?jǐn)?shù)值的遞增次序。如此重復(fù)進(jìn)行下去，直到構(gòu)成一個(gè)二叉樹為止，即得到哈夫曼樹。如下圖：

哈夫曼算法過程例：給定4個(gè)數(shù)：7，5，2，4Exercise:

1、給定一組權(quán)值5個(gè)數(shù)：9，1，8，5，3構(gòu)造一個(gè)哈夫曼樹。4、哈夫曼編碼哈夫曼編碼（Haffmancoding）是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)，該技術(shù)一般可將數(shù)據(jù)壓縮20%至90%，其壓縮效率取決于被壓縮數(shù)據(jù)的特征。通常我們將壓