6.1樹的定義和基本術(shù)語

6.2二叉樹

6.3遍歷二叉樹和線索二叉樹

6.4樹和森林

6.6赫夫曼樹及其應(yīng)用

6.1樹的是文

打基本術(shù)得

樹的定義樹是一種數(shù)據(jù)結(jié)構(gòu)Tree=(D,R)

其中D是包含n個數(shù)據(jù)元素的有限集(nNO),若

n<l9則R=①，否則R={H},H是D上的二元關(guān)系，

它滿足下列條件：

1)D中有且僅有一個數(shù)據(jù)元素root在關(guān)系H下無前驅(qū),

root稱為根。

2)D中除根root以外的任一數(shù)據(jù)元素都有且僅有一個

前驅(qū)。

3)對于D中除根root以外的任一數(shù)據(jù)元素e,都存在

一個元素序列root=e0?ebe2,…，es=e,

使得(l<i<s)9

該序列稱為從根到元素e的一條路徑。

例：T=（D，R）

D={a,b,c,d,e,f,g,k}R={H}

H={<a,b>,<a,c>,<a,d>,<b,e>,<b,f>,

〈d,g〉，〈f,k〉}

從才艮a至I結(jié)點k的

路徑為：

⑶b,f,k）

樹的遞歸定義

樹是n(nNO)個結(jié)點的有限集。在任意一棵

非空樹中：

1)有且僅有一個特定的稱為根的結(jié)點；

2)當(dāng)n>l時，其余結(jié)點可分為m(m>0)個互不

相交的有限集…,Tm，其中每一個子

集本身又是一棵樹，并且稱為根的子樹。

樹形結(jié)構(gòu)基本術(shù)語

結(jié)點的度：結(jié)點的子樹個數(shù)（后繼個數(shù)）;

樹的度：樹中各結(jié)點的度的最大值；

葉子結(jié)點（終端結(jié)點）：度為零的結(jié)點；

分支結(jié)點（非終端結(jié)點）：度大于零的結(jié)點;

結(jié)點的層次：根結(jié)點的層次定義為1,

第/層結(jié)點的子樹根結(jié)點的

層次為/+1;

樹的深度（高度）：樹中結(jié)點的最大層次;

若〈e,e，〉eH,則稱e是e，的雙親，

"是e的孩子；

