(1.7)-第六章 數(shù)據(jù)結(jié)構(gòu)樹和二叉樹

第六章

樹和二叉樹6.1樹的定義和基本術(shù)語6.2二叉樹6.3遍歷二叉樹和線索二叉樹6.4樹和森林6.6

赫夫曼樹及其應(yīng)用6.1樹的定義和基本術(shù)語樹（Tree）是n（n>=0）個結(jié)點的有限集。在任意一棵非空樹中:1）由且僅有一個特定的稱為根（Root）的結(jié)點；2）當(dāng)n>1時，其余結(jié)點可分為m（m>0）個互不相交的有限集T1，T2，…，Tm，其中每一個集合本身又是一棵樹，并且稱為根的子樹。其抽象數(shù)據(jù)類型定義如下：數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。

若D為空集，則稱為空樹。若D僅含一個數(shù)據(jù)元素，則R為空集，否則R={H}，H是如下二元關(guān)系:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root；它在H下無前驅(qū)(2)若D-{root}≠?，則存在D-{root}的一個劃分D1,D2,…,Dm（m>0)，對任意j≠

k，有Dj∩

Dk=?,且對任意的i，唯一存在數(shù)據(jù)元素xi∈Di,有<root,xi>∈H;(3)對應(yīng)于D-{root}的劃分，H-{<root,x1>，…<root,xm>}有惟一的一個劃分H1,…Hm(m>0)，對任意j≠

k，有Hj∩

Hk=?,且對任意的i，Hi是Di上的關(guān)系，（Di,{Hi})是一棵符合本定義的樹，稱為根root的子樹。

數(shù)據(jù)關(guān)系R：ADTTree{

基本操作：查找類

插入類刪除類

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())//遍歷InitTree(&T)//初始化置空樹

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

ClearTree(&T)//將樹清空

刪除類：DestroyTree(&T)//銷毀樹的結(jié)構(gòu)DeleteChild(&T,&p,i)//刪除結(jié)點p的第i棵子樹ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2樹根例如:(１)有確定的根；(２)樹根和子樹根之間為有向關(guān)系。有向樹：有序樹：子樹之間存在確定的次序關(guān)系。無序樹：子樹之間不存在確定的次序關(guān)系。對比樹型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結(jié)構(gòu)樹型結(jié)構(gòu)第一個數(shù)據(jù)元素

(無前驅(qū))

根結(jié)點

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

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

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

由從根到該結(jié)點所經(jīng)分支和結(jié)點構(gòu)成ABCDEFGHIJMKL假設(shè)根結(jié)點的層次為1，根的孩子為第二層。第l層的結(jié)點的子樹根結(jié)點的層次為l+1樹中葉子結(jié)點所在的最大層次任何一棵非空樹是一個二元組

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

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

6.2.1

二叉樹的定義

6.2.2二叉樹的性質(zhì)

6.2.3二叉樹的存儲結(jié)構(gòu)6.2.1二叉樹的定義二叉樹或為空樹，或是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。ABCDEFGHK根結(jié)點左子樹右子樹數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。

若D=?，則R=?，稱BinaryTree為空二叉樹。否則，R={H}，H是如下二元關(guān)系:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root；它在H下無前驅(qū)(2)若D-{root}≠?，則存在D-{root}={

Dl,Dr},且Dl∩Dr=?;(3)若Dl≠?

，則Dl中存在惟一的元素xl,<root,xl>∈H，且存在Dl上的關(guān)系Hl∈H；若Dr

≠?

，則Dr中存在惟一的元素xr,<root,xr>∈H，且存在Dr上的關(guān)系Hr∈H；H={<root,xl>,<root,xr>,Hl,HR}

；（4）(Dl,{Hl})是一棵符合本定義的二叉樹，稱為根的左子樹，(Dr,{Hr})是一棵符合本定義的二叉樹，稱為根的右子樹，

數(shù)據(jù)關(guān)系R：ADTBinaryTree{二叉樹的五種基本形態(tài)：N空樹只含根結(jié)點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);

具體內(nèi)容見課本

P121-P123

6.2.2二叉樹的性質(zhì)

性質(zhì)1：

在二叉樹的第i

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

歸納基：

歸納假設(shè)：

歸納證明：i=1

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

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

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

2=2i-1

。歸納假設(shè)性質(zhì)2：

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

20+21+

+2k-1=2k-1。

