第六章樹(shù)和二叉樹(shù)

第六章樹(shù)和二叉樹(shù)6.1樹(shù)的定義和基本術(shù)語(yǔ)6.2二叉樹(shù)

6.2.1二叉樹(shù)的定義

6.2.2二叉樹(shù)的性質(zhì)

6.2.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)6.3遍歷二叉樹(shù)和線索二叉樹(shù)

6.3.1遍歷二叉樹(shù)

6.3.2線索二叉樹(shù)6.4樹(shù)和森林

6.4.1樹(shù)的存儲(chǔ)結(jié)構(gòu)

6.4.2森林與二叉樹(shù)的轉(zhuǎn)換6.6赫夫曼樹(shù)及其應(yīng)用

6.6.1最優(yōu)二叉樹(shù)(赫夫曼樹(shù))非線性數(shù)據(jù)結(jié)構(gòu)。樹(shù)的遞歸定義：樹(shù)(tree)是n(n>=0)個(gè)結(jié)點(diǎn)的有限集。當(dāng)n>0時(shí),(1)有且僅有一個(gè)特定的稱(chēng)為根(root)的結(jié)點(diǎn);(2)當(dāng)n>1時(shí),其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,...,Tm,其中每個(gè)集合本身又是一棵樹(shù)。稱(chēng)為子樹(shù)(subtree)。第六章樹(shù)和二叉樹(shù)

6.1樹(shù)的定義和基本術(shù)語(yǔ)樹(shù)的示例空樹(shù)

n=0層次1234一般的樹(shù)ABCDEFGHIJKL只有根結(jié)點(diǎn)的樹(shù)n=1AADTTree｛

數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。

數(shù)據(jù)關(guān)系R：若D為空集，則稱(chēng)為空樹(shù);

若D僅含一個(gè)數(shù)據(jù)元素，則R為空集，否則R＝｛H｝，H是如下二元關(guān)系：（1）在D中存在唯一的稱(chēng)為根的數(shù)據(jù)元素root，它在關(guān)系H下無(wú)前驅(qū)；（2）若D－｛root｝≠φ，則存在D－｛root｝的一個(gè)劃分D1,D2,...,Dm（m＞0），對(duì)任意j≠k（1≤j,k≤m）有Dj∩Dk=φ

，且對(duì)任意的i（1≤i≤m），唯一存在數(shù)據(jù)元素xiξDi，有<root,xi>ξH;（3）對(duì)應(yīng)于D－｛root｝的劃分，H－｛<root,x1>，....，<root,xm>｝有唯一的一個(gè)劃分H1,H2,...,Hm

（m＞0），對(duì)任意j≠k（1≤j,k≤m）有Hj∩Hk=φ

，且對(duì)任意的i（1≤i≤m），Hi

是Di上的二元關(guān)系，（Di,{Hi}）是一棵符合本定義的樹(shù)，稱(chēng)為根root的子樹(shù)。樹(shù)的抽象數(shù)據(jù)類(lèi)型定義：

INITTREE（＆T）；操作結(jié)果：構(gòu)造空樹(shù)T。

DESTROYTREE（＆T）；初始條件：樹(shù)T存在。操作結(jié)果：銷(xiāo)毀樹(shù)T。

CREATETREE（＆T，DEFINITION）；初始條件：DEFINITION給出樹(shù)T的定義。操作結(jié)果：按DEFINITION構(gòu)造樹(shù)T。

CLEARTREE（＆T）；初始條件：樹(shù)T存在。操作結(jié)果：將樹(shù)T清為空樹(shù)。樹(shù)的抽象數(shù)據(jù)類(lèi)型定義：

基本操作（之一）

TREEEMPTY（T）初始條件：樹(shù)T存在。操作結(jié)果：若T為空樹(shù)，則返回TURE，否則FALSE。

TREEDEPTH（T）初始條件：樹(shù)T存在。操作結(jié)果：返回T的深度。

ROOT（T）初始條件：樹(shù)T存在。操作結(jié)果：返回T的根。

VALUE（T,CUR_E）；初始條件：樹(shù)T存在，CUR＿E是T中某個(gè)結(jié)點(diǎn)。操作結(jié)果：返回CUR＿E的值。樹(shù)的抽象數(shù)據(jù)類(lèi)型定義：

