第六章樹和二叉樹16.1樹的類型定義6.2二叉樹的類型定義6.3

二叉樹的存儲結(jié)構(gòu)6.4二叉樹的遍歷6.8

哈夫曼樹與哈夫曼編碼26.1樹的類型定義3數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。

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

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

數(shù)據(jù)關(guān)系R：4ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2樹根例如:5基本術(shù)語6結(jié)點:結(jié)點的度:樹的度:葉子結(jié)點:分支結(jié)點:數(shù)據(jù)元素+若干指向子樹的分支分支的個數(shù)樹中所有結(jié)點的度的最大值度為零的結(jié)點度大于零的結(jié)點DHIJM7(從根到結(jié)點的)路徑：孩子結(jié)點：一個結(jié)點的后繼稱為該結(jié)點的孩子結(jié)點。雙親結(jié)點:

由從根到該結(jié)點所經(jīng)分支和結(jié)點構(gòu)成ABCDEFGHIJMKL一個結(jié)點稱其為其后繼結(jié)點的雙親結(jié)點。兄弟結(jié)點：同一雙親結(jié)點下的孩子結(jié)點互稱為兄弟結(jié)點。堂兄弟：雙親互為兄弟的兩個結(jié)點互稱為堂兄弟。8祖先結(jié)點

:子孫結(jié)點：一個結(jié)點的所有子樹中的結(jié)點稱之為該結(jié)點的子孫結(jié)點。ABCDEFGHIJMKL從樹根結(jié)點到達一個結(jié)點的路徑上的所有結(jié)點稱為該結(jié)點的祖先結(jié)點結(jié)點的層次：假設(shè)樹的根結(jié)點的層次為

1，第l層的結(jié)點的子樹根結(jié)點的層次為l＋1樹的深度：樹中結(jié)點的最大層次稱為樹的深度（或高度）9任何一棵非空樹是一個二元組

Tree=（root，F(xiàn)）其中：root被稱為根結(jié)點

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

基本操作：查找類

插入類刪除類11

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

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

Parent(T,cur_e)//求當(dāng)前結(jié)點的雙親結(jié)點LeftChild(T,cur_e)//求當(dāng)前結(jié)點的最左孩子

RightSibling(T,cur_e)//求當(dāng)前結(jié)點的右兄弟TreeEmpty(T)//判定樹是否為空樹

TreeDepth(T)//求樹的深度TraverseTree(T,Visit())//遍歷12InitTree(&T)//初始化置空樹

插入類：CreateTree(&T,definition)//按定義構(gòu)造樹Assign(T,cur_e,value)//給當(dāng)前結(jié)點賦值InsertChild(&T,&p,i,c)//將以c為根的樹插入為結(jié)點p的第i棵子樹13

ClearTree(&T)//將樹清空

刪除類：DestroyTree(&T)//銷毀樹的結(jié)構(gòu)DeleteChild(&T,&p,i)//刪除結(jié)點p的第i棵子樹14(１)有確定的根；(２)樹根和子樹根之間為有向關(guān)系。有向樹：有序樹：子樹之間存在確定的次序關(guān)系。無序樹：子樹之間不存在確定的次序關(guān)系。15ABCDEFGHIJMKL例如:16對比樹型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點17~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結(jié)構(gòu)樹型結(jié)構(gòu)第一個數(shù)據(jù)元素

(無前驅(qū))

根結(jié)點

(無前驅(qū))最后一個數(shù)據(jù)元素

(無后繼)多個葉子結(jié)點

(無后繼)其它數(shù)據(jù)元素(一個前驅(qū)、一個后繼)其它數(shù)據(jù)元素(一個前驅(qū)、多個后繼)186.2

二叉樹的類型定義19

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

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

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());23

InitBiTree(&T);Assign(T,&e,value);

CreateBiTree(&T,definition);

InsertChild(T,p,LR,c);24ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);25二叉樹

的重要特性26

性質(zhì)1：

在二叉樹的第i

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

歸納基：

歸納假設(shè)：

歸納證明：i=1

層時，只有一個根結(jié)點：

2i-1=20=1；假設(shè)對所有的j，1≤j

i，命題成立；二叉樹上每個結(jié)點至多有兩棵子樹，則第i層的結(jié)點數(shù)=2i-22=2i-1

