《數(shù)據(jù)結(jié)構(gòu)-C語(yǔ)言描述》樹(shù)

第六章

樹(shù)和二叉樹(shù)樹(shù)的概念與定義二

叉

樹(shù)二叉樹(shù)的遍歷與線索化樹(shù)和森林哈夫曼樹(shù)及其應(yīng)用樹(shù)的計(jì)數(shù)6.1樹(shù)的概念與定義樹(shù)的定義：樹(shù)(tree)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集T，當(dāng)n=0時(shí)，稱為空樹(shù)；當(dāng)n>0時(shí)，滿足以下條件：有且僅有一個(gè)結(jié)點(diǎn)被稱為樹(shù)根（root結(jié)點(diǎn)；當(dāng)n>1時(shí)，除根結(jié)點(diǎn)以外的其余n-1個(gè)結(jié)點(diǎn)可以劃分成m(m>0)個(gè)互不相交的有限集T1,T2,…，Tm，其中每一個(gè)集合本身又是一棵樹(shù)，稱為根的子樹(shù)(subtree)。圖6.1·結(jié)點(diǎn)(node)：表示樹(shù)中的元素，包括數(shù)據(jù)項(xiàng)及若干指向其子樹(shù)的分支?！そY(jié)點(diǎn)的度(degree)：結(jié)點(diǎn)擁有的子樹(shù)的數(shù)目。圖6.1中結(jié)點(diǎn)A的度為3?！と~子(leaf)：度為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。圖6.1中，葉子結(jié)點(diǎn)有：K，L，F(xiàn)，G，M，I，J?！し种ЫY(jié)點(diǎn)：度不為0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。圖6.1中，非終端結(jié)點(diǎn)有：A，B，C，D等?！ず⒆咏Y(jié)點(diǎn)(child)：結(jié)點(diǎn)的子樹(shù)的根稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。圖6.1中，結(jié)點(diǎn)A的孩子結(jié)點(diǎn)為B，C，D，結(jié)點(diǎn)B的孩子結(jié)點(diǎn)為E，F(xiàn)。·雙親結(jié)點(diǎn)(parents)：孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)稱為該結(jié)點(diǎn)的雙親結(jié)點(diǎn)。圖6.1中，結(jié)點(diǎn)I的雙親為D，結(jié)點(diǎn)L的雙親為

E。·兄弟結(jié)點(diǎn)(sibling)：具有同一雙親結(jié)點(diǎn)的孩子結(jié)點(diǎn)之間互稱為兄弟結(jié)點(diǎn)。圖6.1中，結(jié)點(diǎn)B，C，D互為兄弟，結(jié)點(diǎn)K，L互為兄弟。·樹(shù)的度：樹(shù)中最大的結(jié)點(diǎn)的度數(shù)即為樹(shù)的度。圖6.1中的樹(shù)的度為3?！そY(jié)點(diǎn)的層次(level)：從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層……。若某結(jié)點(diǎn)在第l層，則其孩子結(jié)點(diǎn)就在

第l+1層。圖6.1中，結(jié)點(diǎn)A的層次為1，結(jié)點(diǎn)M的層次為4?！?shù)的高度(depth)：樹(shù)中結(jié)點(diǎn)的最大層次數(shù)。圖6.1中的樹(shù)的高度為4?！ど?forest)：m(m≥0)棵互不相交的樹(shù)的集合?！び行驑?shù)與無(wú)序樹(shù)：樹(shù)中結(jié)點(diǎn)的各子樹(shù)從左至右是有次序的（不能互換）則稱該樹(shù)為有序樹(shù)，否則稱該樹(shù)為無(wú)序樹(shù)。6.2

二叉樹(shù)二叉樹(shù)的定義：二叉樹(shù)是由n(n≥0)個(gè)結(jié)點(diǎn)的有限集T構(gòu)成，此集合或者為空集，或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的左右子樹(shù)組成，并且左右子樹(shù)都是二叉樹(shù)。注意：二叉樹(shù)的子樹(shù)有左右之分，因此二叉樹(shù)是一種有序樹(shù)。二叉樹(shù)的性質(zhì)：性質(zhì)1

在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i≥1)。性質(zhì)2

深度為k的二叉樹(shù)至多有2k－1個(gè)結(jié)點(diǎn)（k>=1）。性質(zhì)3