基本操作（之二）ASSIGN（T，CUR_E，VALUE）初始條件：樹(shù)T存在，CUR＿E是T中某個(gè)結(jié)點(diǎn)。操作結(jié)果：結(jié)點(diǎn)CUR_E賦值為VALUE。

PARENT（T，CUR＿E）初始條件：樹(shù)T存在，CUR＿E是T中某個(gè)結(jié)點(diǎn)。操作結(jié)果：若CUR＿E是T的非根結(jié)點(diǎn)，則返回它的雙親，否則函數(shù)值為“空”。

LEFTCHILD（T，CUR＿E）初始條件：樹(shù)T存在，CUR＿E是T中某個(gè)結(jié)點(diǎn)。操作結(jié)果：若CUR＿E是T的非葉子結(jié)點(diǎn)，則返回它的最左孩子，否則返回“空”。

RIGHTSIBLING（T，CUR＿E）初始條件：樹(shù)T存在，CUR＿E是T中某個(gè)結(jié)點(diǎn)。操作結(jié)果：若CUR＿E有右兄弟，則返回它的右兄弟，否則函數(shù)值為“空”。樹(shù)的抽象數(shù)據(jù)類(lèi)型定義：

基本操作（之三）INSERTCHILD（＆T，＆P，I，C）；初始條件：樹(shù)T存在，P指向T中某個(gè)結(jié)點(diǎn)，1≤I≤P所指結(jié)點(diǎn)的度＋1，非空樹(shù)C與T不相交。操作結(jié)果：插入C為T(mén)中P指結(jié)點(diǎn)的第I棵子樹(shù)。

DELETECHILD（＆T，＆P，I）；初始條件：樹(shù)T存在，P指向T中某個(gè)結(jié)點(diǎn)，1≤I≤P指結(jié)點(diǎn)的度。操作結(jié)果：刪除T中P所指結(jié)點(diǎn)的第I棵子樹(shù)。

TRAVERSETREE（T，VISIT（））；初始條件：樹(shù)t存在，VISIT是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作結(jié)果：按某種次序?qū)的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)VISIT（）一次且至多一次。一旦VISIT（）失敗，則操作失敗。｝ADTTREE樹(shù)的抽象數(shù)據(jù)類(lèi)型定義：

基本操作（之四）子樹(shù)(subtree)結(jié)點(diǎn)結(jié)點(diǎn)的度(degree)葉子(leaf)(終端結(jié)點(diǎn))分支結(jié)點(diǎn)(非終端結(jié)點(diǎn))樹(shù)的度樹(shù)的基本術(shù)語(yǔ)（之一）ABCDFGHIL

孩子(child)

雙親(parent)

兄弟(sibling)

堂兄弟祖先子孫樹(shù)的基本術(shù)語(yǔ)（之二）ABCDFGHIL子樹(shù)(subtree)

層次(level)

深度(depth)

有序樹(shù)無(wú)序樹(shù)森林:m(m>=0)棵互不相交的樹(shù)的集合.樹(shù)的基本術(shù)語(yǔ)（之三）ABCDFGHIL二叉樹(shù)(binarytree):度不超過(guò)2的有序樹(shù)。二叉樹(shù)的五種基本形態(tài)6.2二叉樹(shù)

6.2.1二叉樹(shù)的定義(a)空二叉樹(shù);(b)僅有根結(jié)點(diǎn)的二叉樹(shù)；(c)右子樹(shù)為空的二叉樹(shù)；(d)左、右子樹(shù)均為非空的二叉樹(shù)；(e)左子樹(shù)為空的二叉樹(shù)。(a)A(b)A(c)A(d)A(e)性質(zhì)2：深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)(k>=1).

k-1Nk=∑2i=2k-1i=0性質(zhì)3:對(duì)任何一棵二叉樹(shù)T,如果其葉結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則n0=n2+二叉樹(shù)的性質(zhì)

-

性質(zhì)1：在二叉樹(shù)的第i層上至多有2(i-1)個(gè)結(jié)點(diǎn)(i>=1).一般的二叉樹(shù)ABDEFHIJKL層次1234一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱(chēng)為滿(mǎn)二叉樹(shù)。k=3k=4滿(mǎn)二叉樹(shù)的定義:123456789141011151213

