《數(shù)據(jù)結(jié)構(gòu)用c語言描述》第六章.j

第六章樹和二叉樹樹的概念和基本術(shù)語二叉樹二叉樹遍歷二叉樹的計數(shù)樹與森林哈夫曼樹第一頁，共八十五頁。樹的概念和基本術(shù)語樹的定義樹是由n(n0)個結(jié)點的有限集合。如果n=0，稱為空樹；如果n>0，則有且僅有一個特定的稱之為根(Root)的結(jié)點，它只有直接后繼，但沒有直接前驅(qū)；當n>1，除根以外的其它結(jié)點劃分為m(m>0)個互不相交的有限集T1,T2

,…,Tm，其中每個集合本身又是一棵樹，并且稱為根的子樹

(SubTree)。第二頁，共八十五頁。ABDKL例如A只有根結(jié)點的樹CE

F

G

H

I

JM有13個結(jié)點的樹其中：A是根；其余結(jié)點分成三個互不相交的子集，T1={B,E,F,K,L}；

T2={C,G}；

T3={D,H,I,J,M},T1,T2,T3都是根A的子樹，且本身也是一棵樹第三頁，共八十五頁。樹的基本術(shù)語1層2層4層3層height=

4ACBDE

FMG

H

I

JK

L·

結(jié)點·

結(jié)點的度

·

子女

·

祖先·

葉結(jié)點

·

雙親

·

子孫·

分支結(jié)點

·

兄弟

·

結(jié)點層次·

樹的深度·

樹的度·

森林第四頁，共八十五頁。二叉樹(Binary

Tree)定義五種形態(tài)一棵二叉樹是結(jié)點的一個有限集合，該集合或者為空，或者是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。LLRR特點每個結(jié)點至多只有兩棵子樹（二叉樹中不存在度大于2的結(jié)點）第五頁，共八十五頁。性質(zhì)1

在二叉樹的第

i

層上至多有

2i

－1個結(jié)點。(i

1)

[證明用歸納法]證明：當i=1時，只有根結(jié)點，2

i-1=2

0=1。假設對所有j，i>j

1，命題成立，即第j層上至多有2

j-1

個結(jié)點。由歸納假設第i-1

層上至多有2i－2個結(jié)點。由于二叉樹的每個結(jié)點的度至多為2，故在第i層上的最大結(jié)點數(shù)為第i-1層上的最大結(jié)點數(shù)的2倍，即2*2i－2=2

i-1。性質(zhì)第六頁，共八十五頁。性質(zhì)2

深度為k

的二叉樹至多有

2

k-1個結(jié)點(k 1)。證明：由性質(zhì)1可見，深度為k的二叉樹的最大結(jié)點數(shù)為＝20

+

21

+

…

+

2

k-1

=

2

k-1＝第七頁，共八十五頁。性質(zhì)3

對任何一棵二叉樹T,

如果其葉結(jié)點數(shù)為n0,度為2的結(jié)點數(shù)為n2,則n0＝n2＋1.證明：若度為1的結(jié)點有n1

個，總結(jié)點個數(shù)為n，總邊數(shù)為e，則根據(jù)二叉樹的定義，n

=

n0

+

n1

+

n2

e

=

2n2

+

n1

=

n

-

1因此，有

2n2

+

n1

=

n0

+

n1

+

n2

-

1n2

=

n0

-

1

n0

=

n2

+

1第八頁，共八十五頁。兩種特殊形態(tài)的二叉樹62定義1

滿二叉樹(Full

Binary

Tree)一棵深度為k且有2

k-1個結(jié)點的二叉樹稱為滿二叉樹。175438

9

10

11

12

13

14

15滿二叉樹第九頁，共八十五頁。2154367216543非完全二叉樹定義2

完全二叉樹(Complete

Binary

Tree)若設二叉樹的高度為h，則共有h層。除第h層外，其它各層(0h-1)的結(jié)點數(shù)都達到最大個62數(shù)，第h層從右向左連續(xù)缺若干結(jié)點，這就是完全二叉樹。175438