對(duì)任意一棵二叉樹(shù)BT，如果其葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0＝n2＋1。性質(zhì)4

具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為【log2n】＋1。（符號(hào)【x】表示不大于x的最大整數(shù)。）二叉樹(shù)的性質(zhì)：性質(zhì)5

對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)如果對(duì)其結(jié)點(diǎn)按層次編號(hào)，則對(duì)任一結(jié)點(diǎn)

i(1≤i≤n)，有：(1)如果i=1，則結(jié)點(diǎn)i是二叉樹(shù)的根，無(wú)親；如果i>1，則其雙親是【i/2】(2)

如果2i>n，則結(jié)點(diǎn)i無(wú)左孩子；如果2in，則其左孩子是2i(3)

如果2i+1>n，則結(jié)點(diǎn)i無(wú)右孩子；如果

2i+1≤n，則其右孩子是2i+1滿二叉樹(shù)：一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱為滿二叉樹(shù)。完全二叉樹(shù)：深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為完全二叉樹(shù)。12345896710

11

12

13

14

1512345896710

11

121234567123456二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)·

順序存儲(chǔ)結(jié)構(gòu)

:為了能夠反映出結(jié)點(diǎn)之間的邏輯關(guān)系，必須將它“修補(bǔ)”成完全二叉樹(shù)，對(duì)應(yīng)該完全二叉樹(shù)，可以開(kāi)辟長(zhǎng)度為12的數(shù)組，對(duì)12個(gè)數(shù)據(jù)元素進(jìn)行存儲(chǔ)，原二叉樹(shù)中空缺的結(jié)點(diǎn)在數(shù)組中的相應(yīng)單元必須置空a

b

c

d

e

φ

φ

φ

φ

f

g二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)·

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

:表示二叉樹(shù)的鏈表中的結(jié)點(diǎn)應(yīng)該包含3個(gè)域：數(shù)據(jù)域和指向左、右子樹(shù)的指針域，二叉樹(shù)的這種存儲(chǔ)結(jié)構(gòu)被稱為二叉鏈表。Lchild

data

rchild在n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指針域6.3

二叉樹(shù)的遍歷與線索化二叉樹(shù)的遍歷：是按某條搜索路徑訪問(wèn)樹(shù)中的每一個(gè)結(jié)點(diǎn)，使得每一個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅被訪問(wèn)一次。先根遍歷二叉樹(shù)（1）訪問(wèn)根結(jié)點(diǎn)；（2）先根遍歷左子樹(shù)；（3）先根遍歷右子樹(shù)。中根遍歷二叉樹(shù)·（1）中根遍歷左子樹(shù)；·（2）訪問(wèn)根結(jié)點(diǎn)；·（3）中根遍歷右子樹(shù)。后根遍歷二叉樹(shù)·（1）后根遍歷左子樹(shù)；·（2）后根遍歷右子樹(shù)；·（3）訪問(wèn)根結(jié)點(diǎn)。先根遍歷:

-+a*b–cd/ef中根遍歷:

a+b*c–d–e/f后根遍歷:

abcd-*+ef/-typedef

struct

Node{datatype

data;struct

Node

*Lchild;struct

Node

*Rchild;}

BTnode,*Btree;·先根遍歷算法void

preorder(Btree

root){if(root!=NULL){Visit(root->data);preorder(root->Lchild);preorder(root->Rchild);}}·中根遍歷算法void InOrder(Btree

root){if(root!=NULL){InOrder(root->Lchild);Visit(root->data);InOrder(root->Rchild);}}·后根遍歷算法void PostOrder(Btree

root){if(root!=NULL){PostOrder(root->Lchild);PostOrder(root->Rchild);Visit(root

->data);}}線索二叉樹(shù)：利用二插鏈表剩余的n+1個(gè)空指針域來(lái)存放遍歷過(guò)程中結(jié)點(diǎn)的前驅(qū)和后繼的指針，這種附加的指針?lè)Q為“線索”，加上了線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹(shù)稱為線索二叉樹(shù)。為了區(qū)分結(jié)點(diǎn)的指針域是指向其孩子的指針，還是指向其前驅(qū)或后繼的線索，可在二叉鏈表的結(jié)點(diǎn)中,再增設(shè)2個(gè)標(biāo)志域。Lchild

