第六章-樹和二叉樹2課件

第六章樹和二叉樹(2)第六章樹和二叉樹(2)1主要內(nèi)容樹的定義和基本術(shù)語二叉樹遍歷二叉樹線索二叉樹樹、森林與二叉樹赫夫曼樹及其應(yīng)用主要內(nèi)容樹的定義和基本術(shù)語24、線索二叉樹4.1何謂線索二叉樹？4.2線索二叉樹的存儲結(jié)構(gòu)4.3線索二叉樹的遍歷4、線索二叉樹34.1何謂線索二叉樹？為什么要線索？1）二叉樹的存儲結(jié)構(gòu)中沒有反映出某結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)是什么。2）二叉樹的二叉鏈表存儲結(jié)構(gòu)中的那些空指針域可利用。4.1何謂線索二叉樹？為什么要線索？1）二叉樹的存儲結(jié)構(gòu)中4ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA遍歷二叉樹的結(jié)果是，求得結(jié)點(diǎn)的一個(gè)線性序列。ABCDEFGHK例如:先序序列:中序序列:后序序列:遍歷二5ABCDEFGHK^

D^

C^^

B

E^指向該線性序列中的“前驅(qū)”和“后繼”的指針，稱作“線索”。包含“線索”的存儲結(jié)構(gòu)，稱作“線索鏈表”。加上線索的二叉樹，稱作“線索二叉樹”。ABCDEFGH6lchild

ltag

data

rtag

rchild0:lchild指向該結(jié)點(diǎn)的左孩子1:lchild指向該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)0:rchild指向該結(jié)點(diǎn)的右孩子1:rchild指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)ltag=rtag=4.2線索二叉樹的存儲結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)線索鏈表如此定義的二叉樹的存儲結(jié)構(gòu)稱作“線索鏈表”。lchildltagdatartagrchild07第六章--樹和二叉樹2課件8第六章--樹和二叉樹2課件9先序線索二叉樹：先序序列為：ABCD線索二叉樹畫法先序線索二叉樹：線索二叉樹畫法10中序線索二叉樹：中序序列為：BADC中序線索二叉樹：11后序線索二叉樹：后序序列為：BDCA后序線索二叉樹：125、樹、森林與二叉樹5.1樹的三種存儲結(jié)構(gòu)5.2樹、森林和二叉樹的轉(zhuǎn)換5、樹、森林與二叉樹135.1樹的三種存儲結(jié)構(gòu)一、雙親表示法二、孩子鏈表表示法三、樹的二叉鏈表(孩子-兄弟） 存儲表示法5.1樹的三種存儲結(jié)構(gòu)一、雙親表示法二、孩子鏈表表示法三、14ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5dataparent一、雙親表示法:ABCDEFG0A-1datapare15

typedefstructPTNode{Elemdata;

intparent;//雙親位置域

}

PTNode;

dataparent#defineMAX_TREE_SIZE100結(jié)點(diǎn)結(jié)構(gòu):C語言的類型描述:typedefstructPTNode{dat16typedefstruct{PTNodenodes[MAX_TREE_SIZE];

intr,n;//根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)

}