性質(zhì)3：

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

2

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

n=n0+n1+n2，

其中n1為度為1的結(jié)點數(shù)。又二叉樹上分支總數(shù)b=n1+2n2

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

性質(zhì)4：

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

log2n

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

2k-1-1<n≤2k-1

或2k-1≤n<2k

即

k-1≤log2n<k因為k只能是整數(shù)，因此，

k=log2n

+1。性質(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é)點?！筰/2

」ii+12i2i+12i+32i+2LCHILD(i)LCHILD(i+1)RCHILD(i)RCHILD(i+1)(a)結(jié)點i和i+1在同一層上；i+12i+22i+3i2i2i+1(b)結(jié)點i和i+1不在同一層上；圖6.5完全二叉樹中結(jié)點i和i+1的左、右孩子……6.2.3二叉樹的存儲結(jié)構(gòu)二、二叉樹的鏈?zhǔn)酱鎯Ρ硎疽?、二叉樹的順序存儲表?defineMAX_TREE_SIZE100//二叉樹的最大結(jié)點數(shù)typedef

TElemTypeSqBiTree[MAX_TREE_SIZE];//0號單元存儲根結(jié)點SqBiTreebt;一、二叉樹的順序存儲表示例如:ABCDEF

ABDCEF

0123456789101112131401326二、二叉樹的鏈?zhǔn)酱鎯Ρ硎?.二叉鏈表2．三叉鏈表3．雙親鏈表4．線索鏈表ADEBCF

rootlchilddatarchild結(jié)點結(jié)構(gòu):1.二叉鏈表typedef

struct

BiTNode

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

TElemTypedata;

struct

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

BiTNode,*BiTree;lchilddatarchild結(jié)點結(jié)構(gòu):C語言的類型描述如下:ADEBCF

root

2．三叉鏈表parent

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

typedef

struct

TriTNode

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

TElemTypedata;

struct

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

struct

TriTNode

*parent;//雙親指針

}

TriTNode,*TriTree;parent

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

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ù)目

int

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

}

BPTree6.3遍歷二叉樹和線索二叉樹一、問題的提出二、先左后右的遍歷算法三、算法的遞歸描述四、中序遍歷算法的非遞歸描述五、遍歷算法的應(yīng)用舉例6.3.1遍歷二叉樹何謂二叉樹的遍歷？一、問題的提出“訪問”的含義可以很廣，如：輸出結(jié)點的信息等。

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

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

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

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