Ltag

Data

Rtag

RchildLchild域指示結(jié)點(diǎn)的左孩子Ltag=Lchild域指示結(jié)點(diǎn)的遍歷前驅(qū)Rchild域指示結(jié)點(diǎn)的右孩子Rtag=Rchild域指示結(jié)點(diǎn)的遍歷后繼中序線索二叉樹(shù)·

基于遍歷的應(yīng)用與線索二叉樹(shù)的應(yīng)用二叉樹(shù)的遍歷是對(duì)二叉樹(shù)進(jìn)行各種運(yùn)算的一個(gè)重要基礎(chǔ)，對(duì)訪問(wèn)（程序中的visit函數(shù)）結(jié)點(diǎn)可理解為各種對(duì)二叉樹(shù)中結(jié)點(diǎn)進(jìn)行操作。因此，只要將二叉樹(shù)三種遍歷算法中的visit函數(shù)具體化，就產(chǎn)生了基于二叉樹(shù)的不同應(yīng)用?！?/p>

輸出二叉樹(shù)中的結(jié)點(diǎn)Void

paintnode

(Btree

root){if

(root!=NULL){printf

(root

->data);paintnode

(root

->Lchild);paintnode

(root

->Rchild);}}·

輸出二叉樹(shù)中的葉子結(jié)點(diǎn)Void

paintleaf

(Btree

root){if

(root!=NULL){if

(root

->Lchild==NULL

&&

root

->Rchild==NULL)printf

(root

->data);paintleaf

(root

->Lchild);paintleaf

(root

->Rchild);}}·

統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)目Void

leafcount(Btree

root){if(root!=NULL){leafcount(root->Lchild);leafcount(root->Rchild);if

(root

->Lchild==NULL

&&

root

->Rchild==NULL)count++;}}提示：count為全局變量，在主函數(shù)中定義。·

建立二叉樹(shù)圖中二叉樹(shù)的先根遍歷序列為：

ABDGCEHF，而考慮空子樹(shù)后的先根遍歷序列應(yīng)為：ABD．G．CE．HF，其中“．”代表空子樹(shù)。如果已知二叉樹(shù)的考慮了空子樹(shù)后的遍歷序列，那么建立這棵二叉樹(shù)的算法如下(假定datatype類型為char)Void

CreateBtree(Btree

*bt){char

ch;ch=getchar();if(ch==".")*bt=NULL;else{*bt=(Btree)malloc(sizeof(BTnode));(*bt)->data=ch;CreateBiTree(&((*bt)->Lchild));CreateBiTree(&((*bt)->Rchild));}}·

求二叉樹(shù)的高度采用遞歸的方法定義二叉樹(shù)的高度：若二叉樹(shù)為空，則高度為0；若二叉樹(shù)非空，其高度應(yīng)為其左右子樹(shù)高度的最大值加1。int

TreeDepth(Btree

bt){int

hl,hr,max;if(bt!=NULL){hl=TreeDepth(bt->Lchild);hr=TreeDepth(bt->Rchild);max=(hl，hr);return(max+1);}else

return(0);}·

在中根遍歷的線索樹(shù)中查找前驅(qū)結(jié)點(diǎn)對(duì)于二叉樹(shù)中任意結(jié)點(diǎn)p，要找其前驅(qū)結(jié)點(diǎn),當(dāng)p->Ltag=1時(shí)，p->Lchild即為p的前驅(qū)結(jié)點(diǎn)；當(dāng)p->Ltag=0時(shí)，說(shuō)明

p有左子樹(shù)，此時(shí)p的中根遍歷下的前驅(qū)結(jié)點(diǎn)即為其左子右鏈下的最后一個(gè)結(jié)點(diǎn)。Void

Previous(ThreadTnode

*

p,

ThreadTnode

*pre){

ThreadTnode

*q;if(p->Ltag==1)

pre=

p->Lchild;else{for(q=

p->Lchild;q->Rtag==0;q=q->Rchild);pre=q;}}·

在中根遍歷的線索樹(shù)中查找后繼結(jié)點(diǎn)二叉樹(shù)中任意結(jié)點(diǎn)p，若要找其后繼結(jié)點(diǎn)，當(dāng)p->Rtag=1時(shí)，p->Rchild即為p的后繼結(jié)點(diǎn)；當(dāng)p->Rtag=0時(shí)，說(shuō)明

