6.1樹的類型定義6.2二叉樹的類型定義6.3

二叉樹的存儲結構6.4二叉樹的遍歷6.5線索二叉樹6.6樹和森林的表示方法6.7樹和森林的遍歷6.8哈夫曼樹與哈夫曼編碼第六章樹和二叉樹6.1樹的類型定義

A

C

GT2D

HIT3J

M

BEL

KT1F例子：學校的行政關系、書的層次結構、人類的家族血緣關系等。結點間有明顯的層次結構關系數據對象D：D是具有相同特性的數據元素的集合。

數據關系R：若D為空集，則稱為空樹。否則:(1)在D中存在唯一的稱為根的數據元素root；

(2)當n>1時，其余結點可分為m(m>0)個互不相交的有限集T1,2,…,Tm，其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹。

基本操作：查找類

插入類刪除類

Root(T)//求樹的根結點

查找類：Value(T,cur_e)//求當前結點的元素值

Parent(T,cur_e)//求當前結點的雙親結點LeftChild(T,cur_e)//求當前結點的最左孩子RightSibling(T,cur_e)//求當前結點的右兄弟TreeEmpty(T)//判定樹是否為空樹TreeDepth(T)//求樹的深度TraverseTree(T,Visit())//遍歷InitTree(&T)//初始化置空樹

插入類：CreateTree(&T,definition)//按定義構造樹Assign(T,cur_e,value)//給當前結點賦值InsertChild(&T,&p,i,c)

//將以c為根的樹插入為結點p的第i棵子樹

ClearTree(&T)//將樹清空

刪除類：DestroyTree(&T)//銷毀樹的結構DeleteChild(&T,&p,i)//刪除結點p的第i棵子樹樹的表示樹根T1T2T3(１)有確定的根；(２)樹根和子樹根之間為有向關系。有向樹：有序樹：子樹之間存在確定的次序關系。無序樹：子樹之間不存在確定的次序關系。對比樹型結構和線性結構的結構特點~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結構樹型結構第一個數據元素

(無前驅)

根結點

(無前驅)最后一個數據元素

(無后繼)多個葉子結點

(無后繼)其它數據元素(一個前驅、一個后繼)其它數據元素(一個前驅、多個后繼)基本術語結點:結點的度:樹的度:葉子結點:分支結點:數據元素+若干指向子樹的分支分支的個數樹中所有結點的度的最大值度為零的結點度大于零的結點DHIJM(從根到結點的)路徑：孩子結點、雙親結點兄弟結點、堂兄弟祖先結點、子孫結點結點的層次:樹的深度：

由從根到該結點所經分支和結點構成ABCDEFGHIJMKL假設根結點的層次為1，第l層的結點的子樹根結點的層次為l+1樹中葉子結點所在的最大層次任何一棵非空樹是一個二元組

Tree=（root，F）其中：root被稱為根結點

F被稱為子樹森林森林：是m（m≥0）棵互不相交的樹的集合ArootBCDEFGHIJMKLF6.2

二叉樹的類型定義

二叉樹或為空樹，或是由一個根結點加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。ABCDEFGHK根結點左子樹右子樹二叉樹的五種基本形態：N空樹只含根結點NNNLRR右子樹為空樹L左子樹為空樹左右子樹均不為空樹

二叉樹的主要基本操作：查找類插入類刪除類

Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);

PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());

InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);二叉樹

的重要特性

性質1：

在二叉樹的第i

層上至多有2i-1個結點。(i≥1)用歸納法證明：

歸納基：

歸納假設：

歸納證明：i=1

層時，只有一個根結點：2i-1=20=1；假設對所有的j，1≤j

i，命題成立；二叉樹上每個結點至多有兩棵子樹，則第i層的結點數=2i-2

2=2i-1

。423167891011121314155第三層上(i=3)，有23-1=4個節點。第四層上(i=4)，有24-1=8個節點。性質2：

深度為k的二叉樹上至多含2k-1個結點（k≥1）。證明：

基于上一條性質，深度為k的二叉樹上的結點數至多為

20+21+

+2k-1=2k-1

。423167891011121314155此樹的深度k

=4，共有24-1=15個節點。

性質3：

對任何一棵二叉樹，若它含有n0個葉子結點、n2個度為