。27性質(zhì)2：

深度為k的二叉樹上至多含2k-1個結(jié)點（k≥1）。證明：基于上一條性質(zhì)，深度為k的二叉樹上的結(jié)點數(shù)至多為

20+21+

+2k-1=2k-1

。28

性質(zhì)3：

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

2

的結(jié)點，則必存在關(guān)系式：n0=n2+1。證明：設(shè)二叉樹上結(jié)點總數(shù)n=n0+n1+n2又二叉樹上分支總數(shù)b=n1+2n2

而b=n-1=n0+n1+n2-1由此，n0=n2+1。29兩類特殊的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個結(jié)點的二叉樹。完全二叉樹：樹中所含的n個結(jié)點和滿二叉樹中編號為1至n的結(jié)點一一對應(yīng)。123456789101112131415abcdefghij30

性質(zhì)4：

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

log2n+1。證明：設(shè)完全二叉樹的深度為k則根據(jù)第二條性質(zhì)得2k-1≤n<2k

即

k-1≤log2n<k

因為k只能是整數(shù)，因此，

k=log2n

+1。31性質(zhì)5：若對含n個結(jié)點的完全二叉樹從上到下且從左至右進行1

至n

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

的結(jié)點：

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

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

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

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

否則，編號為2i+1的結(jié)點為其右孩子結(jié)點。326.3二叉樹的存儲結(jié)構(gòu)二、二叉樹的鏈?zhǔn)酱鎯Ρ硎疽?、二叉樹的順序存儲表?3#defineMAX_TREE_SIZE100//二叉樹的最大結(jié)點數(shù)typedef

TElemType

SqBiTree[MAX_TREE_SIZE];//0號單元存儲根結(jié)點SqBiTree

bt;一、二叉樹的順序存儲表示34例如:ABCDEF

ABDCEF

012345678910111213140132635二、二叉樹的鏈?zhǔn)酱鎯Ρ硎?.二叉鏈表2．三叉鏈表3．雙親鏈表4．線索鏈表36ADEBCFrootlchilddatarchild結(jié)點結(jié)構(gòu):1.二叉鏈表37typedef

struct

BiTNode

{//結(jié)點結(jié)構(gòu)

TElemTypedata;

struct

BiTNode

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

BiTNode,*BiTree;lchilddatarchild結(jié)點結(jié)構(gòu):C語言的類型描述如下:38ADEBCFroot2．三叉鏈表parent

lchilddatarchild結(jié)點結(jié)構(gòu):39

typedef

struct

TriTNode

{//結(jié)點結(jié)構(gòu)

TElemTypedata;

struct

TriTNode

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

struct

TriTNode

*parent;//雙親指針

}

TriTNode,*TriTree;parent

lchilddatarchild結(jié)點結(jié)構(gòu):C語言的類型描述如下:400123456dataparent結(jié)點結(jié)構(gòu):3．雙親鏈表LRTagLRRRL41

typedef

struct

BPTNode

{//結(jié)點結(jié)構(gòu)

TElemTypedata;

int

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

charLRTag;//左、右孩子標(biāo)志域

}

BPTNode

typedef

struct

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

BPTNodenodes[MAX_TREE_SIZE];

int

num_node;//結(jié)點數(shù)目

introot;//根結(jié)點的位置

}

BPTree426.4二叉樹的遍歷43一、問題的提出二、先左后右的遍歷算法三、算法的遞歸描述四、中序遍歷算法的非遞歸描述五、遍歷算法的應(yīng)用舉例44

順著某一條搜索路徑巡訪二叉樹中的結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次。一、問題的提出“訪問”的含義可以很廣，如：輸出結(jié)點的信息等。45

“遍歷”是任何類型均有的操作，對線性結(jié)構(gòu)而言，只有一條搜索路徑(因為每個結(jié)點均只有一個后繼)，故不需要另加討論。而二叉樹是非線性結(jié)構(gòu)，每個結(jié)點有兩個后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。46

對“二叉樹”而言，可以有三條搜索路徑：1．先上后下的按層次遍歷；2．先左（子樹）后右（子樹）的遍歷；3．先右（子樹）后左（子樹）的遍歷。47二、先左后右的遍歷算法先（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法48