p有右子樹(shù)，此時(shí)p的中根遍歷下的后繼結(jié)點(diǎn)即為其右子左鏈下的最后一個(gè)結(jié)點(diǎn)。Void

Succedent(ThreadTnode

*p,

ThreadTnode

*succ){

ThreadTnode

*q;if

(p->Rtag==1)succ=

p->

RChild;else{for(q=

p->RChild;

q->Ltag==0

;q=q->LChild

);succ=q;}}6.4

樹(shù)和森林·樹(shù)的存儲(chǔ)結(jié)構(gòu)雙親（鏈表）表示法用一組連續(xù)的存儲(chǔ)空間（數(shù)組）來(lái)存儲(chǔ)樹(shù)中的結(jié)點(diǎn)，每個(gè)組元素中不但包含結(jié)點(diǎn)本身的信息，還保存該結(jié)點(diǎn)雙親結(jié)點(diǎn)在數(shù)組中的下標(biāo)號(hào)。數(shù)組中每個(gè)結(jié)點(diǎn)含兩個(gè)域：數(shù)據(jù)域：存放結(jié)點(diǎn)本身信息雙親域：指示本結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中位置在雙親表示法下，樹(shù)的數(shù)據(jù)類型定義如下：

#define

Maxsize

50typedef

struct

Node{DataType

data;int

parent;}Tnode;Tnode

Ptree[Maxsize];abcdefhgidataparent0a－11b12c13d24e25f36g57h58i5如何找孩子結(jié)點(diǎn)·孩子鏈表表示法把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來(lái)，構(gòu)成一個(gè)單鏈表，該鏈表就是本結(jié)點(diǎn)的孩子鏈表。具有n個(gè)結(jié)點(diǎn)的樹(shù)就形成了個(gè)孩子鏈表·孩子結(jié)點(diǎn)·#define

Maxsize

50typedef

struct

ChildNode{int

Child;struct

ChildNode

*

next;}ChildNode;·表頭結(jié)點(diǎn)typedef

struct{DataType

data;ChildNode

*

ChildHead

;}DataNode;·孩子鏈表·DataNode

Ctree[Maxsize];·

孩子兄弟鏈表表示法又稱為二叉鏈表表示法，即以二叉鏈表作為樹(shù)的存儲(chǔ)結(jié)構(gòu)。鏈表中每個(gè)結(jié)點(diǎn)設(shè)有兩個(gè)鏈域，與二叉樹(shù)的二叉鏈表表示法所不同是，這兩個(gè)鏈域分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟（右兄弟）。dataNextsiblingFirstChildtypedef

struct

CSNode{DataType

data;Struct

CSNode

*FirstChild,

*Nextsibling;}

*CSTree;對(duì)應(yīng)結(jié)論：樹(shù)的孩子兄弟鏈表表示法與對(duì)應(yīng)二叉樹(shù)的二插鏈表表示法相同。因此，上圖中的樹(shù)與二叉樹(shù)之間存在相互轉(zhuǎn)換的關(guān)系。BEFGDA

AC

D

B

CH

I

E

F

GHIABCDEFGHIABCDEABCDEFGHIF

G

H

I樹(shù)轉(zhuǎn)換成的二叉樹(shù)其右子樹(shù)一定為空·樹(shù)轉(zhuǎn)換為二叉樹(shù)加線：在樹(shù)中所有相鄰的兄弟之間加一連線；抹線：對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)，除了其左孩子外抹去該結(jié)點(diǎn)與其孩子之間的連線。整理：以樹(shù)的根結(jié)點(diǎn)為軸心，將整樹(shù)順時(shí)針轉(zhuǎn)45°?！ど洲D(zhuǎn)換成二叉樹(shù)·將各棵樹(shù)分別轉(zhuǎn)換成二叉樹(shù)將每棵樹(shù)的根結(jié)點(diǎn)用線相連以第一棵樹(shù)根結(jié)點(diǎn)為二叉樹(shù)的根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，構(gòu)成二叉樹(shù)型結(jié)構(gòu)ABCDFE

GHIJBCDEFA