2

的結點，則必存在關系式：n0=n2+1。證明：設二叉樹上結點總數n=n0+n1+n2又二叉樹上分支總數b=n1+2n2

而b=n-1=n0+n1+n2-1由此，n0=n2+1。423167891011121314155n0=8n2=7兩類特殊的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個結點的二叉樹。完全二叉樹：樹中所含的n個結點和滿二叉樹中編號為1至n的結點一一對應。123456789101112131415abcdefghij特點：每一層上都含有最大結點數。深度為K的滿二叉樹，結點個數為2k-1

性質4

：

具有n個結點的完全二叉樹的深度為

log2n

+1。證明：設完全二叉樹的深度為k則根據第二條性質得2k-1≤n<2k

即

k-1≤log2n<k因為k只能是整數，因此，k=log2n

+1。423167891011121314155性質5：若對含n個結點的完全二叉樹從上到下且從左至右進行1

至n

的編號，則對完全二叉樹中任意一個編號為i

的結點：

(1)若i=1，則該結點是二叉樹的根，無雙親，否則，編號為

i/2

的結點為其雙親結點；

(2)若2i>n，則該結點無左孩子，

否則，編號為2i的結點為其左孩子結點；

(3)若2i+1>n，則該結點無右孩子結點，

否則，編號為2i+1的結點為其右孩子結點。423167891011125

完全二叉樹6.3二叉樹的存儲結構二、二叉樹的鏈式存儲表示一、二叉樹的順序存儲表示#defineMAX_TREE_SIZE100//二叉樹的最大結點數typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0號單元存儲根結點SqBiTreebt;一、二叉樹的順序存儲表示用一組連續的存儲單元存放二叉樹的數據元素。結點在數組中的相對位置蘊含著結點之間的關系。二叉樹順序存儲結構

bt[16]若父結點在數組中i下標處，其左孩子在2*i處，右孩子在2*i+1處。11ABcFED

●●●●●●●●●124

8

9105637121314152h-1=24-1=15用一組連續的存儲單元存放二叉樹的數據元素。結點在數組中的相對位置蘊含著結點之間的關系。0000FE000DC0BA15141312111098765432100一般二叉樹必須按完全二叉樹的形式存儲，將造成存儲的浪費。typedefTElemTypeSqBiTree[MAX_TREE_SIZE+1];//0號單元未用SqBiTreebt例如:ABCDEF

ABDCEF

0123456789101112131401326typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0號單元存儲根結點二、二叉樹的鏈式存儲表示1.二叉鏈表2．三叉鏈表3．雙親鏈表4．線索鏈表ADEBCF