若〈e,er>eH,<e,en>eH,則e[e"互為兄弟;

從根到某結(jié)點路徑上的所有結(jié)點都是該

結(jié)點的祖先；以某結(jié)點為根的子樹中的任

一結(jié)點都稱為該結(jié)點的子孫。

有向樹：

如果一棵樹有確定的根，并且樹根和子

樹根之間為有向關(guān)系，則稱作有向樹。

有序樹、無序樹：

如果我們關(guān)心樹中結(jié)點的各子樹的相對

次序，把它們看成是從左至右有序的（即

不能互換），則稱該樹為有序樹，否則稱

為無序樹。

森林(樹林):

零棵或多棵互不相交的樹的有序集合。

任何一棵非空樹是一個二元組

Tree=(root,F)

其中：root稱為根結(jié)點,F稱為root的子樹森林。

——樹的間接遞歸定義

樹形結(jié)構(gòu)和線性結(jié)構(gòu)結(jié)構(gòu)特點比較

線性結(jié)構(gòu)樹形結(jié)構(gòu)

第一個數(shù)據(jù)元素根結(jié)點

（無前驅(qū)）（無前驅(qū)）

最后一個數(shù)據(jù)元素多個葉子結(jié)點

（無后繼）（無后繼）

其它數(shù)據(jù)元素其它數(shù)據(jù)元素

（一個前驅(qū)、（一個前驅(qū)、

一個后繼）多個后繼）

樹的基本操作

InitTree(&T)//初始化

操作結(jié)果：構(gòu)造空樹T。該參數(shù)應(yīng)能給出:

一棵樹的精確定義，

DestroyTree(&T)//峪肖毀例如它可以是一個

初始條件：樹T存在。以廣義表形式表示

操作結(jié)果：銷毀樹T。的樹。；

CreateTree(&T9definition)//建樹

初始條件：definition給出樹T的定義。

操作結(jié)果：按definition構(gòu)造樹T。

ClearTree(&T)//清樹

初始條件：樹T存在。

操作結(jié)果：將樹T清為空樹。

TreeEmpty(T)〃判樹空

初始條件：樹T存在。

操作結(jié)果：若T為空樹，則返回True,否則返回False。

TreeDepth(T)〃求深度

初始條件：樹T存在。

操作結(jié)果：返回T的深度。

Root(T)//求根

初始條件：樹T存在。

操作結(jié)果：返回T的根。

Parent"cure)〃求雙親

初始條件：樹T存在，cur_e是T中某個結(jié)點。

操作結(jié)果：若cur_e是T的非根結(jié)點,

則返回它的雙親，否則返回“空”。

LeftChild(T9cure)〃求最左孩子

初始條件：樹T存在，cur_e是T中某個結(jié)點。

操作結(jié)果：若cur_e是T的非葉結(jié)點，

則返回它的最左孩子，否則返回“空”。

RightSibling(T5cure)〃求右兄弟

初始條件：樹T存在，cur_e是T中某個結(jié)點。

操作結(jié)果：若cur_e有右兄弟，

則返回它的右兄弟，否則返回“空”。

InsertChild(&T5&p,i,c)//插入子樹

初始條件：樹T存總p指向T中某個結(jié)點，

l<i<p結(jié)點的度+1俳空樹c與T不相交。

操作結(jié)果：插入c為T中p結(jié)點的第i棵子樹。

DeleteChild(&T5&p,i)//刪除子樹

初始條件：樹T存在，p指向T中某個結(jié)點，

l<i<p結(jié)點的度。

操作結(jié)果：刪除T中p結(jié)點的第i棵子樹。

TraverseTree(T9VisitQ)//遍歷

初始條件：樹T存在,Visit是對結(jié)點操作的應(yīng)用函數(shù)。

操作結(jié)果：按某種次序?qū)的每個結(jié)點調(diào)用函數(shù)Visit

一■次且至多一■次。

事

4

6.2.1二叉樹的定義

二叉樹是結(jié)點的有限集合，該集合或者為空

集；或者由一個根結(jié)點和兩棵不相交的分別稱

作左子樹和右子樹的二叉樹組成。

二叉樹與樹的區(qū)別：

二叉樹不是樹的特殊情形，而是與樹不同的

數(shù)據(jù)結(jié)構(gòu)，即二叉樹并不等價于2度的樹。

1）二叉樹中不存在度大于2的結(jié)點。

2）二叉樹中結(jié)點的子樹有左、右之分。

二叉樹的基本操作

InitBiTree(&T)//初始化

操作結(jié)果：構(gòu)造空二叉樹T。

DestroyBiTree(&T)//銷毀

初始條件：二叉樹T存在。

操作結(jié)果：銷毀二叉樹T。

CreateBiTree(&T,definition)//建二叉樹

初始條件：definition給出二叉樹T的定義。

操作結(jié)果：按definition構(gòu)造二叉樹T。

ClearBiTree(&T)〃清樹

初始條件：二叉樹T存在。

操作結(jié)果：將二叉樹T清為空樹。

BiTreeEmpty(T)//判樹空

初始條件：二叉樹T存在。

操作結(jié)果：若T為空二叉樹,則返回True,否則False。

BiTreeDepth(T)//求深度

初始條件：二叉樹T存在。

操作結(jié)果：返回T的深度。

Root(T)//求根

初始條件：二叉樹T存在。

操作結(jié)果：返回T的根。

Parent。,e)〃求雙親

初始條件：二叉樹T存在，e是T中某個結(jié)點。

操作結(jié)果：若e是T的非根結(jié)點，

則返回它的雙親，否則返回“空”。

LeftChild(T9e)〃求左孩子