9

10

11

12完全二叉樹第十頁，共八十五頁。性質(zhì)4

具有n

(n度為

log2(n)0)個結(jié)點的完全二叉樹的深＋1證明：設完全二叉樹的深度為h，則根據(jù)性質(zhì)2和完全二叉樹的定義有2h－1

-

1

<

n

2h-

1或

2h－1

n

<

2h取對數(shù)h－1<log2n因此有h

=

log2(n)h，又h是整數(shù)，＋1第十一頁，共八十五頁。性質(zhì)5

如將一棵有n個結(jié)點的完全二叉樹自頂向下，同一層自左向右連續(xù)給結(jié)點編號1,2,…,n，則有以下關(guān)系：若i=1,則i無雙親若i

>

0,

則i

的雙親為

i

/2若2*i<=n,則i的左子女為2*i，若2*i+1<=n,則i的右子女為2*i+1■若結(jié)點編號i為奇數(shù)，且i!=1,則左兄弟結(jié)點i-1.■若結(jié)點編號i為偶數(shù)，且小于n,則右兄弟結(jié)點為i+1.■結(jié)點i

所在層次為

log2(i+1十二頁，共八十五頁。完全二叉樹的順序表示二叉樹的存儲結(jié)構(gòu)1

2

3

4

5

6

7

8

9101

2

3

4

0

5

6

7

8

0

0

910一般二叉樹的順序表示89

104

5

6

712365478

9·順序表示12

3190第十三頁，共八十五頁?！ゆ湵肀硎綿atalChildrChild二叉鏈表lChild

data

rChild含兩個指針域的結(jié)點結(jié)構(gòu)lChild

data

parent

rChild含三個指針域的結(jié)點結(jié)構(gòu)parentdatalChildrChild三叉鏈表第十四頁，共八十五頁。二叉樹鏈表表示的示例AAABBBCCC

DDDFFE

FEErootrootroot二叉樹二叉鏈表三叉鏈表第十五頁，共八十五頁。三叉鏈表的靜態(tài)結(jié)構(gòu)ABC

DE

Frootdataparentlchildrchi0A-11-11B0232C1-1-13D1454

E5

F33-1-1-1-1第十六頁，共八十五頁。typedef

char

datatype;//結(jié)點數(shù)據(jù)類型//結(jié)點定義typedef

struct

node

{datatype

data;struct

node

*

lChild,

*

rchild;}

bitree;typedef

bitree *

bitree;//根指針二叉鏈表的定義第十七頁，共八十五頁。介紹按完全二叉樹的層次順序，依次輸入結(jié)點信息建立二叉樹的算法。算法的基本思想：1、依次輸入結(jié)點信息，若輸入的結(jié)點不是虛結(jié)點，則建立一個新結(jié)點。2、若新結(jié)點是第一個結(jié)點，則令其為根結(jié)點；否則作為孩子連接到其雙親結(jié)點上。3、重復上述過程，至到輸入結(jié)束信息為止。二叉樹的生成第十八頁，共八十五頁。為此，設置一個指針類型的數(shù)組隊列，保存已輸入結(jié)點的地址。1、先輸入的結(jié)點的孩子必定比后輸入的結(jié)點的孩子先進隊列，因此可利用隊頭指針front指向當前必須與其孩子結(jié)點建立連接的雙親結(jié)點，利用隊尾指針rear指向當前輸入的結(jié)點。2、若rear為偶數(shù)，作為左孩子與雙親連接，否則作為右孩子與雙親連接。3、若雙親結(jié)點或孩子結(jié)點為虛結(jié)點，則無須連接。4、若雙親結(jié)點與其兩個孩子連接完畢，則做出隊操作，使頭指針指向下一個等待連接的雙親結(jié)點。第十九頁，共八十五頁。bitree

*Q[maxsize];bitree

*CREATREE(

){

char

ch

;

int

front

,

rear

;bitree

*root

,

*s

;root

=

null

; front

=

1

;

rear

=

0

;ch

=

getchar(

)

;while

(

ch

!=

‘

#

’

){

s

=

null

;if

(

ch

!=

‘

@

’

){

s

=

malloc(sizeof(bitree));s.data

=

ch

;

s.lchild

=

null

;s,rchild

=null;}第二十頁，共八十五頁。rear

+

+

;

Q[rear]

=

s

;if

(rear

==

1

)

root

=

s

;else{

if

(

s

&&

Q[front]

)if

(rear%2==0

)

Q[front].lchild

=

s

;else Q[front].rchild

=

s

;front

+

+

;if

(

rear%2==1

)}ch

=

getchar

(

)

;}return

root

;}第二十一頁，共八十五頁。二叉樹遍歷樹的遍歷就是按某種次序訪問樹中的結(jié)點，要求每個結(jié)點訪問一次且僅訪問一次。設訪問根結(jié)點記作D

遍歷根的左子樹記作L遍歷根的右子樹記作R則可能的遍歷次序有前序

DLR中序

LDR后序

LRDDLR第二十二頁，共八十五頁?！?/p>

中序遍歷二叉樹算法的定義：若二叉樹為空，則空操作；否則中序遍歷左子樹(L)；訪問根結(jié)點(D)；中序遍歷右子樹(R)。遍歷結(jié)果a

+

b

*

c

-

d

-

e

/

f中序遍歷(Inorder

Traversal)--/+*abcdef第二十三頁，共八十五頁。void

InOrder

(

bitree

*t){if

(

t

!=

NULL

){InOrder

(

t->lchild

);printf(“\t%c\n”,

t->data);InOrder

(

t->rchild

);}}·中序遍歷二叉樹的遞歸算法第二十四頁，共八十五頁。訪問根結(jié)點(D)；前序遍歷左子樹(L)；前序遍歷右子樹(R)。遍歷結(jié)果-

+

a

*

b

-

c

d

/

e

f前序遍歷(Preorder

Traversal)·

前序遍歷二叉樹算法的定義：若二叉樹為空，則空操作；否則--/+*abcdef第二十五頁，共八十五頁?！で靶虮闅v二叉樹的遞歸算法voidPreOrder

(

bitree

*t

){if

(

t

!=

NULL

){printf(“\t%c\n”,t->data);PreOrder

(

t->lchild

);PreOrder

(

t->rchild

);}}第二十六頁，共八十五頁。后序遍歷右子樹(R)；訪問根結(jié)點(D)。遍歷結(jié)果a

b

c

d

-

*

+

e

f

/

-后序遍歷(Postorder

Traversal)·

后序遍歷二叉樹算法的定義：若二叉樹為空，則空操作；否則后序遍歷左子樹(L)；--/+*abcdef第二十七頁，共八十五頁?！ず笮虮闅v二叉樹的遞歸算法：void

PostOrder

(

bitree

*

t

){if

(

t!=NULL

){PostOrder

(

t->lchild

);PostOrder

(

t->rchild

);printf(“\t%c\n”,t->data);}}第二十八頁，共八十五頁。int

Count

(

bitree

*T

){if

(

T

==

NULL

)

return

0;elsereturn1

+

Count

(

T->lchild

)+

Count

(

T->rchild

);}1.

計算二叉樹結(jié)點個數(shù)(遞歸算法)第二十九頁，共八十五頁。int

Leaf_Count(Bitree

*T){//求二叉樹中葉子結(jié)點的數(shù)目if(!T)

return

0;

//空樹沒有葉子else

if(!T->lchild&&!T->rchild)return

1;

//葉子結(jié)點else

returnLeaf_Count(T.lchild)+Leaf_Count(T.rchild);左子樹的葉子數(shù)加上右子樹的葉子數(shù)}2.

求二叉樹中葉子結(jié)點的個數(shù)第三十頁，共八十五頁。int

Height

(

bitree

*

T

){

int

m,

n

;if

(

T

==

NULL

)

return

-1;else{

m

=

Height

(

T->lchild

);n

=

Height

(

T->rchild

);return

(m

>

n)

?

m+1

:

n+1;}}3.

求二叉樹高度(遞歸算法)第三十一頁，共八十五頁。4.

復制二叉樹(遞歸算法)int

Copy(

bitree

*

T

){

if

(

T

==

NULL

)

return

-1;bitree

*

temp;Temp->data=T->data;Temp->

lchild

=

Copy(

T->lchild

);Temp->

rchild

=Copy(T->rchild

);return

temp;}第三十二頁，共八十五頁。5.

判斷二叉樹等價(遞歸算法)int

Equal(

bitree

*a,

bitree

*b){

if

(

a

==

NULL

&&

b

==

NULL

)return

1

;if

(

a

!==

NULL

&&

b

!==

NULL&&

a->data==b->data&&

equal(

a->lchild,

b->lchild)&&

equal(

a->rchild,

b->rchild))return

1;else

return

0;//a和b的子樹不等同}第三十三頁，共八十五頁。中序遍歷二叉樹(非遞歸算法)用棧實現(xiàn)baabcdeadaa

b入棧b退棧訪問d入棧ad退棧訪問?？誥退棧訪問ecc

e

入棧c

退棧訪問ce

退棧訪問第三十四頁，共八十五頁。void

InOrder

(

bitree

*T

){

stack

*S;

SETNULL(

S

);//遞歸工作棧bitree

*p

=

T;//初始化while

(

p

!=

NULL

||

!Empty(S)

){

if(

p

!=

NULL

){

Push(S,

p);

p

=

p->lchild;

}if

(

!Empty(S)

){

Pop(S,

p);//棧非空//退棧//訪問根printf(“%c\n”,

p->data

);p

=

p->rchild;}//if}//whilereturn

ok;}abcde第三十五頁，共八十五頁。前序遍歷二叉樹(非遞歸算法)用棧實現(xiàn)caabcdedcc訪問a進棧c

左進

b訪問

退棧

退棧b

d

c進棧

訪問

訪問d

d

c

左進

左進 左進空

空 e訪問

e

左進空退棧結(jié)束第三十六頁，共八十五頁。void

PreOrder(

bitree

*T

){

stack

*S;

SETNULL(S);//遞歸工作棧bitree

*

p=T;Push(S,NULL);while(p!=NULL){

printf

(“%c\n”,

p->data

);if

(

p->rchild

!=

NULL

)Push

(

S,

p->rchild

);if

(

p->lchild!=NULL

)//進左子樹p

=

p->lchild;else

Pop(

S,

p

);}}abcde第三十七頁，共八十五頁?！ず笮虮闅v二叉樹(非遞歸算法)用棧實現(xiàn)后序遍歷時使用的棧的結(jié)點定義typedef struct

{bitree

*ptr;//結(jié)點指針enum

tag{L,R};

//該結(jié)點退棧標記}

StackNode;

ptr

tag{L,R}根結(jié)點的tag

=

L，表示從左子樹退出,

訪問右子樹。tag

=

R, 表示從右子樹退出,

訪問根。第三十八頁，共八十五頁。·void

PostOrder

(

BinTree

T

)

{stack

S;

InitStack(&S);

StackNode

w;bitree

*

p

=

T;do

{while

(

p

!=

NULL

)

{

//向左子樹走w.ptr

=

p;

w.tag

=

L;

Push

(&S,

w);p

=

p->lchild;}int

continue=1;

//繼續(xù)循環(huán)標記第三十九頁，共八十五頁。while

(

continue

&&

!StackEmpty(&S)

)

{Pop

(&S,

w);

p

=

w.ptr;switch

(

w.tag

)

{case

L

:

w.tag=

R;//判斷棧頂tag標記

Push(&S,w);continue

=

0;p

=

p->rchild;

break;case

R

:

cout

<<

p->data

<<

endl;}}}

while

(

p

!=

NULL

||

!StackEmpty(&S)

);cout

<<

endl;}第四十頁，共八十五頁。練習:交換二叉樹各結(jié)點的左、右子樹(遞歸算法)void

unknown

(

bitree

*

T

){ bitree

*p

=

T,

*temp;if

(

p

!=

NULL

){

temp

=

p->lchild;p->lchild

=

p->rchild;p->rchild

=

temp;unknown

(

p->lchild

);unknown

(

p->rchild

);}}第四十一頁，共八十五頁。void

unknown

(

bitree

*

T

){

bitree

*p

=

T,

*temp;while

(

p

!=

NULL

){

temp

=

p->lchild;p->lchild

=

p->rchild;p->rchild

=

temp;unknown

(

p->lchild

);p

=

p->rchild;}}不用棧消去遞歸算法中的第二個遞歸語句第四十二頁，共八十五頁。使用棧消去遞歸算法中的兩個遞歸語句void

unknown

(

bitree

*

T

){

bitree

*p,

*temp;stack

*S;

SETNULL

(S);if

(

T

!=

NULL

){

push(S,

T);while

(

!

Empty(S)

){Pop(S,p);

//棧中退出一個結(jié)點temp=p->lchild;

//交換子女p->lchild

=

p->rchild;p->rchild

=

temp;第四十三頁，共八十五頁。if

(

p->rchild

!=

NULL

)push

(S,p->rchild

);if

(

p->lchild

!=

NULL

)push

(S,

p->lchild

);}}}第四十四頁，共八十五頁。ltag=0,ltag=1,rtag=0,rtag=1,lchild為左子女指針

lchild為前驅(qū)線索

rchild為右子女指針rchild為后繼指針lchildrchilddataltagrtag·線索二叉樹(Threaded

Binary

Tree)結(jié)點結(jié)構(gòu)第四十五頁，共八十五頁。第四十六頁，共八十五頁。下面給出線索鏈表的形式說明：typedef

int

datatype

;typedef

struct

node{

int

ltag

,

rtag

;datatype

data

;struct

node

*lchild

,

*rchild

;}bithptr

;bithptr

*pre

;第四十七頁，共八十五頁。通過中序遍歷建立中序線索化二叉樹bithptr

*pre

=null;INTHREAD

(

bithptr

*p

){

if

(

p

!=

NULL

)//左子樹線索化{

INTHREAD

(p->lchild

);if

(p->lchild

==

NULL

){

p->lchild

=

pre;p->ltag

=

1;}

//建立當前結(jié)點的前驅(qū)線索第四十八頁，共八十五頁。if

(

pre

!=

NULL

&&pre->rchild

==

NULL

)

{pre->rchild

=

p;pre->rtag

=

1;}

//建立前驅(qū)結(jié)點的后繼線索pre

=

p;//前驅(qū)跟上當前指針//遞歸,INTHREAD

(

p->rchild);右子樹線索化}}第四十九頁，共八十五頁。?樹的存儲結(jié)構(gòu)·雙親表示：以一組連續(xù)空間存儲樹的結(jié)點，同時在結(jié)點中附設一個指針，存放雙親結(jié)點在鏈表中的位置。樹與森林A0123456BCDdataABCDEFGEFGparent-1000113第五十頁，共八十五頁。用雙親表示實現(xiàn)的樹定義#define

MaxSize//最大結(jié)點個數(shù)typedef

char

datatype;//結(jié)點數(shù)據(jù)//樹結(jié)點定義typedef

struct

{datatype

data;int

parent;}

TreeNode;typedef

TreeNode

Tree[MaxSize];

//樹第五十一頁，共八十五頁。AB

CDEFG·左子女-右兄弟表示法第一種解決方案等數(shù)量的鏈域data

child1

child2child3childdABCDEFG空鏈域n(k-1)+1個第五十二頁，共八十五頁。結(jié)點結(jié)構(gòu)AB

C

DE

F

G空鏈域n+1個第二種解決方案樹的左子女-右兄弟表示（二叉鏈表表示）data

firstChild

nextSiblingBCDGFEA第五十三頁，共八十五頁。用左子女-右兄弟表示實現(xiàn)的樹定義typedef

char

datatype;typedef

struct

node

{datatype

data;struct

node

*firstChild,

*nextSibling;}

TreeNode;typedef

TreeNode

*

Tree;第五十四頁，共八十五頁。(1)樹轉(zhuǎn)化成二叉樹的簡單方法①

在同胞兄弟之間加連線；②

保留結(jié)點與第一個孩子之間的連線，去掉其余連線；③

順時針旋轉(zhuǎn)45度。以根結(jié)點為軸；左孩子不再旋轉(zhuǎn)。森林轉(zhuǎn)化成二叉樹④

將森林中的每棵樹轉(zhuǎn)換成對應的二叉樹；⑤

將森林中已經(jīng)轉(zhuǎn)換成的二叉樹的各個根視為兄弟，各兄弟之間自第一棵樹根到最后一棵樹根之間加連線；⑥

以第一棵樹的根為軸，順時針旋轉(zhuǎn)45度。第五十五頁，共八十五頁。T2T3T1

T2

T3A

F

HB

C

D

G

I

JE

KT1ABCDEGF

HIKJABCEDHIFG3

棵樹的森林K

J森林的二叉樹表示?森林與二叉樹的轉(zhuǎn)換各棵樹的二叉樹表示第五十六頁，共八十五頁。樹的二叉樹表示:深度優(yōu)先遍歷先根次序遍歷后根次序遍歷AB

C

DE

F?樹的遍歷GABCEDGF第五十七頁，共八十五頁。深度優(yōu)先遍歷當樹非空時訪問根結(jié)點

依次先根遍歷根的各棵子樹樹先根遍歷ABEFCDG對應二叉樹前序遍歷ABEFCDG樹的先根遍歷結(jié)果與其對應二叉樹表示的前序遍歷結(jié)果相同

樹的先根遍歷可以借助對應二叉樹的前序遍歷算法實現(xiàn)ABCEDGF·樹的先根次序遍歷第五十八頁，共八十五頁。·樹的后根次序遍歷:當樹非空時

依次后根遍歷根的各棵子樹訪問根結(jié)點樹后根遍歷EFBCGDA對應二叉樹中序遍歷EFBCGDA樹的后根遍歷結(jié)果與其對應二叉樹表示的中序遍歷結(jié)果相同樹的后根遍歷可以借助對應二叉樹的中序遍歷算法實現(xiàn)ABCEDGF第五十九頁，共八十五頁。二叉樹的計數(shù)由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹。例,前序序列{ABHFDECKG}和中序序列{HBDFAEKCG},構(gòu)造二叉樹過程如下：A

AHBDF

EKCG

B

EKCGH

DF第六十頁，共八十五頁。KCGEKCGABH

DFEKCGABHFDEABHFDEABHFDCKG第六十一頁，共八十五頁。如果前序序列固定不變，給出不同的中序序列，可得到不同的二叉樹。612345761237588

49

9固定前序排列,選擇所有可能的中序排列,可以構(gòu)造多少種不同的二叉樹？第六十二頁，共八十五頁。例如, 有

3

個數(shù)據(jù){

1,

2,

3

}，可得

5

種不同的二叉樹。它們的前序排列均為123，中序序

列可能是

321

，

231，

213，

132，123.21

1

12

2321

123

3

3

3具有n個結(jié)點不同形態(tài)的樹的數(shù)目和具有n-1個結(jié)點互不相似的二叉樹的數(shù)目相同。第六十三頁，共八十五頁。有0個,1個,2個,3個結(jié)點的不同二叉樹如下b0

=1b1

=1b2

=2b3

=5b4

=14第六十四頁，共八十五頁?！び嬎憔哂衝個結(jié)點的不同二叉樹的棵數(shù)最終結(jié)果：bibn-i-11第六十五頁，共八十五頁。哈夫曼樹(Huffman

Tree)·路徑長度(Path

Length)兩個結(jié)點之間的路徑長度PL是連接兩結(jié)點的路徑上的分支數(shù)。樹的外部路徑長度是各葉結(jié)點(外結(jié)點)到根結(jié)點的路徑長度之和EPL。樹的內(nèi)部路徑長度是各非葉結(jié)點(內(nèi)結(jié)點)到根結(jié)點的路徑長度之和IPL。樹的路徑長度PL=EPL+IPL第六十六頁，共八十五頁。1234

56782345678樹的外部路徑長度EPL

=

3*1+2*3

=

9樹的外部路徑長度EPL

=

1*1+2*1+3*1+4*1

=

101第六十七頁，共八十五頁?！?quán)路徑長度(Weighted

Path

Length,WPL)二叉樹的帶權(quán)(外部)路徑長度是樹的各葉結(jié)點所帶的權(quán)值wi

與該結(jié)點到根的路徑長度li

的乘積的和。第六十八頁，共八十五頁。WPL

=

2*1+WPL

=

7*1+4*2+5*2+4*2+5*3+5*2+2*3+7*2

=

367*3

=

464*3

=

35224455772

4

5

7WPL

=

2*2+帶權(quán)(外部)路徑長度達到最小第六十九頁，共八十五頁。哈夫曼樹

帶權(quán)路徑長度達到最小的二叉樹即為哈夫曼樹。在哈夫曼樹中，權(quán)值大的結(jié)點離根最近。哈夫曼算法(1)由給定的n個權(quán)值{w0,w1,w2,…,wn-1}，構(gòu)造具有n棵擴充二叉樹的森林F={T0,T1,T2,…,

Tn-1

}，其中每棵擴充二叉樹Ti

只有一個帶權(quán)值

wi

的根結(jié)點,其左、右子樹均為空。第七十頁，共八十五頁。(2)重復以下步驟,直到F中僅剩下一棵樹為止：①

在F

中選取兩棵根結(jié)點的權(quán)值最小的擴充二叉樹, 做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和。②在F中刪去這兩棵二叉樹。③把新的二叉樹加入F。第七十一頁，共八十五頁。F

:

{7}

{5}

{2}

{4}

F

:

{7}

{5}

{6}7

5

247

56初始

F:{7}{11}117562

4合并{5}{6}5合并{7}{11}2462

4合并{2}{4}F

:

{18}187

11舉例哈夫曼樹的構(gòu)造過程第七十二頁，共八十五頁。75

2

4Weightparentlchildrchil7-1-1-15-1-1-12-1-1-14-1-1-1-1-1-1-1-1-1-1-1-10123456上例存儲結(jié)構(gòu)初態(tài)第七十三頁，共八十五頁。572

46Weightparentlchildrchi0123456p1p27

-15

-12

4-14

4-16

-1-1-1-1-1-1-1-12-1-1-1-1-1-1-1

3-1-1i過程第七十四頁，共八十五頁。5274611Weightparentlchildrchild11-1-10123456p1p27-1-1-155-1-1-124-1-144-1-16-5123-11-1-1

4-1i第七十五頁，共八十五頁。52467

11Weightparentlchildrchild0123456p1p276-1-1

-155-1

-124-1

-144-1

-1652

3116-11418-1-01-15i18終態(tài)第七十六頁，共八十五頁。int

n=20;//葉結(jié)點數(shù)int

m=2*n

-1;//結(jié)點數(shù)typedef

struct

{float

weight;int

parent,

lchild,

rchild;}

hufmt