rootlchilddatarchild結點結構:1.二叉鏈表typedefstructBiTNode{//結點結構

TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;ADEBCF

root

2．三叉鏈表parent

lchilddatarchild結點結構:typedefstructTriTNode{//結點結構

TElemTypedata;structTriTNode*lchild,*rchild;//左右孩子指針

structTriTNode*parent;//雙親指針

}TriTNode,*TriTree;0123456dataparent結點結構:3．雙親鏈表LRTagLRRRLtypedefstruct

BPTNode

{//結點結構

TElemTypedata;

int

*parent;//指向雙親的指針

charLRTag;//左、右孩子標志域

}BPTNodetypedefstructBPTree{//樹結構

BPTNodenodes[MAX_TREE_SIZE];

intnum_node;//結點數目

introot;//根結點的位置

}BPTree6.4二叉樹的遍歷一、問題的提出二、先左后右的遍歷算法三、算法的遞歸描述四、中序遍歷算法的非遞歸描述五、遍歷算法的應用舉例遍歷：按某條搜索路線尋訪樹中每個結點且只被訪問一次。一、問題的提出“訪問”的含義可以很廣，如：輸出結點的信息等。查找某個結點，或對二叉樹中全部結點進行某種處理，就需要遍歷。

“遍歷”是任何類型均有的操作，對線性結構而言，只有一條搜索路徑(因為每個結點均只有一個后繼)，故不需要另加討論。而二叉樹是非線性結構，每個結點有兩個后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。對“二叉樹”而言，可以有三條搜索路徑1．先上后下的按層次遍歷；2．先左（子樹）后右（子樹）的遍歷；3．先右（子樹）后左（子樹）的遍歷。二、先左后右的遍歷算法按先左后右的原則，一般使用三種遍歷：先根遍歷(DLR):

訪問根結點，按先序遍歷左子樹，按先序遍歷右子樹。中根遍歷(LDR):

按中序遍歷左子樹，訪問根結點，按中序遍歷右子樹。后根遍歷(LRD):

按后序遍歷左子樹，按后序遍歷右子樹，訪問根結點。二叉樹為空時，執行空操作，即空二叉樹已遍歷完。遍歷算法例：先序遍歷：DLR中序遍歷：LDR后序遍歷：LRDADBCT1T2T3DLRADLRDLR>B>>D>>CDLR以先序遍歷DLR為例演示遍歷過程ABDCBDACDBCA三、算法的遞歸描述voidPreorder(BiTreeT,void(*visit)(TElemTypee)){//

先序遍歷二叉樹

//初始條件：二叉樹T存在，Visit是對結點操作的應用函數。修改算法6.1//操作結果：先序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次

if(T){//T不空

visit(T->data);

//先訪問根結點.如printf(“%c”,T->data)

Preorder(T->lchild,visit);

//再先序遍歷左子樹

Preorder(T->rchild,visit);//最后先序遍歷右子樹

}}四、中序遍歷算法的非遞歸描述voidInOrderTraverse1(BiTreeT,void(*Visit)(TElemType)){//采用二叉鏈表存儲結構，Visit是對數據元素操作的應用函數。修改算法6.3//中序遍歷二叉樹T的非遞歸算法(利用棧)，對每個數據元素調用函數VisitSqStackS;InitStack(S);//初始化棧Swhile(T||!StackEmpty(S))//當二叉樹T不空或者棧不空

{if(T)//二叉樹T不空

{//根指針進棧，遍歷左子樹

Push(S,T);//入棧根指針

T=T->lchild;//T指向其左孩子

}else//根指針退棧，訪問根結點，遍歷右子樹

{Pop(S,T);//出棧根指針

Visit(T->data);//訪問根結點

T=T->rchild;//T指向其右孩子

}}printf("\n");}T五、遍歷算法的應用舉例1、統計二叉樹中葉子結點的個數

(先序遍歷)2、求二叉樹的深度(后序遍歷)3、復制二叉樹(后序遍歷)4、建立二叉樹的存儲結構5、由遍歷序列確定二叉樹1、統計二叉樹中葉子結點的個數算法基本思想:

先序(或中序或后序)遍歷二叉樹，在遍歷過程中查找葉子結點，并計數。由此，需在遍歷算法中增添一個“計數”的參數，并將算法中“訪問結點”的操作改為：若是葉子，則計數器增1。void

CountLeaf

(BiTreeT,int&count){

if(T){

if((!T->lchild)&&(!T->rchild))count++;//對葉子結點計數

CountLeaf(T->lchild,count);

CountLeaf(T->rchild,count);}//if}//CountLeaf2、求二叉樹的深度(后序遍歷)算法基本思想:

從二叉樹深度的定義可知，二叉樹的深度應為其左、右子樹深度的最大值加1。由此，需先分別求得左、右子樹的深度，算法中“訪問結點”的操作為：求得左、右子樹深度的最大值，然后加1。int

Depth(BiTreeT){//返回二叉樹的深度

if(!T)depthval=0;else{depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);

depthval=1+(depthLeft>depthRight?depthLeft:depthRight);

}

returndepthval;}3、復制二叉樹其基本操作為：生成一個結點。根元素T左子樹右子樹根元素NEWT左子樹右子樹左子樹右子樹(后序遍歷)BiTNode

*GetTreeNode(TElemTypeitem,

BiTNode

*lptr,BiTNode*rptr){

if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))

exit(1);

T->data=item;

T->lchild=lptr;T->rchild=rptr;

returnT;}

生成一個二叉樹的結點(其數據域為item,左指針域為lptr,右指針域為rptr)BiTNode