初始條件：二叉樹T存在，e是T中某個結(jié)點。

操作結(jié)果：返回e的左孩子。

若e無左孩子，則返回“空”。

RightChild。,e)//求右孩子

初始條件：二叉樹T存在，e是T中某個結(jié)點。

操作結(jié)果：返回e的右孩子。

若e無右孩子，則返回“空”。

InsertChild(T,p,LR,c)//插入子樹

初始條件：二叉樹T存在，p指向T中某個結(jié)點，

LR為0或1,非空二叉樹c與T不相交且

右子樹為空。

操作結(jié)果：根據(jù)LR為。或1,插入c為T中p結(jié)點的

左或右子樹。p結(jié)點原有的左或右子樹則

成為c的右子樹。

DeleteChild(T5p5LR)〃刪除子樹

初始條件：二叉樹T存在，p指向T中某個結(jié)點，

LR為。或1。

操作結(jié)果：根據(jù)LR為0或1，

刪除T中p結(jié)點的左或右子樹。

對于下列二叉樹,分別畫出：

1）插入子樹操作InsertChild（T5p90,c）完成后

二叉樹T的狀態(tài)；

2）插入子樹操作InsertChild。,p,1,c）完成后

二叉樹T的狀態(tài)；

6.2.2二叉樹的性質(zhì)

性質(zhì)1:

在二叉樹的第，層上至多有2叼個結(jié)點（，》/）。

用歸納法證明：

1）i=1時,只有一個根結(jié)點）2、i=2。=1;

2）假設(shè)對所有的力l<j<i-l9命題成立,即

第層上至多有2、2個結(jié)點。

二叉樹上每個結(jié)點至多有兩棵子樹，則

第i層的結(jié)點數(shù)S2"2x2=2，”證畢

性質(zhì)2:

深度為k的二叉樹至多有2心1個結(jié)點

（k》l）

證明：

根據(jù)性質(zhì)1,深度為上的二叉樹上的結(jié)

點數(shù)至多為

2。+21+...........+2kA=2k-l

證畢

性質(zhì)3:

對于任何一棵非空二叉樹，若它的葉子結(jié)點

數(shù)為n0,2度結(jié)點數(shù)為叼，則n0=n2+lo

證明：

設(shè)二叉樹結(jié)點總數(shù)為n=n0+H]+n2

則二叉樹上分支總數(shù)b=n1+2n2

而b=n-1=n0+Hj+n2-1

于是〃o+I=+2〃2艮口no=n2+

證畢

特殊形態(tài)二叉樹：

滿二叉樹

——深度為4且有2J?個結(jié)點的二叉樹。

完全二叉樹（近似滿二叉樹）

——深度為4的二叉樹，若前AU層構(gòu)成

滿二叉樹，且第左層結(jié)點從最左邊開始依次連

續(xù)排列，則稱作完全二叉樹。

嚴(yán)格二叉樹（正則二叉樹）

——若二叉樹中不存在度為1的結(jié)點，則

稱作嚴(yán)格二叉樹。

性質(zhì)4:

具有〃個結(jié)點的完全二叉樹的深度為

\jog2n\+1

證明:

設(shè)完全二叉樹的深度為k

則根據(jù)性質(zhì)2和完全二叉樹的定義有

kAk

2<n<2即k-1<log2n<k

,:k是整數(shù):.k=Uog2〃」+1

證畢

性質(zhì)5:

若對一棵有n個結(jié)點的完全二叉樹自上而下先

左后右進行從I至M的編號(即按層次次序編號),

則對完全二叉樹中任意一個編號為i的結(jié)點，有：

⑴若則該結(jié)點是二叉樹的根，無雙親，

否則，其雙親結(jié)點是編號為|_〃2」的結(jié)點；

⑵若2i>",則該結(jié)點無左孩子，

否則，其左孩子結(jié)點是編號為2i的結(jié)點；

(3)若2計7>〃，則該結(jié)點無右孩子結(jié)點，