GHIJABCDEFGHIJABCDEFGHIJ·二叉樹(shù)轉(zhuǎn)換成樹(shù)·加線：若p結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則將p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都與p的雙親用線連起來(lái)·抹線：抹掉原二叉樹(shù)中雙親與右孩子之間的連線·調(diào)整：將結(jié)點(diǎn)按層次排列，形成樹(shù)結(jié)構(gòu)EGHIA

ACDB

BC

EF

D

FGHIEGHIA

ACDB

BC

EF

D

FGHIABCDEFGHI·二叉樹(shù)轉(zhuǎn)換成森林·

抹線：將二叉樹(shù)中根結(jié)點(diǎn)與其右孩子連線，及沿右分支·搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二樹(shù)·還原：將孤立的二叉樹(shù)還原成樹(shù)ABCDEFGHIJABCDEFGHIJBCDEFA

GHIJABCDEFGHIJ·樹(shù)和森林的遍歷樹(shù)的遍歷先根遍歷若樹(shù)非空，則遍歷方法為：a.訪問(wèn)根結(jié)點(diǎn)。b.從左到右，依次先根遍歷根結(jié)點(diǎn)的每一棵子樹(shù)。后根遍歷若樹(shù)非空，則遍歷方法為：a.從左到右，依次后根遍歷根結(jié)點(diǎn)的每一棵子樹(shù)。b.訪問(wèn)根結(jié)點(diǎn)。按層次遍歷若樹(shù)非空，則遍歷方法為：先訪問(wèn)第一層上的結(jié)點(diǎn)，然后依次遍歷第二層，……第n層的結(jié)點(diǎn)。ABCDEFGHIJ

K

L

MNO先根遍歷：A

B

E

F

I

G

C

D

H

J

K

L

N

O

M后根遍歷：E

IF

G

B

C

JK

N

O

L

M

H

D

A層次遍歷：A

B

C

D

E

F

G

H

I

J

K

L

M

N

O·森林的遍歷·先根遍歷·若森林非空，則遍歷方法為：a.訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)。b.先根遍歷第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林。c.先根遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。·中根遍歷若森林非空，則遍歷方法為：·a.中根遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林?！.訪問(wèn)第一棵樹(shù)的根結(jié)點(diǎn)。c.中根遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林?！ず蟾闅v·若森林非空，則遍歷方法為：a.后根遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林。b.后根遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。c.訪問(wèn)第一棵樹(shù)的根結(jié)點(diǎn)。先根遍歷：ABCDEFGHIJ中根遍歷：BCDAFEHJIG后根遍歷：DCBFJIHGEA6.5

哈夫曼樹(shù)及其應(yīng)用與哈夫曼樹(shù)相關(guān)的基本概念路徑和路徑長(zhǎng)度路徑：從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支序列。路徑長(zhǎng)度：是指從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)所經(jīng)過(guò)的分支數(shù)目。結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長(zhǎng)度結(jié)點(diǎn)的權(quán)：在實(shí)際的應(yīng)用中，人們常常給樹(shù)的每個(gè)結(jié)點(diǎn)賦予一個(gè)具有某種實(shí)際意義的數(shù)值，我們稱該數(shù)值為這個(gè)結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：從樹(shù)根到某一結(jié)點(diǎn)的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積，叫做該結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度。樹(shù)的帶權(quán)路徑長(zhǎng)度樹(shù)的帶權(quán)路徑長(zhǎng)度是指樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)之和?！?shù)的帶權(quán)路徑長(zhǎng)度樹(shù)的帶權(quán)路徑長(zhǎng)度是指樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和?！す蚵鼧?shù)哈夫曼樹(shù)：是由n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹(shù)中帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹(shù)。哈夫曼樹(shù)又叫最佳判定樹(shù)。例：有4個(gè)結(jié)點(diǎn)，權(quán)值分別為7，5，2，4，構(gòu)造有4個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)ab

cd7

5

2

4WPL=7*2+5*2+2*2+4*2=36dcb2a745WPL=7*3+5*3+2*1+4*2=46abc

d752

4WPL=7*1+5*2+2*3+4*3=35·構(gòu)造Huffman樹(shù)的方法——Huffman算法·