深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿(mǎn)二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱(chēng)之為完全二叉樹(shù)。完全二叉樹(shù)的定義:123456完全二叉樹(shù)和非完全二叉樹(shù)舉例:123456789101112完全二叉樹(shù)123456非完全二叉樹(shù)完全二叉樹(shù)性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為[log2n]*+1。性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)（其深度為[log2n]*+1）的結(jié)點(diǎn)按層序編號(hào)（從第1層到第[log2n]*+1層，每層從左到右），則對(duì)任一結(jié)點(diǎn)i（1≤i≤n），有（1）如果i＝1，則結(jié)點(diǎn)i是二叉樹(shù)的根，無(wú)雙親；如果i＞1，則其雙親PARENT（i）是結(jié)點(diǎn)[i/2]*。（2）如果2i＞n，則結(jié)點(diǎn)i無(wú)左孩子（結(jié)點(diǎn)i為葉子結(jié)點(diǎn)），否則其左孩子LCHILD（i）是結(jié)點(diǎn)2i。（3）如果2i＋1＞n，則結(jié)點(diǎn)i無(wú)右孩子；否則其右孩子RCHILD（i）是結(jié)點(diǎn)2i+1.//--------二叉樹(shù)的順序存儲(chǔ)表示------------#defineMAX_TREE_SIZE100typedefTElemTypeSqBiTree[MAX_TREE_SIZE];SqBiTreebt;上一節(jié)完全二叉樹(shù)的十二個(gè)結(jié)點(diǎn)的順序存儲(chǔ)為：

上一節(jié)非完全二叉樹(shù)的六個(gè)結(jié)點(diǎn)的順序存儲(chǔ)（需7個(gè)存儲(chǔ)空間）為：

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

一、順序存儲(chǔ)結(jié)構(gòu)12 34 56 78 910 111212 34 05 6最壞情況：深度為k的且只有k個(gè)結(jié)點(diǎn)的單支樹(shù)需要長(zhǎng)度為2k-1的一維數(shù)組。typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)rchilddatalchilddataparentlchildrchilddatalchildrchildparent鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示例樹(shù)的二叉兩鏈表示。三叉鏈表示略ABCDGEFABCDEFG?BDA?E?F??G??C??0123456123456???????StatusCreateBiTree(BiTree&T);//按先序次序輸入二叉樹(shù)中結(jié)點(diǎn)的值（一個(gè)字符），空格字符表示空樹(shù)，//構(gòu)造二叉鏈表表示的二叉樹(shù)T。StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采用二叉鏈表存儲(chǔ)結(jié)構(gòu),Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)//先序遍歷二叉樹(shù)T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。//一旦Visit()失敗，則操作失敗?；静僮鞯暮瘮?shù)原型說(shuō)明(一)StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采用二叉鏈表存儲(chǔ)結(jié)構(gòu),Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。//中序遍歷二叉樹(shù)T，一旦Visit()失敗，則操作失敗。StatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采用二叉鏈表存儲(chǔ)結(jié)構(gòu),Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。//后序遍歷二叉樹(shù)T，一旦Visit()失敗，則操作失敗。StatusLevelOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采用二叉鏈表存儲(chǔ)結(jié)構(gòu),Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。//層序遍歷二叉樹(shù)T，一旦Visit()失敗，則操作失敗?；静僮鞯暮瘮?shù)原型說(shuō)明(二)

6.3.1遍歷二叉樹(shù)如果按某條搜索路徑巡訪樹(shù)中每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅被訪問(wèn)一次。6.3遍歷二叉樹(shù)和線索二叉樹(shù)ABCDGEF

若二叉樹(shù)為空，則空操作；否則（1）訪問(wèn)根結(jié)點(diǎn)；（2）先序遍歷左子樹(shù)；（3）先序遍歷右子樹(shù)。

ABCDFEG先序遍歷二叉樹(shù)的操作定義為：ABCDGEFStatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){if(T){if(Visit(T->data))if(PreOrderTraverse(T->lchild,Visit))if(PreOrderTraverse(T->rchild,Visit))returnOK;returnERROR;}elsereturnOK;}//PreOrderTraverse先序遍歷二叉樹(shù)的遞歸算法若二叉樹(shù)為空，則空操作；否則（1）中序遍歷左子樹(shù)；（2）訪問(wèn)根結(jié)點(diǎn)；（3）中序遍歷右子樹(shù)。