否則，其右孩子結(jié)點是編號為2i+l的結(jié)點。

6.2.3二叉樹的存儲結(jié)構(gòu)

一、順序存儲結(jié)構(gòu)

完全二叉樹的順序存儲——

將完全二叉樹的所有結(jié)點按層次次序存儲在

一組地址連續(xù)的存儲單元中。

非完全二叉樹的順序存儲——

先將其擴充為完全二叉樹，再按完全二叉樹

存儲之。

二叉樹順序存儲結(jié)構(gòu)的類C語言描述

//--二叉樹的順序存儲結(jié)構(gòu)（完全二叉樹表示法）

#defineMAX_TREE_SIZE100

〃結(jié)構(gòu)大小，二叉樹最大結(jié)點數(shù)+1

typedefTElemTypeSqBiTree[MAX_TREE_SIZE];

〃數(shù)組的1號單元存儲根結(jié)點，0號單元不使用

SqBiTreebt;

二、鏈?zhǔn)酱鎯Y(jié)構(gòu)

?二叉鏈表

?三叉鏈表

?線索鏈表

?二叉鏈表

結(jié)點結(jié)構(gòu):Ichilddatarchild

?三叉鏈表

結(jié)點結(jié)構(gòu):Ichilddataparentrchild

二叉鏈表的類C語言描述

//一一?二叉樹的二叉鏈表存儲結(jié)構(gòu)