構(gòu)造Huffman樹(shù)步驟根據(jù)給定的n個(gè)權(quán)值{w1,w2,……wn}，構(gòu)造n棵只有根結(jié)點(diǎn)的二叉樹(shù)，令起權(quán)值為wj在森林中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作左右子樹(shù)，構(gòu)造一棵新的二叉樹(shù)，置新二叉樹(shù)根結(jié)點(diǎn)權(quán)值為其左右子樹(shù)根結(jié)點(diǎn)權(quán)值之和在森林中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入森林中重復(fù)上述兩步，直到只含一棵樹(shù)為止，這棵樹(shù)即哈夫曼樹(shù)例7

5

2

4a

b

c

d7a5b2

4c

d67a5b2

4c

d6117a5b2

4c

d61118例w={5,29,7,8,14,23,3,11}5

2929

733

118157

829

145

378142381423115231181181929

14

23

157

8115

3829

23

1914157

85

32929147

829115

381915

234211819234214157

829

2958115

381923422914157

829585

3100·

哈夫曼樹(shù)的應(yīng)用·

最佳判定樹(shù)·

學(xué)生成績(jī)的分布呈正態(tài)分布即：中等成績(jī)的學(xué)生較多，而較好或較差學(xué)生均比較少。設(shè)其分布規(guī)律如下表：等級(jí)不及格及格中等良好優(yōu)秀分?jǐn)?shù)段0~5960~6970~7980~8990~100比例5％15％40％30％10％（a）（b）若采用圖（a）來(lái)進(jìn)行判斷，則80%以上的數(shù)據(jù)要進(jìn)行三次或三次以上的比較才能得到結(jié)果。而如果我們以各分?jǐn)?shù)段人數(shù)的占總?cè)藬?shù)的比例5、15、40、30、10為權(quán)值構(gòu)造哈夫曼樹(shù)，可得到（b）所示的判定樹(shù)來(lái)進(jìn)行判斷可以使大部分?jǐn)?shù)據(jù)經(jīng)過(guò)較少次數(shù)的比較得到結(jié)果。·

哈夫曼編碼哈夫曼樹(shù)還被廣泛的應(yīng)用在編碼技術(shù)中。利用哈夫曼樹(shù)，我們可以得到平均長(zhǎng)度最短的編碼。設(shè)有一臺(tái)模型機(jī)，共有7種不同的指令，其使用頻率如下：為了充分地利用編碼信息和減少程序的總位數(shù)，我們考慮采用變長(zhǎng)編碼。如果對(duì)每一條指令指定一條編碼，使得這些編碼互不相同且最短。若要設(shè)計(jì)變長(zhǎng)的編碼，這種編碼必須滿足這樣一個(gè)條件：任意一個(gè)編碼不能成為其它任意編碼的前綴。我們把滿足這個(gè)條件的編碼叫做前綴編碼。利用哈夫曼算法，可以設(shè)計(jì)出最優(yōu)的前綴編碼。以每條指令的使用頻率為權(quán)值構(gòu)造哈夫曼樹(shù)，構(gòu)造結(jié)果如圖所示：·哈夫曼編碼算法的實(shí)現(xiàn)數(shù)據(jù)類型的定義如下：typedef

struct

Node{int

weight

;int

parent,

LChild,RChild

;}

HTNode,

*

HTree;typedef

char

*

*HuffmanCode

;創(chuàng)建哈夫曼樹(shù)并求哈夫曼編碼的算法如下：viod

CreatHTree(HTree

*ht

,

HuffmanCode

*hc,int

*

w,int

n){/*w存放n個(gè)權(quán)值,構(gòu)造哈夫曼樹(shù)ht,并求出哈夫曼編碼hc

*/int

start;m=2*n-1;*ht=(HTree)malloc((m+1)*sizeof(HTNode));for(i=1;i<=n;i++)(*ht)[i]

={

w[i],0,0,0};for(i=n+1;i<=m;i++)(*

ht)[i]={0,0,0,0};/*初始化*/for(i=n+1;i<=m;i++){select(ht,i-1,&s1,&s2);/*在(*ht)[1]~(*ht)[i-1]的范圍內(nèi)選擇兩個(gè)parent為0且weight最小的結(jié)點(diǎn)，其序號(hào)分別賦值給s1、s2返回，select函數(shù)要求在上機(jī)調(diào)試使補(bǔ)充定義*/(*ht)[s1].parent=i;(*ht)[s2].parent=i;