CBDFAGE中序遍歷二叉樹(shù)的操作定義為：ABCDGEF中序遍歷二叉樹(shù)得:a+b*(c-d)-e/f中序遍歷二叉樹(shù)示例-+a*e/-fbdcStatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

if(T){

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

if(Visit(T->data))

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

returnERROR;

}elsereturnOK;

}//InOrderTraverse中序遍歷二叉樹(shù)的遞歸算法

若二叉樹(shù)為空，則空操作；否則（1）后序遍歷左子樹(shù)；（2）后序遍歷右子樹(shù)；（3）訪問(wèn)根結(jié)點(diǎn)。

CFDBGEA后序遍歷二叉樹(shù)的操作定義為：ABCDGEFStatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

if(T){

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

if(PostOrderTraverse(T->rchild,Visit))

if(Visit(T->data))returnOK;

returnERROR;

}elsereturnOK;

}//PostOrderTraverse后序遍歷二叉樹(shù)的遞歸算法StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

InitStack(S);Push(S,T);while(!StackEmpty(S)){while(GetTop(S,p)&&p)Push(S,p->lchild);

Pop(S,p);

if(!StackEmpty(S)){

Pop(S,p);if(!Visite(p->data))returnERROR;Push(S,p->rchild);

}}returnOK;

}//InOrderTraverse中序遍歷二叉樹(shù)的非遞歸算法CBDFAGE中序遍歷二叉樹(shù)的非遞歸算法

示意圖ABCDGEFABCNULLSGetTop<--pAS

PoppCBDFA先序序列：ABCDEFG中序序列：CBEDAFG例：已知結(jié)點(diǎn)的先序序列和中序序列，求整棵二叉樹(shù)。AC

B

E

DFGABCDEFGABCFDEGStatusCreateBiTree(BiTree&T){scanf(“%c”,&ch);

if(ch==‘#’)T=NULL;else{

if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);

T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}returnOK;

}//CreateBiTree構(gòu)造二叉鏈表表示的二叉樹(shù)

的遞歸算法構(gòu)造二叉鏈表ABCDGEF按下列次序輸入字符:ABCDEGF(其中表示空格字符)可建立如右圖的二叉鏈表.遍歷是非線性結(jié)構(gòu)的線性化操作