typedefstructBiTNode{

TElemTypedata;

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;

結(jié)構(gòu)體類型結(jié)構(gòu)體指針類型

6.3遍歷二義相

和狡索二天樹

6.3.1遍歷二叉樹

按一定的次序系統(tǒng)地訪問二叉樹中的

結(jié)點，使得每個結(jié)點均被訪問一次，并

且僅被訪問一次。

“訪問”是一種抽象操作，指對結(jié)點所

進行的某種處理，如讀取、修改、輸出

結(jié)點信息等。

遍歷二叉樹的方式

NLR（先序、前序）

LNR（中序、對稱序）

LRN（后序）

層次序

先序遍歷操作的定義:

若二叉樹為空，則空操作；否貝八

(1)訪問根結(jié)點；

(2)先序遍歷左子樹；

(3)先序遍歷右子樹。

中序遍歷操作的定義:

若二叉樹為空）則空操作；否貝h

（1）中序遍歷左子樹；

（2）訪問根結(jié)點；

（3）中序遍歷右子樹。

后序遍歷操作的定義:

若二叉樹為空，則空操作；否貝h

(1)后序遍歷左子樹；

(2)后序遍歷右子樹；

(3)訪問根結(jié)點。

StatusPreOrder(BitreeT,Status(*Visit)(TElemType)){

〃最簡單的Visit函數(shù)舉例：

〃StatusPrintElement(TElemTypee)

〃{printf(e);returnOK;}

〃調(diào)用實例：PreOrder(T,PrintElement);

if(T){

if(Visit(T->data))

if(PreOrder(T->lchild,Visit))

if(PreOrder(T->rchild,Visit))returnOK;

returnERROR;

}elsereturnOK;

}//PreOrder

算法6.1

StatusPreOrder(BitreeT,Status(*Visit)(TElemType)){

//先序遍歷二叉樹的遞歸算法

//采用二叉鏈表存儲結(jié)構(gòu)，T為根指針

//設(shè)Visit操作不會發(fā)生失敗的情況

if(T){

Visit(T->data);

PreOrder(T->lchild,Visit);

PreOrder(T->rchild,Visit);

returnOK;

}//PreOrder

算法6.1a

StatusInOrder(BitreeT,Status(*Visit)(TElemType)){

//中序遍歷二叉樹的非遞歸算法,T為二叉鏈表的根指針

InitStack(S);Push(S,T);

while(!StackEmpty(S)){

while(GetTop(S,p)&&p)Push(S9p->lchild);

Pop(S,p);〃找二叉樹“最左下”的結(jié)點

if(IStackEmpty(S)){

Pop(S,p);if(!Visit(p->data))returnERROR;

Push(S,p->rchild);

returnOK;

}//InOrder

算法6.2

StatusInOrder(BitreeT,Status(*Visit)(TElemType)){

//中序遍歷二叉樹的非遞歸算法,T為二叉鏈表的根指針

InitStack(S);p=T;

while(p||IStackEmpty(S))

if(p){Push(S,p);p=p->lchild;}

〃找二叉樹“最左下”的結(jié)點

else{

Pop(S9p);if(!Visit(p->data))returnERROR;

p=p->rchild;

)

returnOK;

}//InOrder

算法6.3

二叉樹遍歷的應(yīng)用

?求二叉樹的深度

?先序建立二叉鏈表

?表達(dá)式二叉樹及其應(yīng)用

?根據(jù)先序和中序序列構(gòu)造二叉樹

?求二叉樹的深度

intdepth(BiTreeT){

//本算法返回根指針為T的二叉樹的深度

if(!T)return0;

left=depth(T->lchild);//求左子樹深度

right=depth(T->rchild);//求右子樹深度

returnleft>right?left+1:right+1;

}//depth

問題：算法采用了何種遍歷次序?

?先序建立二叉鏈表——算法6.4

StatusCreateBitree(Bitree&T){

scanf(&ch);

if(ch==!!)T=NULL;

else{

T=(BiTNode*)malloc(sizeof(BiTNode));

if(!T)exit(OVERFLOW);

T->data=ch;//生成根結(jié)點

CreateBitree(T->lchild);〃建左子樹

CreateBitree(T->rchild);//建右子樹

)

returnOK;

}//CreateBitree

■表達(dá)式二叉樹及其應(yīng)用

表達(dá)式可以用二叉樹表示,如：a*b-c

特點：

操作數(shù)做葉子結(jié)點

運算符為分支結(jié)點

先序序列:-*abc前綴式

中序序列:a*b-c中綴式

后序序列:ab*c-后綴式

?根據(jù)先序和中序序列構(gòu)造二叉樹

僅知二叉樹結(jié)點的先序序列abcdefg9

不能唯一■確定一■棵二叉樹；

如果同時已知它的中序序列cbdaegf,

則此二叉樹可構(gòu)造出來。

6.3.2線索二叉樹

關(guān)于二叉鏈表，有下列事實：

1）在二叉鏈表中大約有一半指針域為空；

2）在二叉鏈表中進行遍歷操作不很方便。

為了使二叉樹的遍歷操作更加方便、更加有

效，一個行之有效的方法就是利用二叉鏈表的

空指針域存放一些有利于遍歷的信息。

例如：

若lchild=NULL,則存放結(jié)點的中序前驅(qū)地址；

若rchild=NULL,則存放結(jié)點的中序后繼地址。

一叉樹結(jié)點中指向某種遍歷次序下的前驅(qū)結(jié)點

或后繼結(jié)點的指針稱之為線索?！?/p>

加進了線索的二叉鏈表稱為線索鏈表，其邏輯

結(jié)構(gòu)稱為線索二叉樹。

在中序線索二叉樹中，結(jié)點之間存在兩種關(guān)系：

1）雙親一孩子關(guān)系（樹形結(jié)構(gòu)中的關(guān)系）

2）中序下的前驅(qū)—后繼關(guān)系（線性關(guān)系）

線索的標(biāo)識

在線索鏈表中，指針域的值雖然都是地址,但意

義不同，線索和孩子結(jié)點的地址必須加以區(qū)分。

為此，需改變結(jié)點結(jié)構(gòu)，增加兩個標(biāo)志域：

IchildLTagdataRTagrchild

10Ichild存放結(jié)點的左孩子地址

LTag=

Ichild存放結(jié)點的前驅(qū)線索

f0rchild存放結(jié)點的右孩子地址

RTag=1

rchild存放結(jié)點的后繼線索

線索鏈表的類C語言描述

枚舉常量

//——二叉樹的線索鏈表存儲結(jié)構(gòu)

typedefenumPointerTag{Link,Thread};

//Link==O:孩子指針,Thread==l:線索

typedefstructBiThrNode{

TElemTypedata;

structBiThrNode*lchild5*rchild;

enumPointerTagLTag,RTag;

}BiThrNode,*BiThrTree;

線索鏈表的應(yīng)用

由于線索鏈表中保存了線索，從而給二叉樹

的一些操作帶來了方便。

例如，在中序雙向線索鏈表中，可以很方便

地確定任一結(jié)點*P的中序后繼：

若p->RTag==Thread

貝I若p->rchild==thrt

則無后繼

否貝I后繼為*(p->rchild)

否則后繼為其右子樹中“最左下”的結(jié)

點

StatusInOrder(BiThrtreeT,Status(*Visit)(TElemType)){

//中序遍歷中序雙向線索鏈表,T為其頭指針

p=T->lchild;//p指向根結(jié)點或頭結(jié)點(p==T)

while(p!=T){

while(p->LTag==Link)p=p->lchild;〃找最左下結(jié)點

if(!Visit(p->data))returnERROR;

while(p->RTag==Thread&&p->rchild!=T){

p=p->rchild;if(!Visit(p->data))returnERROR;

}

p=p->rchild;//p指向右子樹的根或頭結(jié)點

returnOK;

}//InOrder

算法6.5

二叉樹的線索化

將未加入線索的二叉鏈表改造成為線索鏈表的

過程稱作二叉鏈表的線索化或二叉樹的線索化。

算法6.6已知T指向二叉鏈表的根結(jié)點，二叉鏈

表中所有結(jié)點的LTagRTag域為0;該算法中

序遍歷生成中序雙向線索鏈表，Thrt為指向頭

結(jié)點的指針。

算法6.7中序線索化以p為根指針的二叉鏈表，

算法結(jié)束后，pre指向該二叉樹中序遍歷的最

后一個結(jié)點）且除pre->rchild==NULL外,該

二叉樹中其余結(jié)點的指針域均非空。

線索二叉樹相關(guān)問題:

1）根據(jù)需要，可以對二叉樹進行中序線索化、

先序線索化或后序線索化。

2）線索二叉樹可以是完全線索化的，即既有前

驅(qū)線索又有后繼線索。也可以只進行后繼線

索化，構(gòu)成后繼線索二叉樹。

3）在后序線索二叉樹中求結(jié)點的后序后繼仍可

能是不方便的。

6.4.1樹的存儲結(jié)構(gòu)

一、雙親表示法

二、孩子鏈表表示法

三、孩子兄弟表示法

（樹的二叉鏈表表示法）

一、雙親表示法

將樹的結(jié)點按某種次序存儲在一組連續(xù)

的存儲單元中，每個結(jié)點中設(shè)一個指示器

指示其雙親結(jié)點的存儲位置。

雙親表示法的特點：

空間占用較少，求雙親、求根操作比較

方便；但求結(jié)點的孩子時需遍歷整個鏈表。

雙親表示法的類C語言描述

//---樹的雙親存儲表示----

#defineMAX_TREE_SIZE100

typedefstruct{〃結(jié)點結(jié)構(gòu)

TElemTypedata;

intparent;//雙親位置域

}PTNode;

typedefstruct{//樹結(jié)構(gòu)

PTNodenodes[MAX_TREE_SIZE];

intr5n;〃根的位置和結(jié)點數(shù)

}PTree;

二、孩子鏈表表示法

#defineMAX_TREE_SIZE100

typedefstructCTNode{〃孩子結(jié)點

intchild;

structCTNode*next;

}*ChildPtr;

typedefstruct{

TElemTypedata;

ChildPtrfirstchild;〃孩子鏈表頭指針

}CTBox;

typedefstruct{

CTBoxnodes[MAX_TREE_SIZE];

intr,n;〃根的位置和結(jié)點數(shù)

}CTree;

三、孩子兄弟表示法

（二叉樹表示法，二叉鏈表表示法）

結(jié)點結(jié)構(gòu)：

Ifc/hIdataInsi、b__

/\

firstchildnextsibling

類c語言描述

//-----樹的二叉鏈表（孩子?兄弟）存儲表示-----

typedefstructCSNode{

ElemTypedata;

structCSNode*fch,*nsib;

}CSNode,*CSTree;

6.4.2森林與二叉樹的轉(zhuǎn)換

樹與二叉樹之間存在著必然聯(lián)系——任

意給定一棵樹，可以找到唯——棵二叉樹

與之對應(yīng)。

二叉鏈表存儲結(jié)構(gòu)相同的樹和二叉樹相

互對應(yīng)。

任何一棵和樹對應(yīng)的二叉樹，其右子樹

必空。

樹和二叉樹各部分的對應(yīng)關(guān)系

樹二叉樹

根根

結(jié)點的結(jié)點的左孩子

第一個孩子

結(jié)點的結(jié)點的右孩子

下'一■個兄弟

森林和二叉樹各部分的對應(yīng)關(guān)系

森林二叉樹

第一棵樹的根根

第一棵樹

根的左子樹

根結(jié)點的子樹森林

除第一棵樹外

根的右子樹

其余樹組成的森林

轉(zhuǎn)換規(guī)則的遞歸定義

一、森林轉(zhuǎn)換成二叉樹

如果F=(TbT2,…,Tm)是森林,則可按如下

規(guī)則轉(zhuǎn)換成一棵二叉樹B=(root,LB,RB):

(1)若F為空，即m=0,則B為空樹；

(2)若F非空,即mM,則B的根root即為森

林中第一棵樹的根ROOT(Ti);B的左子樹LB是

從Ti中根結(jié)點的子樹森林Fi=(Tn,T12,...,Tlml)

轉(zhuǎn)換而成的二叉樹；其右子樹RB是從森林

F'=(12,T3,??.，轉(zhuǎn)換而成的二叉樹。

二、二叉樹轉(zhuǎn)換成森林

如果B=(root,LB,RB)是一棵二叉樹，則可按

如下規(guī)則轉(zhuǎn)換成森林F=(TbT2,

(1)若B為空,則F為空；

(2)若B非空，貝IF中第一棵樹Ti的根ROOT(Ti)

即為二叉樹B的根root;T1中根結(jié)點的子樹森林

Fi是由B的左子樹LB轉(zhuǎn)換而成的森林；F中除Ti

之外其余樹組成的森林F=02,13,…,Tm)是由

B的右子樹RB轉(zhuǎn)換而成的森林。

轉(zhuǎn)換的意義

有許多實際問題的數(shù)學(xué)模型都是樹，而樹的

結(jié)構(gòu)較復(fù)雜，計算機直接處理不很方便。由于

森林和二叉樹有著----對應(yīng)的關(guān)系，樹和森林

的問題就可以轉(zhuǎn)化為二叉樹的問題。

二叉樹結(jié)構(gòu)簡單，存儲及操作實現(xiàn)比較容易。

樹和森林可以轉(zhuǎn)化為二叉樹存儲，樹和森林的

操作也可以通過其對應(yīng)二叉樹的操作來完成。

6.4.3樹和森林的遍歷

?樹的遍歷

?森林的遍歷

.森林的遍歷

與二叉樹遍歷的關(guān)系

?樹的遍歷

先根（次序）遍歷：

若樹不空，則先訪問根結(jié)點，然后依次

先根遍歷根的每棵子樹。

后根（次序）遍歷：

若樹不空,則先依次后根遍歷根的每棵

子樹，然后訪問根結(jié)點。

層次（次序）遍歷：

若樹不空，則自上而下從左至右按層次

訪問樹中每個結(jié)點。

森林的三個組成部分：

1）森林中第一棵樹的

根結(jié)點；

2）森林中第一棵樹的

根結(jié)點的子樹森林；

3）森林中（除第一棵樹之外）

其余樹才勾成的森林。

?森林的遍歷

先序（先根次序）遍歷：

若森林不空，則

1）訪問森林中第一棵樹的根結(jié)點；

2）先序遍歷第一棵樹根結(jié)點的子樹森林；

3）先序遍歷除第一棵樹之外其余樹構(gòu)成的

森林。

即：從左至右依次對森林中的每一棵樹

進行先根次序遍歷。

中序（后根次序）遍歷：

若森林不空，則

1）中序遍歷第一棵樹根結(jié)點的子樹森林；

2）訪問第一棵樹的根結(jié)點；

3）中序遍歷除第一棵樹之外其余樹構(gòu)成的

森林。

即：從左至右依次對森林中的每一棵樹

進行后根次序遍歷。

?森林的遍歷與二叉樹遍歷的關(guān)系

森林（樹）的先根和后根遍歷分

別等同于其對應(yīng)二叉樹的先序和中

序遍歷。

6.6赫夫曼哲

及其應(yīng)用

6.6.1最優(yōu)二叉樹（赫夫曼樹）

?結(jié)點的路徑長度

從根到該結(jié)點路徑上的分支數(shù)目。

（即結(jié)點的真祖先數(shù)目）

?樹的路徑長度

樹中每個結(jié)點的路徑長度之和。

?結(jié)點的帶權(quán)路徑長度

結(jié)點上的權(quán)與該結(jié)點路徑長度的乘積。

?樹的帶權(quán)路徑長度

樹中所有葉子結(jié)點的帶權(quán)路徑長度之和，

通常記作：

葉子結(jié)點個數(shù)一|一葉子結(jié)點上的權(quán)

WPL=Y^k------1

rk=l

WeightedPathLength葉子結(jié)點的路徑長度

?赫夫曼樹(Huffinantree)

給定一組n個實數(shù)，以它們作為各葉子

結(jié)點上的權(quán)，可以構(gòu)成不同的有n個葉子

結(jié)點的二叉樹，其中帶權(quán)路徑長度最小的

二叉樹稱為最優(yōu)二叉樹或赫夫曼樹。

*在所有含n個葉子結(jié)點且?guī)в邢嗤瑱?quán)值

的m叉樹中，必存在一棵帶權(quán)路徑長度取

最小值的樹,稱為最優(yōu)樹,又稱赫夫曼樹。

赫夫曼算法(Huffiman1952)

1）根據(jù)給定的n個權(quán)值{w19W25...5wn}9構(gòu)造n

棵二叉樹的集合F=…，1},其中每棵

二叉樹E中均只含一個帶權(quán)值為四的根結(jié)點，

其左、右子樹均為空樹；

2）在F中選取兩棵其根結(jié)點的權(quán)值為最小的二叉

樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹,

并置這棵新二叉樹根結(jié)點的權(quán)值為其左、右子

樹根結(jié)點的權(quán)值之和；

3）從F中刪去這兩棵樹，同時加入剛生成的新樹;

4）重復(fù)2）和3）兩步，直至F中只含一棵樹為止。

對于給定的一組權(quán)值，根據(jù)赫夫曼算

法構(gòu)造的最優(yōu)樹可能不是唯一的。

赫夫曼算法可知,赫夫曼樹是一棵

嚴(yán)格二叉樹,故有n個葉子結(jié)點的赫夫

曼樹共有2n-l個結(jié)點。

赫夫曼樹應(yīng)用之一——設(shè)計最佳判定算法

例：將百分制轉(zhuǎn)換成五級分制的程序

if(a<60)b="bad";

elseif(a<70)b="pass";

elseif(a<80)b="general";

elseif(a<90)b="good";

elseb=nexcellent1;

分?jǐn)?shù)0?5960?6970?7980?8990?100

比例數(shù)0.050.150.400.300.10

80%以上的數(shù)據(jù)需進行3次或3次以上的

比較才能得出結(jié)果

轉(zhuǎn)

換

五

級

分

制

的

判30

(a)