*CopyTree(BiTNode*T){

if(!T)returnNULL;

if(T->lchild)

newlptr=CopyTree(T->lchild);//復制左子樹

elsenewlptr=NULL;

if(T->rchild)

newrptr=CopyTree(T->rchild);//復制右子樹

elsenewrptr=NULL;

newT=GetTreeNode(T->data,newlptr,newrptr);

returnnewT;}//CopyTreeABCDEFGHK^D^C^^B^H^^K^G^F^E^A例如：下列二叉樹的復制過程如下：newT4、建立二叉樹的存儲結構不同的定義方法相應有不同的存儲結構的建立算法

以字符串的形式根左子樹右子樹定義一棵二叉樹例如:ABCD以空白字符“”表示A(B(,C(,)),D(,))空樹只含一個根結點的二叉樹A以字符串“A”表示以下列字符串表示AB

C

D

ABCD算法執行過程舉例如下：ATBCD^^^^^scanf(&ch);//輸入結點的值

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

else{T=(BiTree)malloc(sizeof(BiTNode));//生成根結點

if(!T)exit(OVERFLOW);T->data=ch;CreateBiTree(T->lchild);//遞歸構造左子樹

CreateBiTree(T->rchild);//遞歸構造右子樹}}voidCreateBiTree(BiTree&T){voidCreateBiTree(BiTree&T)//算法6.4：按先序次序輸入二叉樹中結點的值(字符型)，構造二叉鏈表表示的二叉樹T。

僅知二叉樹的先序序列“abcdefg”

不能唯一確定一棵二叉樹，5、由遍歷序列確定二叉樹

如果同時已知二叉樹的中序序列“cbdaegf”，則會如何？

二叉樹的先序序列二叉樹的中序序列左子樹左子樹右子樹右子樹根根由二叉樹的先序和中序序列確定二叉樹abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列6.5

線索二叉樹

何謂線索二叉樹？線索鏈表的遍歷算法如何建立線索鏈表？一、何謂線索二叉樹？遍歷二叉樹的結果是，求得結點的一個線性序列。ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA指向該線性序列中的“前驅”和“后繼”的指針，稱作“線索”與其相應的二叉樹，稱作“線索二叉樹”包含“線索”的存儲結構，稱作“線索鏈表”ABCDEFGHK^D^

C^^B

E^意義：保存遍歷二叉樹后得到的線性序列，避免重復遍歷。對線索鏈表中結點的約定：

在二叉鏈表的結點中增加兩個標志域，規定如下：如此定義的二叉樹的存儲結構稱作“線索鏈表”。左標志ltag:0表示lchild指向左孩子結點

1表示lchild指向前驅結點右標志rtag:0表示rchild指向右孩子結點

1表示rchild指向后繼結點這樣,每個結點的存儲結構如下：LChildLtagDataRtagRChildtypedefstruct

BiThrNod{

TElemTypedata;

structBiThrNode*lchild,*rchild;//左右指針

PointerThrLTag,RTag;//左右標志}BiThrNode,*BiThrTree;線索鏈表的類型描述：

typedef

enum{

Link,Thread

}PointerThr;

//Link==0:指針，Thread==1:線索LChildLtagDataRtagRChild二、線索鏈表的遍歷算法:由于在線索鏈表中添加了遍歷中得到的“前驅”和“后繼”的信息，從而簡化了遍歷的算法。例如:對中序線索化鏈表的遍歷算法

※中序遍歷的第一個結點？左子樹上處于“最左下”（沒有左子樹）的結點。

※在中序線索化鏈表中結點的后繼？若無右子樹，則為后繼線索所指結點；否則為對其右子樹進行中序遍歷時訪問的第一個結點。LChildLtagDataRtagRChild二叉樹voidInOrderTraverse_Thr(BiThrTreeT,void(*Visit)(TElemType))

{//中序遍歷線索二叉樹T(頭結點)的非遞歸算法。算法6.5BiThrTreep;p=T->lchild;//p指向根結點

while(p!=T)

{

//空樹或遍歷結束時，p==T

while(p->LTag==Link)

//由根結點一直找到二叉樹的最左結點

p=p->lchild;

//p指向其左孩子

Visit(p->data);//訪問此結點

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

{

//p->rchild是線索(后繼)，且不是遍歷的最后一個結點

p=p->rchild;//p指向其后繼

Visit(p->data);//訪問后繼結點

}

//若p->rchild不是線索(是右孩子)，p指向右孩子，返回循環，找這棵子樹中序遍歷的第1個結點

p=p->rchild;

}}

typedef

enum{

Link,Thread

}PointerThr;

//Link==0:指針，Thread==1:線索LChildLtagDataRtagRChild

在中序遍歷過程中修改結點的左、右指針域，以保存當前訪問結點的“前驅”和“后繼”信息。遍歷過程中，附設指針pre,并始終保持指針pre指向剛剛訪問過的結點，指針p指向當前訪問的結點。即pre指向當前訪問結點的前驅。三、如何建立線索鏈表？BiThrTreepre;//全局變量，始終指向剛剛訪問過的結點

voidInThreading(BiThrTreep)

{//通過中序遍歷進行中序線索化，線索化之后pre指向最后一個結點。算法6.7if(p)//線索二叉樹不空

{InThreading(p->lchild);//遞歸左子樹線索化

if(!p->lchild)//沒有左孩子

{p->LTag=Thread;//左標志為線索(前驅)p->lchild=pre;//左孩子指針指向前驅

}if(!pre->rchild)//前驅沒有右孩子

{pre->RTag=Thread;//前驅的右標志為線索(后繼)pre->rchild=p;//前驅右孩子指針指向其后繼(當前結點p)}pre=p;//保持pre指向p的前驅

InThreading(p->rchild);//遞歸右子樹線索化

}}voidInOrderThreading(BiThrTree&Thrt,BiThrTreeT)

{//中序遍歷二叉樹T，并將其中序線索化，Thrt指向頭結點。算法6.6

if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))//生成頭結點不成功

exit(OVERFLOW);Thrt->LTag=Link;//建頭結點，左標志為指針

Thrt->RTag=Thread;//右標志為線索

Thrt->rchild=Thrt;//右孩子指針回指

if(!T)//若二叉樹T空，則左孩子指針回指

Thrt->lchild=Thrt;

else

//二叉樹T非空

{Thrt->lchild=T;//頭結點的左孩子指針指向根結點

pre=Thrt;//pre(前驅)的初值指向頭結點，全局變量

InThreading(T);

//中序遍歷進行中序線索化，pre指向中序遍歷的最后一個結點

pre->rchild=Thrt;//最后一個結點的右孩子指針指向頭結點

pre->RTag=Thread;//最后一個結點的右標志為線索

Thrt->rchild=pre;//頭結點的右孩子指針指向中序遍歷的最后一個結點

}}

6.6樹和森林的表示方法樹的三種存儲結構一、雙親表示法二、孩子鏈表表示法三、樹的二叉鏈表(孩子-兄弟）存儲表示法四、樹、森林與二叉樹的相互轉換ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5r=0n=7dataparent一、雙親表示法:

typedefstructPTNode{Elemdata;

intparent;//雙親位置域

}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intr,n;//根結點的位置和結點個數

}PTree;結點結構:樹結構:#defineMAX_TREE_SIZE100ABCDEFG0

A1

B

2

C

3

D

4

E

5

F

6

G

r=0n=7123456二、孩子鏈表表示法:parent

1000224datafirstchildABCDEFGABCEDFGrootABCEDFG

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

firstchilddatanextsibling結點結構typedefstructCSNode{Elemdata;

structCSNode

*firstchild,*nextsibling;}CSNode,*CSTree;CSTreeroot四、樹、森林與二叉樹的相互轉換1.樹轉換為二叉樹由于二叉樹可以用二叉鏈表表示，為了使一般樹也能用二叉鏈表表示，必須找出樹與二叉樹之間的關系。這樣，給定一棵樹，可以找到唯一的一棵二叉樹與之對應。(1)樹中所有相鄰兄弟之間加一條連線。(2)對樹中的每個結點，只保留其與第一個孩子結點之間的連線，刪去其與其它孩子結點之間的連線。(3)以樹的根結點為軸心，將整棵樹順時針旋轉一定的角度，使之結構層次分明。

I

A

B

C

DEF

G

H(b)

A

B

CDE

G

HFI(a)樹轉換為二叉樹ABEFCDGHI(d)ABCDEFGHI(c)注意：樹轉換為二叉樹后，根無右子樹。樹與二叉樹的對應樹的二叉鏈表(孩子-兄弟）存儲表示法二叉樹二叉鏈表存儲表示法2.森林轉換為二叉樹

（1）將森林中的每棵樹轉換成相應的二叉樹。（2）第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結點作為前一棵二叉樹根結點的右孩子，當所有二叉樹連在一起后，所得到的二叉樹就是由森林轉換得到的二叉樹。森林轉換為二叉樹的過程森林轉換后的二叉樹，其根結點有右孩子由森林轉換成二叉樹的轉換規則為:若F=Φ，則B=Φ；否則，由ROOT(T1)

對應得到B的根

root；由(t11,t12,…,t1m1)

對應得到LB；由(T2,T3,…,Tm)

對應得到RB。設森林

F=(T1,T2,…,Tm);T1=(root，t11,t12,…,t1m1);二叉樹

B=(root,LB,RB);由二叉樹轉換為森林的轉換規則為：若B=Φ，則F=Φ；否則，由root

對應得到ROOT(T1

)；由LB

對應得到T1中的子森林（t11,t12,…，t1m)；由RB

對應得到(T2,T3,…,Tn)。

3.二叉樹還原為樹或森林（1）若某結點是其雙親的左孩子，則把該結點的右孩子、右孩子的右孩子……都與該結點的雙親結點用線連起來。（2）刪掉原二叉樹中所有雙親結點與右孩子結點的連線。（3）整理由（1）、（2）兩步所得到的樹或森林。二叉樹到森林的轉換示例

設二叉樹

B=(root,LB,RB);森林

F=(T1,T2,…,Tm);

由此，樹的各種操作均可對應二叉樹的操作來完成。

應當注意的是，和樹對應的二叉樹，其左、右子樹的概念已改變為：

左是孩子，右是兄弟。6.7樹和森林的遍歷一、樹的遍歷二、森林的遍歷樹的遍歷可有三條搜索路徑:按層次遍歷:先根(次序)遍歷:后根(次序)遍歷:

若樹不空，則先訪問根結點，然后依次先根遍歷各棵子樹。

若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結點。

若樹不空，則自上而下自左至右訪問樹中每個結點。ABCDEFGHIJK

先根遍歷時頂點的訪問次序：ABEFCDGHIJK

后根遍歷時頂點的訪問次序：EFBCIJKHGDA

層次遍歷時頂點的訪問次序：ABCDEFGHIJK

BCDEFGHIJK1．森林中第一棵樹的根結點；2．森林中第一棵樹的子樹森林；3．森林中其它樹構成的森林。森林由三部分構成：1.先序遍歷森林的遍歷若森林不空，則訪問森林中第一棵樹的根結點；先序遍歷森林中第一棵樹的子樹森林；先序遍歷森林中(除第一棵樹之外)其余樹構成的森林。即：依次從左至右對森林中的每一棵樹進行先根遍歷。例如，P138圖6.17中森林的先序遍歷序列為ABCDEFGHIJ。２．中序遍歷若森林不空，則中序遍歷森林中第一棵樹的子樹森林；訪問森林中第一棵樹的根結點；中序遍歷森林中(除第一棵樹之外)其余樹構成的森林。即：依次從左至右對森林中的每一棵樹進行后根遍歷。森林的遍歷例如，P138圖6.17中森林的中序遍歷序列為BCDAFEHJIG。

樹的遍歷和二叉樹遍歷的對應關系？先根遍歷后根遍歷樹二叉樹森林先序遍歷先序遍歷中序遍歷中序遍歷6.8哈夫曼樹與應用

最優樹的定義

如何構造最優樹哈夫曼樹與應用

一、最優樹的定義樹的路徑長度定義為：

樹中每個結點的路徑長度之和。

結點的路徑長度定義為：

從根結點到該結點的路徑上分支的數目。

樹的帶權路徑長度定義為：

樹中所有葉子結點的帶權路徑長度之和

WPL(T)=

wklk(對所有葉子結點)。

在所有含n個葉子結點、并帶相同權值的m叉樹中，必存在一棵其帶權路徑長度取最小值的樹，稱為“最優樹”。例如：27975492WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21