保留遍歷過(guò)程的順序信息-----線索二叉樹(shù)的表示:若結(jié)點(diǎn)有左子樹(shù)，則其LCHILD域指示其左孩子，否則令LCHILD域指示其前驅(qū)；若結(jié)點(diǎn)有右子樹(shù)，則其RCHILD域指示其右孩子，否則令RCHILD域指示其后繼。6.3.2線索二叉樹(shù)0lchild域指示其左孩子ltag={1lchild域指示其前驅(qū)

0rchild域指示其右孩子rtag={1rchild域指示其后繼線索二叉樹(shù)線索化線索鏈表線索線索二叉樹(shù)結(jié)點(diǎn)的結(jié)構(gòu):datalchildrchildrtagltag中序線索二叉樹(shù)-+a*e/-fbdcNILNILb*11

+

/f00

e

如何在中序線索二叉樹(shù)中找結(jié)點(diǎn)的后繼：

rtag=1時(shí)，rchild所指的結(jié)點(diǎn)即為后繼；

rtag=0時(shí)，其后繼為遍歷其右子樹(shù)時(shí)的第一個(gè)結(jié)點(diǎn)（最左下結(jié)點(diǎn)）。如結(jié)點(diǎn)“*”的后繼是“c”。如何在中序線索二叉樹(shù)中找結(jié)點(diǎn)的前驅(qū)：ltag=1時(shí)，lchild所指的結(jié)點(diǎn)即為前驅(qū)；ltag=0時(shí)，其前驅(qū)為遍歷其左子樹(shù)時(shí)的最后一個(gè)結(jié)點(diǎn)（最右下結(jié)點(diǎn)）。如根結(jié)點(diǎn)“-”的前驅(qū)是“d”。中序線索二叉樹(shù)中

查找結(jié)點(diǎn)的后繼和前驅(qū):中序線索二叉樹(shù)//二叉樹(shù)的二叉線索存儲(chǔ)表示typedefenum{Link,Thread}PointerTag;//Link==0:指針,Thread==1:線索typedefstructBiThrNode{TElemTypedata;structBiThrNode*lchild,*rchild;//左右孩子指針

PointerTagLTag,RTag;//左右標(biāo)志}BiThrNode,*BiThrTree;StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//Thrt指向頭結(jié)點(diǎn)。

if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(OVERFLOW);

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

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

if(!T)Thrt->lchild=Thrt;//若二叉樹(shù)空，則左指針回指

else{

Thrt->lchild=T;pre=Thrt;

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

pre->rchild=Thrt;pre->RTag=Thread;//最后一個(gè)結(jié)點(diǎn)線索化

Thrt->rchild=pre;

}

returnOK;

}//InOrderThreading中序遍歷二叉樹(shù)T，并將其中序線索化:

(為了記下遍歷過(guò)程中訪問(wèn)結(jié)點(diǎn)的先后次序，附設(shè)一個(gè)全程指針pre)voidInThreading(BiThrTreep){

//一個(gè)全程指針pre

if(p){

InThreading(p->lchild);//左子樹(shù)線索化

if(!p->lchild){p->LTag=Thread;p->lchild=pre;}//前驅(qū)線索

if(!pre->rchild){pre->RTag=Thread;pre->rchild=p;}//后繼線索

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

InThreading(p->rchild);//右子樹(shù)線索化

}

}//InThreading

中序遍歷進(jìn)行中序線索化例如:

將下列二叉鏈表改為中序線索鏈表1234567891011121314上例樹(shù)的形態(tài)

Thrt10

1234567891011121314ABDEFCHIGKJMNLStatusInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(TElemTypee)){

//T指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的左鏈lchild指向根結(jié)點(diǎn)，

//可參見(jiàn)線索化算法。中序遍歷二叉線索樹(shù)T的非遞歸算法，

//對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit.

p=T->lchild;//p指向根結(jié)點(diǎn)

while(p!=T){//空樹(shù)或遍歷結(jié)束時(shí)，p==T

while(p->LTag==Link)p=p->lchild;//p尋找最左下結(jié)點(diǎn)

if(!Visit(p->data))returnERROR;//訪問(wèn)其左子樹(shù)為空的結(jié)點(diǎn)

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

p=p->rchild;Visit(p->data);//訪問(wèn)后繼結(jié)點(diǎn)

}

p=p->rchild;

}

returnOK;

}//InOrderTraverse_Thr中序遍歷二叉線索樹(shù)T的非遞歸算法:實(shí)驗(yàn)用鏈表實(shí)現(xiàn)二叉樹(shù)的幾種基本操作：初始化，遍歷以二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，編寫(xiě)以下算法：（1）統(tǒng)計(jì)二叉樹(shù)的葉結(jié)點(diǎn)個(gè)數(shù)（2）分別以先序、中序以及后序遍歷二叉樹(shù)并輸出二叉樹(shù)的節(jié)點(diǎn)已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為() A．-A+B*C/DEB.-A+B*CD/E C．-+*ABC/DED.-+A*BC/DE設(shè)有一表示算術(shù)表達(dá)式的二叉樹(shù)（見(jiàn)下圖），它所表示的算術(shù)表達(dá)式是（

）A.A*B+C/(D*E)+(F-G)B.(A*B+C)/(D*E)+(F-G)C.(A*B+C)/(D*E+（F-G）)D.A*B+C/D*E+F-GE F D G A B / + + * - C * 若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（

）A．9B．11C．15D．不確定具有10個(gè)葉結(jié)點(diǎn)的二叉樹(shù)中有（

）個(gè)度為2的結(jié)點(diǎn)A．8B．9C．10D．1l一棵完全二叉樹(shù)上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（

）A．250B．500C．254D．505E．以上答案都不對(duì)某二叉樹(shù)中序序列為A,B,C,D,E,F,G，后序序列為B,D,C,A,F,G,E則前序序列是：A．E,G,F,A,C,D,BB．E,A,C,B,D,G,FC．E,A,G,C,F,B,DD．上面的都不對(duì)

一、雙親表示法（順序存儲(chǔ)）

//-----------樹(shù)的雙親表存儲(chǔ)表示----------//#defineMAX_TREE_SIZE100typedefstructPTNode{TElemTypedata;intparent;//雙親位置域

}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intn;//結(jié)點(diǎn)數(shù)

}PTree;6．4樹(shù)和森林