PTree;樹結(jié)構(gòu):typedefstruct{樹結(jié)構(gòu):17ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

4

datafirstchild123456二、孩子鏈表表示法:-1000224ABCDEFG0A-1datafir18typedefstructCTNode{

intchild;

structCTNode*next;

}*ChildPtr;孩子結(jié)點(diǎn)結(jié)構(gòu):

childnextC語言的類型描述:typedefstructCTNode{孩子結(jié)點(diǎn)結(jié)構(gòu):19

typedefstruct{Elemdata;ChildPtrfirstchild;//孩子鏈的頭指針

}

CTBox;雙親結(jié)點(diǎn)結(jié)構(gòu)

datafirstchildtypedefstruct{雙親結(jié)點(diǎn)結(jié)構(gòu)data20typedefstruct{CTBoxnodes[MAX_TREE_SIZE];

intn,r;//結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置

}

CTree;樹結(jié)構(gòu):typedefstruct{樹結(jié)構(gòu):21ABCDEFG

ABCEDFGroot

ABCEDFG

三、樹的二叉鏈表(孩子-兄弟）存儲表示法ABCDEFGAroot22typedefstructCSNode{Elemdata;

structCSNode

*firstchild,*nextsibling;}CSNode,*CSTree;C語言的類型描述:結(jié)點(diǎn)結(jié)構(gòu):

firstchilddatanextsiblingtypedefstructCSNode{C語言的類型描述235.2樹、森林和二叉樹的轉(zhuǎn)換樹和二叉樹之間的對應(yīng)關(guān)系

樹：兄弟關(guān)系二叉樹：雙親和右孩子樹：雙親和長子二叉樹：雙親和左孩子AEBCFDGABCDEFG5.2樹、森林和二叉樹的轉(zhuǎn)換樹和二叉樹之間的對應(yīng)關(guān)系A(chǔ)EB241.兄弟加線.樹轉(zhuǎn)換為二叉樹示例ABCDEFG1.兄弟加線.樹轉(zhuǎn)換為二叉樹示例ABCDEFG252.保留雙親與第一孩子連線,刪去與其他孩子的連線.ABCDEFG1.兄弟加線.樹轉(zhuǎn)換為二叉樹示例2.保留雙親與第一孩子連線,刪去與其他孩子的連線.ABCDE263.順時(shí)針轉(zhuǎn)動(dòng),使之層次分明.2.保留雙親與第一孩子連線,刪去與其他孩子的連線.1.兄弟加線.ABCDEFG樹轉(zhuǎn)換為二叉樹示例3.順時(shí)針轉(zhuǎn)動(dòng),使之層次分明.2.保留雙親與第一孩子連線,刪273.順時(shí)針轉(zhuǎn)動(dòng),使之層次分明.2.保留雙親與第一孩子連線,刪去與其他孩子的連線.1.兄弟加線.GDABECF樹轉(zhuǎn)換為二叉樹示例3.順時(shí)針轉(zhuǎn)動(dòng),使之層次分明.2.保留雙親與第一孩子連線,刪28樹轉(zhuǎn)換為二叉樹步驟⑴加線——樹中所有相鄰兄弟之間加一條連線。

⑵去線——對樹中的每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪去它與其它孩子結(jié)點(diǎn)之間的連線。

⑶層次調(diào)整——以根結(jié)點(diǎn)為軸心，將樹順時(shí)針轉(zhuǎn)動(dòng)一定的角度，使之層次分明。

樹轉(zhuǎn)換為二叉樹步驟⑴加線——樹中所有相鄰兄弟之間加一條連線29森林轉(zhuǎn)換為二叉樹步驟⑴將森林中的每棵樹轉(zhuǎn)換成二叉樹；⑵從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹連起來后，此時(shí)所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。森林轉(zhuǎn)換為二叉樹步驟⑴將森林中的每棵樹轉(zhuǎn)換成二叉樹；30二叉樹轉(zhuǎn)換為樹或森林步驟⑴加線——若某結(jié)點(diǎn)x是其雙親y的左孩子，則把結(jié)點(diǎn)x的右孩子、右孩子的右孩子、……，都與結(jié)點(diǎn)y用線連起來；⑵去線——?jiǎng)h去原二叉樹中所有的雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線；⑶

層次調(diào)整——整理由⑴、⑵兩步所得到的樹或森林，使之層次分明。

二叉樹轉(zhuǎn)換為樹或森林步驟⑴加線——若某結(jié)點(diǎn)x是其雙親y的31FHGEAICDBFHGDCEBAIFEDCBAHGI加線去線層次調(diào)整IHGBCDAFE二叉樹轉(zhuǎn)換為樹或森林示例FHGEAICDBFHGDCEBAIFEDCBAHGI加線去326、赫夫曼樹及其應(yīng)用6.1相關(guān)概念6.2如何構(gòu)造最優(yōu)二叉樹（赫夫曼樹）6.3赫夫曼樹應(yīng)用——赫夫曼編碼6、赫夫曼樹及其應(yīng)用6.1相關(guān)概念336.1相關(guān)概念葉子結(jié)點(diǎn)的權(quán)值：對葉子結(jié)點(diǎn)賦予的一個(gè)有意義的數(shù)值量。

二叉樹的帶權(quán)路徑長度：設(shè)二叉樹具有n個(gè)帶權(quán)值的葉子結(jié)點(diǎn)，從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的路徑長度與相應(yīng)葉子結(jié)點(diǎn)權(quán)值的乘積之和。記為：WPL=?=nkkklw1第k個(gè)葉子的權(quán)值；從根結(jié)點(diǎn)到第k個(gè)葉子的路徑長度最優(yōu)二叉樹（赫夫曼樹）：在所有含n個(gè)葉子結(jié)點(diǎn)、并帶相同權(quán)值的二叉樹中，必存在一棵其帶權(quán)路徑長度取最小值的二叉樹，稱為“最優(yōu)二叉樹”。6.1相關(guān)概念葉子結(jié)點(diǎn)的權(quán)值：對葉子結(jié)點(diǎn)賦予的一個(gè)有意義的3427975492WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=895427975492WPL(T)=735赫夫曼樹的特點(diǎn)：1.權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。2.只有度為0（葉子結(jié)點(diǎn)）和度為2（分支結(jié)點(diǎn)）的結(jié)點(diǎn)，不存在度為1的結(jié)點(diǎn).

2347WPL=32WPL=41WPL=3023477423赫夫曼樹的特點(diǎn)：2347WPL=32366.2如何構(gòu)造最優(yōu)樹赫夫曼算法基本思想：⑴初始化：由給定的n個(gè)權(quán)值{w1，w2，…，wn}構(gòu)造n棵只有一個(gè)根結(jié)點(diǎn)的二叉樹，從而得到一個(gè)二叉樹集合F＝{T1，T2，…，Tn}；⑵選取與合并：在F中選取根結(jié)點(diǎn)的權(quán)值最小的兩棵二叉樹分別作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和；⑶刪除與加入：在F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到F中；

⑷

重復(fù)⑵、⑶兩步，當(dāng)集合F中只剩下一棵二叉樹時(shí)，這棵二叉樹便是赫夫曼樹。

6.2如何構(gòu)造最優(yōu)樹赫夫曼算法基本思想：37例：W＝{2，3，4，5}

赫夫曼樹的構(gòu)造過程重復(fù)第2步5432

554

9重復(fù)第3步

554

932例：W＝{2，3，4，5}赫夫曼樹的構(gòu)造過程重復(fù)第2步54386.3赫夫曼樹應(yīng)用——赫夫曼編碼編碼：給每一個(gè)對象標(biāo)記一個(gè)二進(jìn)制位串來表示一組對象。前綴編碼：一組編碼中任一編碼都不是其它任何一個(gè)編碼的前綴。前綴編碼保證了在解碼時(shí)不會(huì)有多種可能。利用赫夫曼樹可以構(gòu)造一種不等長的二進(jìn)制編碼，并且構(gòu)造所得的赫夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長度最短。6.3赫夫曼樹應(yīng)用——赫夫曼編碼編碼：給每一個(gè)對象標(biāo)記一39例：一組字符{A,B,C,D,E,F,G}出現(xiàn)的頻率分別是{9,11,5,7,8,2,3}，設(shè)計(jì)最經(jīng)濟(jì)的編碼方案。9523510191126871545000000111111ABDCEFG編碼方案：A：00B：10C：010D：110E：111F：0110G：0111例：一組字符{A,B,C,D,E,F,G}出現(xiàn)的40本章小結(jié)1.理解二叉樹線索化的實(shí)質(zhì)是建立結(jié)點(diǎn)與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系。2.熟悉樹的各種存儲結(jié)構(gòu)及其特點(diǎn)，掌握樹和森林與二叉樹的轉(zhuǎn)換方法。3.了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和赫夫曼編碼的方法。本章小結(jié)1.理解二叉樹線索化的實(shí)質(zhì)是建立結(jié)點(diǎn)與其在相應(yīng)序41作業(yè)：（11月5日交（一））（一）本或紙1、對于下圖所示的二叉樹，請將它轉(zhuǎn)換成森林。2、設(shè)F＝{T1,T2,T3}是森林，請畫出其對應(yīng)的二叉樹。其森林如下圖所示。ABCDEFGHIJABCDEFGHJIK作業(yè)：（11月5日交（一））（一）本或紙ABCDEFGHIJ423、以數(shù)據(jù)集{2,5,7,9,13}為權(quán)值構(gòu)造一棵赫夫曼樹，并計(jì)算其帶權(quán)路徑長度。（二）上機(jī)（不交）1、赫夫曼樹演示2、赫夫曼樹實(shí)驗(yàn)，體會(huì)各算法運(yùn)算過程3、以數(shù)據(jù)集{2,5,7,9,13}為權(quán)值構(gòu)造一棵赫夫曼樹，43第六章樹和二叉樹(2)第六章樹和二叉樹(2)44主要內(nèi)容樹的定義和基本術(shù)語二叉樹遍歷二叉樹線索二叉樹樹、森林與二叉樹赫夫曼樹及其應(yīng)用主要內(nèi)容樹的定義和基本術(shù)語454、線索二叉樹4.1何謂線索二叉樹？4.2線索二叉樹的存儲結(jié)構(gòu)4.3線索二叉樹的遍歷4、線索二叉樹464.1何謂線索二叉樹？為什么要線索？1）二叉樹的存儲結(jié)構(gòu)中沒有反映出某結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)是什么。2）二叉樹的二叉鏈表存儲結(jié)構(gòu)中的那些空指針域可利用。4.1何謂線索二叉樹？為什么要線索？1）二叉樹的存儲結(jié)構(gòu)中47ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA遍歷二叉樹的結(jié)果是，求得結(jié)點(diǎn)的一個(gè)線性序列。ABCDEFGHK例如:先序序列:中序序列:后序序列:遍歷二48ABCDEFGHK^

D^

C^^

B

E^指向該線性序列中的“前驅(qū)”和“后繼”的指針，稱作“線索”。包含“線索”的存儲結(jié)構(gòu)，稱作“線索鏈表”。加上線索的二叉樹，稱作“線索二叉樹”。ABCDEFGH49lchild

ltag

data

rtag

rchild0:lchild指向該結(jié)點(diǎn)的左孩子1:lchild指向該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)0:rchild指向該結(jié)點(diǎn)的右孩子1:rchild指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)ltag=rtag=4.2線索二叉樹的存儲結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)線索鏈表如此定義的二叉樹的存儲結(jié)構(gòu)稱作“線索鏈表”。lchildltagdatartagrchild050第六章--樹和二叉樹2課件51第六章--樹和二叉樹2課件52先序線索二叉樹：先序序列為：ABCD線索二叉樹畫法先序線索二叉樹：線索二叉樹畫法53中序線索二叉樹：中序序列為：BADC中序線索二叉樹：54后序線索二叉樹：后序序列為：BDCA后序線索二叉樹：555、樹、森林與二叉樹5.1樹的三種存儲結(jié)構(gòu)5.2樹、森林和二叉樹的轉(zhuǎn)換5、樹、森林與二叉樹565.1樹的三種存儲結(jié)構(gòu)一、雙親表示法二、孩子鏈表表示法三、樹的二叉鏈表(孩子-兄弟） 存儲表示法5.1樹的三種存儲結(jié)構(gòu)一、雙親表示法二、孩子鏈表表示法三、57ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5dataparent一、雙親表示法:ABCDEFG0A-1datapare58

typedefstructPTNode{Elemdata;

intparent;//雙親位置域

}

PTNode;

dataparent#defineMAX_TREE_SIZE100結(jié)點(diǎn)結(jié)構(gòu):C語言的類型描述:typedefstructPTNode{dat59typedefstruct{PTNodenodes[MAX_TREE_SIZE];

intr,n;//根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)

}

PTree;樹結(jié)構(gòu):typedefstruct{樹結(jié)構(gòu):60ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

4

datafirstchild123456二、孩子鏈表表示法:-1000224ABCDEFG0A-1datafir61typedefstructCTNode{

intchild;

structCTNode*next;

}*ChildPtr;孩子結(jié)點(diǎn)結(jié)構(gòu):

childnextC語言的類型描述:typedefstructCTNode{孩子結(jié)點(diǎn)結(jié)構(gòu):62

typedefstruct{Elemdata;ChildPtrfirstchild;//孩子鏈的頭指針

}

CTBox;雙親結(jié)點(diǎn)結(jié)構(gòu)

datafirstchildtypedefstruct{雙親結(jié)點(diǎn)結(jié)構(gòu)data63typedefstruct{CTBoxnodes[MAX_TREE_SIZE];

intn,r;//結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置

}

CTree;樹結(jié)構(gòu):typedefstruct{樹結(jié)構(gòu):64ABCDEFG

ABCEDFGroot

ABCEDFG

三、樹的二叉鏈表(孩子-兄弟）存儲表示法ABCDEFGAroot65typedefstructCSNode{Elemdata;

structCSNode

*firstchild,*nextsibling;}CSNode,*CSTree;C語言的類型描述:結(jié)點(diǎn)結(jié)構(gòu):

firstchilddatanextsiblingtypedefstructCSNode{C語言的類型描述665.2樹、森林和二叉樹的轉(zhuǎn)換樹和二叉樹之間的對應(yīng)關(guān)系

樹：兄弟關(guān)系二叉樹：雙親和右孩子樹：雙親和長子二叉樹：雙親和左孩子AEBCFDGABCDEFG5.2樹、森林和二叉樹的轉(zhuǎn)換樹和二叉樹之間的對應(yīng)關(guān)系A(chǔ)EB671.兄弟加線.樹轉(zhuǎn)換為二叉樹示例ABCDEFG1.兄弟加線.樹轉(zhuǎn)換為二叉樹示例ABCDEFG682.保留雙親與第一孩子連線,刪去與其他孩子的連線.ABCDEFG1.兄弟加線.樹轉(zhuǎn)換為二叉樹示例2.保留雙親與第一孩子連線,刪去與其他孩子的連線.ABCDE693.順時(shí)針轉(zhuǎn)動(dòng),使之層次分明.2.保留雙親與第一孩子連線,刪去與其他孩子的連線.1.兄弟加線.ABCDEFG樹轉(zhuǎn)換為二叉樹示例3.順時(shí)針轉(zhuǎn)動(dòng),使之層次分明.2.保留雙親與第一孩子連線,刪703.順時(shí)針轉(zhuǎn)動(dòng),使之層次分明.2.保留雙親與第一孩子連線,刪去與其他孩子的連線.1.兄弟加線.GDABECF樹轉(zhuǎn)換為二叉樹示例3.順時(shí)針轉(zhuǎn)動(dòng),使之層次分明.2.保留雙親與第一孩子連線,刪71樹轉(zhuǎn)換為二叉樹步驟⑴加線——樹中所有相鄰兄弟之間加一條連線。

⑵去線——對樹中的每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪去它與其它孩子結(jié)點(diǎn)之間的連線。

⑶層次調(diào)整——以根結(jié)點(diǎn)為軸心，將樹順時(shí)針轉(zhuǎn)動(dòng)一定的角度，使之層次分明。

樹轉(zhuǎn)換為二叉樹步驟⑴加線——樹中所有相鄰兄弟之間加一條連線72森林轉(zhuǎn)換為二叉樹步驟⑴將森林中的每棵樹轉(zhuǎn)換成二叉樹；⑵從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹連起來后，此時(shí)所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。森林轉(zhuǎn)換為二叉樹步驟⑴將森林中的每棵樹轉(zhuǎn)換成二叉樹；73二叉樹轉(zhuǎn)換為樹或森林步驟⑴加線——若某結(jié)點(diǎn)x是其雙親y的左孩子，則把結(jié)點(diǎn)x的右孩子、右孩子的右孩子、……，都與結(jié)點(diǎn)y用線連起來；⑵去線——?jiǎng)h去原二叉樹中所有的雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線；⑶

層次調(diào)整——整理由⑴、⑵兩步所得到的樹或森林，使之層次分明。

二叉樹轉(zhuǎn)換為樹或森林步驟⑴加線——若某結(jié)點(diǎn)x是其雙親y的74FHGEAICDBFHGDCEBAIFEDCBAHGI加線去線層次調(diào)整IHGBCDAFE二叉樹轉(zhuǎn)換為樹或森林示例FHGEAICDBFHGDCEBAIFEDCBAHGI加線去756、赫夫曼樹及其應(yīng)用6.1相關(guān)概念6.2如何構(gòu)造最優(yōu)二叉樹（赫夫曼樹）6.3赫夫曼樹應(yīng)用——赫夫曼編碼6、赫夫曼樹及其應(yīng)用6.1相關(guān)概念766.1相關(guān)概念葉子結(jié)點(diǎn)的權(quán)值：對葉子結(jié)點(diǎn)賦予的一個(gè)有意義的數(shù)值量。

二叉樹的帶權(quán)路徑長度：設(shè)二叉樹具有n個(gè)帶權(quán)值的葉子結(jié)點(diǎn)，從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的路徑長度與相應(yīng)葉子結(jié)點(diǎn)權(quán)值的乘積之和。記為：WPL=?=nkkklw1第k個(gè)葉子的權(quán)值；從根結(jié)點(diǎn)到第k個(gè)葉子的路徑長度最優(yōu)二叉樹（赫夫曼樹）：在所有含n個(gè)葉子結(jié)點(diǎn)、并帶相同權(quán)值的二叉樹中，必存在一棵其帶權(quán)路徑長度取最小值的二叉樹，稱為“最優(yōu)二叉樹”。6.1相關(guān)概念葉子結(jié)點(diǎn)的權(quán)值：對葉子結(jié)點(diǎn)賦予的一個(gè)有意義的7727975492WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=895427975492WPL(T)=778赫夫曼樹的特點(diǎn)：1.權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。2.只有度為0（葉子結(jié)點(diǎn)）和度為2（分支結(jié)點(diǎn)）的結(jié)點(diǎn)，不存在度為1的結(jié)點(diǎn).

2347WPL=32WPL=41WPL=3023477423赫夫曼樹的特點(diǎn)：2347WPL=32796.2如何構(gòu)造最優(yōu)樹赫夫曼算法基本思想：⑴初始化：由給定的n個(gè)權(quán)值{w1，w2，…，wn}構(gòu)造n棵只有一個(gè)根結(jié)點(diǎn)的二叉樹，從而得到一個(gè)二叉樹集合F＝{T1，T2