若二叉樹為空樹，則空操作；否則，（1）訪問根結(jié)點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。先（根）序的遍歷算法：49

若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結(jié)點；（3）中序遍歷右子樹。中（根）序的遍歷算法：50

若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點。后（根）序的遍歷算法：51三、算法的遞歸描述voidPreorder(BiTreeT,

void(*visit)(TElemType&e)){//

先序遍歷二叉樹

if(T){

visit(T->data);//訪問結(jié)點

Preorder(T->lchild,visit);//遍歷左子樹

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

}}52四、中序遍歷算法的非遞歸描述BiTNode

*GoFarLeft(BiTreeT,Stack*S){

if(!T)returnNULL;

while(T->lchild){Push(S,T);T=T->lchild;

}

returnT;}53void

Inorder_I(BiTreeT,void(*visit)(TelemType&e)){

Stack*S;

t=GoFarLeft(T,S);//找到最左下的結(jié)點

while(t){

visit(t->data);

if(t->rchild)t=

GoFarLeft(t->rchild,S);

elseif(!StackEmpty(S))//棧不空時退棧

t=Pop(S);

elset=NULL;//

棧空表明遍歷結(jié)束

}//while}//Inorder_I

54五、遍歷算法的應(yīng)用舉例1、統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)

(先序遍歷)2、求二叉樹的深度(后序遍歷)3、復(fù)制二叉樹(后序遍歷)4、建立二叉樹的存儲結(jié)構(gòu)551、統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)算法基本思想:

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

CountLeaf

(BiTreeT,int&count){

if(T){

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

CountLeaf(T->lchild,count);

CountLeaf(T->rchild,count);}//if}//CountLeaf572、求二叉樹的深度(后序遍歷)算法基本思想:從二叉樹深度的定義可知，二叉樹的深度應(yīng)為其左、右子樹深度的最大值加1。由此，需先分別求得左、右子樹的深度，算法中“訪問結(jié)點”的操作為：求得左、右子樹深度的最大值，然后加1。

首先分析二叉樹的深度和它的左、右子樹深度之間的關(guān)系。58int

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

if(!T)depthval=0;else{

depthLeft=Depth(T->lchild);

depthRight=Depth(T->rchild);

depthval=1+(depthLeft>depthRight?

depthLeft:depthRight);

}

return

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

*GetTreeNode(TElemType

item,

BiTNode

*lptr,BiTNode

*rptr){

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

exit(1);

T->data=item;

T->lchild=

lptr;T->rchild=

rptr;

returnT;}

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

*CopyTree(BiTNode

*T){

if(!T)returnNULL;

if(T->lchild)

newlptr=

CopyTree(T->lchild);//復(fù)制左子樹

else

newlptr=NULL;

if(T->rchild)

newrptr

=

CopyTree(T->rchild);//復(fù)制右子樹

else

newrptr=NULL;

newT=GetTreeNode(T->data,newlptr,

newrptr);

return

newT;}//CopyTree62ABCDEFGHK^D^

C^^B^H^^K^G^F^E^A例如：下列二叉樹的復(fù)制過程如下：newT634、建立二叉樹的存儲結(jié)構(gòu)不同的定義方法相應(yīng)有不同的存儲結(jié)構(gòu)的建立算法64

以字符串的形式根左子樹右子樹定義一棵二叉樹例如:ABCD以空白字符“

”表示A(B(,C(,)),D(,))空樹只含一個根結(jié)點的二叉樹A以字符串“A

”表示以下列字符串表示65Status

CreateBiTree(BiTree

&T)

{

scanf(&ch);

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

else{

if(!(T=(BiTNode

*)malloc(sizeof(BiTNode))))

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

CreateBiTree(T->lchild);//構(gòu)造左子樹

CreateBiTree(T->rchild);//構(gòu)造右子樹

}

returnOK;}//CreateBiTree66AB

C

D

ABCD上頁算法執(zhí)行過程舉例如下：ATBCD^^^^^676.8哈夫曼樹與

哈夫曼編碼

最優(yōu)樹的定義

如何構(gòu)造最優(yōu)樹

前綴編碼

68

一、最優(yōu)樹的定義樹的路徑長度定義為：

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

從根結(jié)點到該結(jié)點的路徑上分支的數(shù)目。69樹的帶權(quán)路徑長度定義為：