6.4.1樹(shù)的存儲(chǔ)結(jié)構(gòu)雙親表示法舉例RADEFCBGKHR-1A0B0C0D1E1F3G6H6K60123456789數(shù)組下標(biāo):*便于涉及雙親的操作；*求結(jié)點(diǎn)的孩子時(shí)需要遍歷整棵樹(shù)。#defineMAX_TREE_SIZE100typedefstructPTNode{TElemTypedata;intchild1;//第1個(gè)孩子位置域

intchild2;//第2個(gè)孩子位置域

......intchildd;//第d個(gè)孩子位置域

}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intn;//結(jié)點(diǎn)數(shù)

}PTree;6.4.1樹(shù)的存儲(chǔ)結(jié)構(gòu)

二、孩子表示法（順序存儲(chǔ)）孩子表示法舉例RADEFCBGKH0123456789數(shù)組下標(biāo):*便于涉及孩子的操作；求雙親不方便；*采用同構(gòu)的結(jié)點(diǎn)，空間浪費(fèi)。R1A4B0C6D0E0F7G0H0K023500000000089000000孩子鏈表存儲(chǔ)表示（鏈?zhǔn)酱鎯?chǔ)）typedefstructCTNode{//孩子結(jié)點(diǎn)

intchild;structCTNode*next;}*ChildPtr;typedefstruct{TElemTypedata;ChildPtrfirstchild;//孩子鏈表頭指針

}CTBox;typedefstruct{CTBoxnodes[MAX_TREE_SIZE];intn,r;//結(jié)點(diǎn)數(shù)和根的位置

}CTree;孩子鏈表存儲(chǔ)表示舉例RADEFCBGKH0123456789數(shù)組下標(biāo):*便于涉及孩子的操作；*求結(jié)點(diǎn)的雙親時(shí)不方便。RAB/CD/E/FG/H/K/123/45/6/789/T.nodes[];T.n=10;T.r=0;例1:設(shè)樹(shù)T以孩子鏈表為存儲(chǔ)結(jié)構(gòu),

尋找值為x的雙親結(jié)點(diǎn)的算法如下:Statusparent(CtreeT,TElemTypex){//當(dāng)值為x的結(jié)點(diǎn)不存在時(shí)返回-2;//當(dāng)值為x的結(jié)點(diǎn)為根結(jié)點(diǎn)時(shí)返回-1,//否則返回x結(jié)點(diǎn)的雙親結(jié)點(diǎn)的下標(biāo)值.if(T.nodes[T.r].data==x)return–1;//值為x的結(jié)點(diǎn)為根結(jié)點(diǎn);for(i=0;i<T.n;i++){p=T.nodes[i].firstchild;while(p&&T.nodes[p->child].data!=x)p=p->next;if(p)return(i);//找到x的雙親結(jié)點(diǎn)

}return–2;//值為x的結(jié)點(diǎn)不存在}例2:刪除值為x的結(jié)點(diǎn)的第i棵子樹(shù)的算法delete如下：voiddeletej(Ctree&T,intj){//刪除樹(shù)T的第j號(hào)結(jié)點(diǎn)及其子樹(shù)

if(!T.nodes[j].firstchild){//刪除葉結(jié)點(diǎn)

for(i=j;i<T.n-1;i++){//j號(hào)結(jié)點(diǎn)后的結(jié)點(diǎn)全部前移一位

T.nodes[i].data=T.nodes[i+1].data; T.nodes[i].firstchild=T.nodes[i+1].firstchild;}T.n--;}else{while(s=T.nodes[j].firstchild){ T.nodes[j].firstchild=s->next; i=s->child; free(s); deletej(T,i);//遞歸刪除第i號(hào)結(jié)點(diǎn)及其子樹(shù)

}}}Statusdelete(Ctree&T,TElemTypex,inti){//當(dāng)值為x的結(jié)點(diǎn)不存在時(shí)返回-2;當(dāng)值為x的結(jié)點(diǎn)為

//葉結(jié)點(diǎn)或無(wú)第i棵子樹(shù)時(shí)返回-1,否則返回1.for(k=0;k<T.n;k++)if(T.nodes[k].data==x)break;//找到值為x的結(jié)點(diǎn)

if(k>=T.n)return–2;//值為x的結(jié)點(diǎn)不存在

p=T.nodes[k].firstchild;j=1;if(!p)return–1;//x結(jié)點(diǎn)為葉結(jié)點(diǎn)

if(i==1){//刪除長(zhǎng)子時(shí),特殊處理

j=p->child;//記住要?jiǎng)h除子樹(shù)的下標(biāo)

T.nodes[k].firstchild=p->next;free(p);}else{while(p->next&&j<i-1){p=p->next;j++;}if(j>i-1||!p->next)return–1;//無(wú)第i棵子樹(shù)

//p指向第i-1個(gè)兒子

j=p->next->child;//記住要?jiǎng)h除子樹(shù)的下標(biāo)

s=p->next;p->next=s->next;free(s);}deletej(T,j);//遞歸刪除第j號(hào)結(jié)點(diǎn)及其子樹(shù)

return1;}//-----樹(shù)的二叉鏈表(孩子兄弟)存儲(chǔ)表示------