若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（遞歸）（2）后序遍歷右子樹；（遞歸）（3）訪問根結(jié)點。后（根）序的遍歷算法：ABCDEFGHK例如：對下面二叉樹的各種遍歷結(jié)果如下：前序遍歷結(jié)果：ABCDEFGHK中序遍歷結(jié)果：BDCAHGKFE后序遍歷結(jié)果：DCBHKGFEAStatusPreOrderTraverse(BiTreeeT,Status(*Visit)(TElemTypee)){//采用二叉鏈表存儲結(jié)構(gòu)，Visit是對數(shù)據(jù)元素操作的應(yīng)用函//數(shù)，先序遍歷二叉樹T的遞歸算法，對每個數(shù)據(jù)元素調(diào)用函數(shù)Visit。最簡單的Visit函數(shù)是：//StatusPrintElement(TElemTypee){//輸出元素e的值//printf(e);//實用時，加上格式串//returnOK;//}//調(diào)用實例：PreOrderTraverse(T,PrintElement);if(T){if(Visit(T->data))if(PreOrderTraverse(T->lchild,Visit))if(PreOrderTraverse(T->rchild,Visit))returnOK;returnERROR;}elsereturnOK;}//PreOrderTraverse算法6.1StatusInOrderTraverse(BiTreeeT,Status(*Visit)(TElemTypee)){

//采用二叉鏈表存儲結(jié)構(gòu)，Visit是對數(shù)據(jù)元素操作的應(yīng)用函//數(shù)。中序遍歷二叉樹T的非遞歸算法，對每個數(shù)據(jù)元素調(diào)用//函數(shù)Visit。

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

while(!StackEmpty(S)){while(GetTop(S,p))&&p)Push(S,p->lchild);//向左走到盡頭

Pop(S,p);//空指針退棧

if(!StackEmpty(S)){//訪問結(jié)點，向右一步

Pop(S,p);if(!Visit(p->data))returnERROR;Push(S,p->rchild);}//if}//WhilereturnOK;}//InOrderTraverse算法6.2StatusInOrderTraverse(BiTreeeT,Status(*Visit)(TElemTypee)){

//采用二叉鏈表存儲結(jié)構(gòu)，Visit是對數(shù)據(jù)元素操作的應(yīng)用函//數(shù)。中序遍歷二叉樹T的非遞歸算法，對每個數(shù)據(jù)元素調(diào)用//函數(shù)Visit。

InitStack(S);p=T;while(p||!StackEmpty(S)){if(p){Push(S,p);p=p->lchild);//根指針進棧，遍歷左子樹

else{//根指針退棧，訪問根結(jié)點，遍歷右子樹

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

}//else}//WhilereturnOK;}//InOrderTraverse算法6.3ABCDEFG‘遍歷’是二叉樹各種操作的基礎(chǔ)，也可在遍歷過程中生成結(jié)點，建立二叉樹的存儲結(jié)構(gòu)。例如：對下面所示二叉樹，按下列次序順序讀入字符ABC??

DE?

G?

?

F?

??其中?表示空格字符，可建立相應(yīng)的二叉鏈表。StatusCreateBiTree(BiTreee&T){

//按先序次序輸入二叉樹中結(jié)點的值（一個字符），空格字符表示空樹。//構(gòu)造二叉鏈表表示的二叉樹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;}//CreateBiTree算法6.4例如:ABCD以字符“?”表示A(B(?,C(?,?)),D(?,?))空樹只含一個根結(jié)點的二叉樹A以字符串“A??”表示以下列字符串表示ALARBLBRCLCRDLDRAB

C

D

ABCD上頁算法執(zhí)行過程舉例如下：ATBCD^^^^^

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

不能唯一確定一棵二叉樹，由二叉樹的先序和中序序列建二叉樹

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

二叉樹的先序序列二叉樹的中序序列左子樹左子樹右子樹右子樹根根abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列void

CrtBT(BiTree&T,charpre[],charino[],

int

ps,intis,intn){//已知pre[ps..ps+n-1]為二叉樹的先序序列，//ins[is..is+n-1]為二叉樹的中序序列，本算//法由此兩個序列構(gòu)造二叉鏈表

if(n==0)T=NULL;

else{k=Search(ino,pre[ps]);//在中序序列中查詢

if(k==-1)T=NULL;

else{…

…}}//}//CrtBTT=(BiTNode*)malloc(sizeof(BiTNode));T->data=pre[ps];if(k==is)T->Lchild=NULL;else

CrtBT(T->Lchild,pre[],ino[],ps+1,is,k-is);if(k=is+n-1)T->Rchild=NULL;else

CrtBT(T->Rchild,pre[],ino[],ps+1+(k-is),k+1,n-(k-is)-1);三、算法的遞歸描述voidPreorder(BiTreeT,

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

先序遍歷二叉樹

if(T){

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

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

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

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

*GoFarLeft(BiTreeT,Stack*S){

if(!T)returnNULL;

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

}

returnT;}void

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;//

?？毡砻鞅闅v結(jié)束}//while}//Inorder_I

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

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

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

CountLeaf

(BiTreeT,int&count){

if(T){

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

CountLeaf(T->lchild,count);

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

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

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

if(!T)depthval=0;else{

depthLeft=Depth(T->lchild);

depthRight=Depth(T->rchild);

depthval=1+(depthLeft>depthRight?

depthLeft:depthRight);

}

return

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

*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)BiTNode

*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;}//CopyTreeABCDEFGHK^D^

C^^B^H^^K^G^F^E^A例如：下列二叉樹的復(fù)制過程如下：newT4、建立二叉樹的存儲結(jié)構(gòu)

不同的定義方法相應(yīng)有不同的存儲結(jié)構(gòu)的建立算法。

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

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

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

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;}//CreateBiTreeAB

C

D

ABCD上頁算法執(zhí)行過程舉例如下：ATBCD^^^^^

按給定的表達(dá)式建相應(yīng)二叉樹

由先綴表示式建二叉樹例如：已知表達(dá)式的先綴表示式

-×+

abc/de

由原表達(dá)式建二叉樹例如：已知表達(dá)式(a+b)×c–d/e對應(yīng)先綴表達(dá)式-×+

abc/de的二叉樹abcde-×+/特點：

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

運算符為分支結(jié)點scanf(&ch);if(In(ch,字母集))建葉子結(jié)點;else{建根結(jié)點;

遞歸建左子樹;

遞歸建右子樹;}由先綴表示式建樹的算法的基本操作：a+b(a+b)×c–d/ea+b×c分析表達(dá)式和二叉樹的關(guān)系:ab+abc×+abc×+(a+b)×cabcde-×+/基本操作:scanf(&ch);if(In(ch,字母集)){建葉子結(jié)點;暫存;}elseif(In(ch,運算符集)){和前一個運算符比較優(yōu)先數(shù);

若當(dāng)前的優(yōu)先數(shù)“高”，則暫存;

否則建子樹;}void

CrtExptree(BiTree

&T,charexp[]){

InitStack(S);Push(S,

#

);InitStack(PTR);p=exp;ch=*p;

while(!(GetTop(S)==

#

&&ch==

#

)){if(!IN(ch,OP))CrtNode(t,ch);//建葉子結(jié)點并入棧

else{}//Switch

if(ch!=

#

){p++;ch=*p;}

}//whilePop(PTR,T);}//CrtExptree……

switch(ch){case

(

:Push(S,ch);break;

case

)

:Pop(S,c);while(c!=

(

){

CrtSubtree(t,c);//建二叉樹并入棧

Pop(S,c)}

break;

defult:}//switch……while(!Gettop(S,c)&&(precede(c,ch))){

CrtSubtree(t,c);Pop(S,c);}if(ch!=

#

)Push(S,ch);

break;建葉子結(jié)點的算法為：void

CrtNode(BiTree&T,charch){T=(BiTNode*)malloc(sizeof(BiTNode));T->data=char;T->lchild=T->rchild=NULL;

Push(PTR,T);}建子樹的算法為：void

CrtSubtree(Bitree&T,charc){T=(BiTNode*)malloc(sizeof(BiTNode));T->data=c;Pop(PTR,rc);T->rchild=rc;Pop(PTR,lc);T->lchild=lc;

Push(PTR,T);}6.3.2線索二叉樹

何謂線索二叉樹？

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

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA指向該線性序列中的“前驅(qū)”和“后繼”的指針，稱作“線索”與其相應(yīng)的二叉樹，稱作“線索二叉樹”包含“線索”的存儲結(jié)構(gòu)，稱作“線索鏈表”ABCDEFGHK^D^

C^^B

E^對線索鏈表中結(jié)點的約定：在二叉鏈表的結(jié)點中增加兩個標(biāo)志域LTag

和RTag并作如下規(guī)定：若該結(jié)點的左子樹不空，則Lchild域的指針指向其左子樹，且左標(biāo)志域LTag的值為0“指針Link”；否則，Lchild域的指針指向其“前驅(qū)”，且左標(biāo)志LTag的值為1“線索Thread”

。若該結(jié)點的右子樹不空，則rchild域的指針指向其右子樹，且右標(biāo)志域RTag的值為0“指針Link”；否則，rchild域的指針指向其“后繼”，且右標(biāo)志RTag的值為1“線索Thread”。

如此定義的二叉樹的存儲結(jié)構(gòu)稱作“線索鏈表”。以某種次序遍歷使其變?yōu)榫€索二叉樹的過程叫做‘線索化’例如，下圖為一中序線索二叉樹ABCDEFGHKtypedef

struct

BiThrNod

{

TElemTypedata;

struct

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

PointerThrLTag,RTag;//左右標(biāo)志}

BiThrNode,*BiThrTree;線索鏈表的類型描述：

typedef

enum

{

Link,Thread

}PointerThr;

//Link==0:指針，Thread==1:線索二、線索鏈表的遍歷算法:

for(p=

firstNode(T);p;p=Succ(p))Visit(p);由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡化了遍歷的算法。例如:

對中序線索化鏈表的遍歷算法

※中序遍歷的第一個結(jié)點？

※在中序線索化鏈表中結(jié)點的后繼？左子樹上處于“最左下”（沒有左子樹）的結(jié)點。若無右子樹，則為后繼線索所指結(jié)點；否則為對其右子樹進行中序遍歷時訪問的第一個結(jié)點。具體算法見算法6.5void

InOrderTraverse_Thr(BiThrTreeT,

void(*Visit)(TElemTypee)){p=T->lchild;//p指向根結(jié)點

while(p!=T){//空樹或遍歷結(jié)束時，p==Twhile(p->LTag==Link)p=p->lchild;if(!Visit(p->data))returnerror//訪問其左子樹為空的結(jié)點

while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;Visit(p->data);//訪問后繼結(jié)點

}

p=p->rchild;//p進至其右子樹根

}}//InOrderTraverse_Thr算法6.5在中序遍歷過程中修改結(jié)點的左、右指針域，以保存當(dāng)前訪問結(jié)點的“前驅(qū)”和“后繼”信息。遍歷過程中，附設(shè)指針pre,并始終保持指針pre指向當(dāng)前訪問的、指針p所指結(jié)點的前驅(qū)。三、如何建立線索鏈表？Status

InOrderThreading(BiThrTree

&Thrt,

BiThrTreeT){//構(gòu)建中序線索鏈表

if(!(Thrt=(BiThrTree)malloc(

sizeof(BiThrNode))))

exit(OVERFLOW);

Thrt->LTag=Link;Thrt->RTag=Thread;//建頭結(jié)點

Thrt->rchild=Thrt;

//右指針回指

returnOK;}//InOrderThreading

……算法6.6if(!T)Thrt->lchild=Thrt;//若二叉樹空,則左指針回指else{

Thrt->lchild=T;pre=Thrt;

InThreading(T);//中序遍歷進行線索化

pre->rchild=Thrt;//最后一個結(jié)點線索化

pre->RTag=Thread;

Thrt->rchild=pre;}void

InThreading(BiThrTreep)

{

if(p){//對以p為根的非空二叉樹進行線索化

InThreading(p->lchild);

//左子樹線索化

if(!p->lchild)//建前驅(qū)線索

{

p->LTag=Thread;p->lchild=pre;}

if(!pre->rchild)//建后繼線索

{

pre->RTag=Thread;pre->rchild=p;}

pre=p;//保持pre指向p的前驅(qū)

InThreading(p->rchild);

//右子樹線索化

}//if}//InThreading算法6.76.4

樹和森林6.4.1樹的存儲結(jié)構(gòu)一、雙親表示法二、孩子鏈表表示法三、樹的二叉鏈表(孩子-兄弟）存儲表示法ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

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

typedef

struct

PTNode

{

Elemdata;

int

parent;//雙親位置域

}

PTNode;

dataparent結(jié)點結(jié)構(gòu):C語言的類型描述:typedef

struct{

PTNodenodes[MAX_TREE_SIZE];

int

r,n;//根結(jié)點的位置和結(jié)點個數(shù)

}

PTree;樹結(jié)構(gòu):ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

4r=0n=7

datafirstchild

123456二、孩子鏈表表示法:-1000224typedef

struct

CTNode

{

int

child;

struct

CTNode

*next;

}*ChildPtr;孩子結(jié)點結(jié)構(gòu):

childnextC語言的類型描述:Next:指向下一孩子結(jié)點的指針

typedef

struct{

Elemdata;

ChildPtrfirstchild;//孩子鏈的頭指針

}

CTBox;雙親結(jié)點結(jié)構(gòu)

datafirstchildtypedef

struct{

CTBoxnodes[MAX_TREE_SIZE];

int

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

}

CTree;樹結(jié)構(gòu):ABCDEFG

ABCEDFGrootABCEDFG

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

struct

CSNode{

Elemdata;

struct

CSNode

*firstchild,*nextsibling;}

CSNode,*CSTree;C語言的類型描述:結(jié)點結(jié)構(gòu):

firstchilddatanextsibling其中，firstchild：指向左邊第一個子結(jié)點的指針,nextsibling：指向右邊第一個兄弟結(jié)點的指針。

6.4.2

森林與二叉樹的轉(zhuǎn)換設(shè)森林

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

B=(LBT,Node(root),RBT);1、由森林轉(zhuǎn)換成二叉樹的轉(zhuǎn)換規(guī)則為:若F=Φ，則B=Φ；否則，由ROOT(T1)

對應(yīng)得到Node(root)；

由(t11,t12,…,t1m)

對應(yīng)得到LBT；

由(T2,T3,…,Tn

)

對應(yīng)得到RBT。2、由二叉樹轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為：若B=Φ，則F=Φ；否則，由Node(root)

對應(yīng)得到ROOT(T1

)；

由LBT

對應(yīng)得到(t11,t12,…，t1m)；

由RBT

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

由此，樹的各種操作均可對應(yīng)二叉樹的操作來完成。

應(yīng)當(dāng)注意的是，和樹對應(yīng)的二叉樹，其左、右子樹的概念已改變?yōu)椋?/p>

左是孩子，右是兄弟。由于樹的根結(jié)點無兄弟，因此對應(yīng)二叉樹的根結(jié)點無右子樹。ABCDE樹ABCDE二叉樹存儲對應(yīng)解釋存儲解釋∧AB∧CC∧D∧∧A∧E∧B∧∧E∧B∧∧AC∧D∧∧E∧∧D∧樹與二叉樹的對應(yīng)關(guān)系示例森林與二叉樹的對應(yīng)關(guān)系示例ABCDEFGHIJABCDEFGHIJABCDEFGHIJ森林與二叉樹對應(yīng)樹與二叉樹對應(yīng)樹根相連6.4.3樹和森林的遍歷一、樹的遍歷二、森林的遍歷三、樹的遍歷的應(yīng)用樹的遍歷可有三條搜索路徑:按層次遍歷:先根(次序)遍歷:后根(次序)遍歷:若樹不空，則先訪問根結(jié)點，然后依次先根遍歷各棵子樹。若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點。若樹不空，則自上而下自左至右訪問樹中每個結(jié)點。ABCDEFGHIJK先根遍歷時頂點的訪問次序：ABEFCDGHIJK后根遍歷時頂點的訪問次序：EFBCIJKHGDA層次遍歷時頂點的訪問次序：ABCDEFGHIJK

BCDEFGHIJK1．森林中第一棵樹的根結(jié)點；2．森林中第一棵樹的子樹森林；3．森林中其它樹構(gòu)成的森林。森林由三部分構(gòu)成：1.先序遍歷森林森林的遍歷若森林不空，則可按下述規(guī)則遍歷之：（1）訪問森林中第一棵樹的根結(jié)點；（2）先序遍歷森林中第一棵樹的子樹森林；（3）先序遍歷森林中(除第一棵樹之外)其余樹構(gòu)成的森林。即：依次從左至右對森林中的每一棵樹進行先根遍歷。２．中序遍歷森林

若森林不空，則可按下述規(guī)則遍歷之：（1）中序遍歷森林中第一棵樹的子樹森林；（2）訪問森林中第一棵樹的根結(jié)點；（3）中序遍歷森林中(除第一棵樹之外)其余樹構(gòu)成的森林。即：依次從左至右對森林中的每一棵樹進行后根遍歷。

樹的遍歷和二叉樹遍歷的對應(yīng)關(guān)系？先根遍歷后根遍歷樹二叉樹森林先序遍歷先序遍歷中序遍歷中序遍歷設(shè)樹的存儲結(jié)構(gòu)為孩子兄弟鏈表typedef

struct

CSNode{

Elemdata;

struct

CSNode

*firstchild,*nextsibling;}

CSNode,*CSTree;樹的遍歷的應(yīng)用一、求樹的深度二、輸出樹中所有從根到葉子的路徑三、建樹的存儲結(jié)構(gòu)int

TreeDepth(CSTreeT){

if(!T)return0;

else{h1=TreeDepth(T->firstchild);h2=TreeDepth(T->nextsibling);}}//TreeDepthreturn(max(h1+1,h2));一、求樹的深度的算法：二、輸出樹中所有從根到葉子的路徑的算法:ABCDEFGHIJK例如：對左圖所示的樹，其輸出結(jié)果應(yīng)為：ABEABFACADGHIADGHJADGHKvoid

AllPath(BitreeT,Stack&S){

if(T)

{

Push(S,T->data);if(!T->Lchild&&!T->Rchild)PrintStack(S);else{

AllPath(T->Lchild,S);

AllPath(T->Rchild,S);}

Pop(S);

}//

if(T)}//AllPath//輸出二叉樹上從根到所有葉子結(jié)點的路徑void

OutPath(BitreeT,Stack&S){

while(!T){

Push(S,T->data);

if(!T->firstchild)Printstack(s);

else

OutPath(T->firstchild,s);

Pop(S);

T=T->nextsibling;

}//while}//OutPath//輸出森林中所有從根到葉的路徑三、建樹的存儲結(jié)構(gòu)的算法:和二叉樹類似，不同的定義相應(yīng)有不同的算法。

假設(shè)以二元組(F，C)的形式自上而下、自左而右依次輸入樹的各邊，建立樹的孩子-兄弟鏈表。ABCDEFG例如:對下列所示樹的輸入序列應(yīng)為:(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)(‘C’,‘F’)(‘E’,‘G’)ABCD(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)可見，算法中需要一個隊列保存已建好的結(jié)點的指針。void

CreatTree(CSTree

&T){T=NULL;

for(scanf(&fa,&ch);ch!=

;

scanf(&fa,&ch);){ p=GetTreeNode(ch);//創(chuàng)建結(jié)點

EnQueue(Q,p);//指針入隊列

if(fa

==

)T=p;//所建為根結(jié)點

else{

}//非根結(jié)點的情況

}//for}//CreateTree ……GetHead(Q,s);//取隊列頭元素(指針值)while(s->data!=

fa){//查詢雙親結(jié)點

DeQueue(Q,s);GetHead(Q,s);}if(!(s->firstchild))

{s->firstchild=p;r=p;}

//鏈接第一個孩子結(jié)點else

{r->nextsibling=p;r=p;}

//鏈接其它孩子結(jié)點

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

6.6.1最優(yōu)二叉樹樹的路徑長度定義為：

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

從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的路徑，路經(jīng)上的分支數(shù)目稱作路經(jīng)長度。結(jié)點的帶權(quán)路徑長度定義為：

從該結(jié)點到樹根之間的路經(jīng)長度與結(jié)點上權(quán)的乘積。樹的帶權(quán)路徑長度定義為：樹中所有葉子結(jié)點的帶權(quán)路徑長度之和。記作：

WPL(T)=

wklk

(對所有葉子結(jié)點)。

在所有含n個葉子結(jié)點、并帶相同權(quán)值的m叉樹中，必存在一棵其帶權(quán)路徑長度取最小值的樹，稱為“最優(yōu)樹”。例如：

假設(shè)有n個權(quán)值{w1,w2,…wn}，試構(gòu)造一棵有n個葉子結(jié)點的二叉樹，每個葉結(jié)點帶權(quán)為wi，則其中帶權(quán)路徑長度WPL最小的二叉樹稱為最優(yōu)二叉樹或哈夫曼樹。27975492WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=8954

如何構(gòu)造最優(yōu)二叉樹呢？哈夫曼最早給出了一個帶有一般規(guī)律的算法，俗稱哈夫曼算法。如下：

（1）根據(jù)給定的n個權(quán)值{w1,w2,…,wn}，構(gòu)造n棵二叉樹的集合F={T1,T2,…,Tn}，其中每棵二叉樹Ti中均只含一個帶權(quán)值為wi

的根結(jié)點，其左、右子樹為空樹；（2）在F中選取其根結(jié)點的權(quán)值為最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點的權(quán)值為其左、右子樹根結(jié)點的權(quán)值之和；（3）從F中刪去這兩棵樹，同時加入剛生成的新二叉樹；（4）重復(fù)

(2)

和

(3)

兩步，直至F中只含一棵樹為止。這棵樹便是哈夫曼樹。9例如:已知權(quán)值W={5,6,2,9,7}56275276976713952767139527952716671329000011110001101101116.6.2哈夫曼編碼

在傳送電文時，希望總長盡可能短。如果對每個字符設(shè)計長度不等的編碼，且讓電文中出現(xiàn)次數(shù)較多的字符采用盡可能短的編碼，則傳送電文的總長度便可減少。任何一個字符的編碼都不是同一字符集中另一個字符的編碼的前綴，這種編碼稱作前綴編碼。

利用赫夫曼樹可以構(gòu)造一種不等長的二進制編碼，并且構(gòu)造所得的赫夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長度最短。//－－－－赫夫曼樹和赫夫曼編碼的存儲表示－－－－

typedef

struct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//動態(tài)分配數(shù)組存儲赫夫曼樹

typedefchar**HuffmanCode;//動態(tài)分配數(shù)組存儲赫夫曼編碼表求赫夫曼編碼的算法：

viod

HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){//w存放n個字符的權(quán)值(均>0)，構(gòu)造赫夫曼樹HT，并求出n個字符的赫夫曼編碼HC。if(n<=1)return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0