typedefstructCSNode{

ELemTypedata;

structCSNode*firstchild,*nextsibling;

}CSNode,*CSTree;

三.孩子兄弟表示法

---樹(shù)的二叉樹(shù)表示法(二叉鏈表示法)RADEFCBGKHR?A?DE?C?H?F?G?B?K??孩子兄弟表示法示例：如果F={T1,T2,

…,Tm}是森林,則可按如下規(guī)則轉(zhuǎn)換成一棵二叉樹(shù)B=(root,LB,RB)。

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

(2)若F非空，即m<>0，則B的根root即為森林中第一棵樹(shù)的根ROOT(T1)；

B的左子樹(shù)LB是從T1中根結(jié)點(diǎn)的子樹(shù)森林F1={T11,T12,…,T1m1}轉(zhuǎn)換而成的二叉樹(shù);

其右子對(duì)RB是從森林F'={T2,T3,

…,Tm}轉(zhuǎn)換而成的二叉樹(shù).6.4.2森林與二叉樹(shù)的轉(zhuǎn)換

一.森林轉(zhuǎn)換成二叉樹(shù)如果B=(root,LB,RB)是一棵二叉樹(shù),則可按如下規(guī)則轉(zhuǎn)換成森林F={T1,T2,…,Tm}：

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

(2)若B非空，則F中第一棵樹(shù)T1的根ROOT(T1)即為二叉樹(shù)B的根root；

T1中的根結(jié)點(diǎn)的子樹(shù)森林F1是由B的左子樹(shù)LB轉(zhuǎn)換而成的森林;F中除T1之外其余樹(shù)組成的森林F'={T2,T3,…，Tm}是由B的右子樹(shù)RB轉(zhuǎn)換而成的森林。二.二叉樹(shù)轉(zhuǎn)換成森林

樹(shù)的兩種遍歷方法：一、先根遍歷：（1）訪問(wèn)樹(shù)的根結(jié)點(diǎn)；（2）依次先根遍歷每棵子樹(shù)。

RADEBCFGHK二、后根遍歷：（1）依次后根遍歷每棵子樹(shù)。（2）訪問(wèn)樹(shù)的根結(jié)點(diǎn)；

DEABGHKFCR6.4.3樹(shù)和森林的遍歷RADEFCBGKH

一、先序遍歷森林：若森林非空，則（1）訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)；（2）先序遍歷第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林；（3）先序遍歷除去第一棵樹(shù)之后的森林。二、中序遍歷森林：若森林非空，則（1）中序遍歷第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林；（2）訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)；（3）中序遍歷除去第一棵樹(shù)之后的森林。森林的兩種遍歷方法：

路徑長(zhǎng)度:

從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑,路徑上的分支數(shù)目稱(chēng)做路徑長(zhǎng)度。

樹(shù)的路徑長(zhǎng)度:

樹(shù)的路徑長(zhǎng)度是從樹(shù)根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。

樹(shù)的帶權(quán)路徑長(zhǎng)度:樹(shù)的帶權(quán)路徑長(zhǎng)度為樹(shù)中所有葉子結(jié)點(diǎn)(k)的帶權(quán)路徑長(zhǎng)度ωkιk之和,通常記作：nWPL=∑ωkιk。

k=1

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

6.6.1最優(yōu)二叉樹(shù)(赫夫曼樹(shù))假設(shè)有n個(gè)權(quán)值{ω1,ω2,

…,ωn}，試構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹(shù),每個(gè)葉子結(jié)點(diǎn)帶權(quán)為ωi,則其中：帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹(shù)稱(chēng)做

最優(yōu)二叉樹(shù)

或赫夫曼樹(shù).最優(yōu)二叉樹(shù)

或赫夫曼(Huffman)樹(shù)的定義例1：下面三棵二叉樹(shù)的四個(gè)葉子結(jié)點(diǎn)a,b,c,d的權(quán)值為7、5、2、4abcd7524abcd7524cdab7524(a)WPL=7x2+5x2+2x2+4x2=36(b)WPL=7x3+5x3+2x1+4x2=46(c)WPL=7x1+5x2+2x2+4x2=35例2最佳判定方法(p.144)

(a)WPL=10x4+30x4+40x3+15x2+5x1=315

(b)WPL=5x3+15x3+40x2+30x2+10x2=22010c<90ed51540ba30<60<70<80NNNNYYYYY10<70<90ec54015ba30<60d<80NNNNYYYYY(1)根據(jù)給定的n個(gè)權(quán)值{w1,w2,…,wn}構(gòu)成n棵二叉樹(shù)的集合F={T1,T2,…,Tn}其中每棵二叉樹(shù)Ti中只有一個(gè)帶權(quán)為Wi的根結(jié)點(diǎn),其左右子樹(shù)均空.(2)在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù),且置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左.右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和.(3)在F中刪除這兩棵樹(shù),同時(shí)將新得到的二叉樹(shù)加入F中.(4)重復(fù)(2)和(3),直到F只含一棵樹(shù)為止.這棵樹(shù)便是赫夫曼樹(shù).構(gòu)造赫夫曼樹(shù)的算法思想構(gòu)造赫夫曼樹(shù)舉例cdab7524abc2d457abc6d57abcd117//-----夫曼樹(shù)和赫夫曼編碼的存儲(chǔ)表示-------typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree; //動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼樹(shù)

typedefchar**HuffmanCode; //動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼編碼表6.6.2赫夫曼編碼

赫夫曼樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)---嚴(yán)格的二叉樹(shù)VoidHuffmanCoding(HuffmanTree*HT,HuffmanCode*HC,int*w,intn){//w存放n個(gè)字符的權(quán)值(均>0),構(gòu)造赫夫曼樹(shù)HT,并求出n個(gè)字符的赫夫曼編碼HC.if(n<=1)return; m=2*n-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0號(hào)單未用

for(p=HT,i=1;i<=n;++i,++p,++w)*p={*w,0,0,0};for(;i<=m;++i,++p)*p={0,0,0,0};求赫夫曼編碼的算法如下:for(i=n+1;i<=m;++i){ //建赫夫曼樹(shù)

//在HT[1..i-1]選擇parent為0且weight最小的兩個(gè)結(jié)點(diǎn),//其序號(hào)分別為s1和s2.select(HT,i-1,s1,s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;} //-----從葉子到根逆向求每個(gè)字符的赫夫曼編碼-----Hc=(HffmanCode)malloc((n+1*sizeof(char*)); //分配n個(gè)字符編碼的頭指針向量

cd=(char*)malloc(n*sizeof(char));//分配求編碼的工作空間

cd[n-1]="/0"; //編碼結(jié)束符.求赫夫曼編碼的算法（續(xù)一）:for(i=1;i<=n;++i){ //逐個(gè)字符求赫夫曼編碼

start=n-1; //編碼結(jié)束符位置

for(c=i,f=HT[i];f!=0;c=f,f=Ht[f].parent)//從葉子至根逆向求編碼

if(HT[f].lchild==c)cd[--start]="0";elsecd[--start]="1";Hc[i]=(char*)malloc((n-start)*sizeof(char));//為第i個(gè)字符編碼分配空間

strcpy(HC[i],&cd[start]);//從cd復(fù)制編碼(串)到HC}free(cd); //釋放工作空間}//HuffanCoding求赫夫曼編碼的算法（續(xù)二）://----------無(wú)棧非遞歸遍歷赫夫曼樹(shù),求赫夫曼編碼HC=(HuffmanCode)malloc((n+1)*sizeof(char*));p=m;cdlen=0;for(i=1;i<=m;++i)HT[i].weight=0;//遍歷赫夫曼樹(shù)時(shí)用作結(jié)點(diǎn)狀態(tài)標(biāo)志while(p){if(HT[p].weight==o){