第六章樹和二叉樹

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

6.2.1二叉樹的定義

6.2.2二叉樹的性質(zhì)

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

6.3.1遍歷二叉樹

6.3.2線索二叉樹6.4樹和森林

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

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

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

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

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

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

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

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

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

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

，且對任意的i（1≤i≤m），Hi

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

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

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

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

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

基本操作（之一）

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

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

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

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

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

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

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

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

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

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

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

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

孩子(child)

雙親(parent)

兄弟(sibling)

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

層次(level)

深度(depth)

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

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

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

-

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

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

上一節(jié)非完全二叉樹的六個結(jié)點的順序存儲（需7個存儲空間）為：

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

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

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

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

ABCDFEG先序遍歷二叉樹的操作定義為：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先序遍歷二叉樹的遞歸算法若二叉樹為空，則空操作；否則（1）中序遍歷左子樹；（2）訪問根結(jié)點；（3）中序遍歷右子樹。

CBDFAGE中序遍歷二叉樹的操作定義為：ABCDGEF中序遍歷二叉樹得:a+b*(c-d)-e/f中序遍歷二叉樹示例-+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中序遍歷二叉樹的遞歸算法

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

CFDBGEA后序遍歷二叉樹的操作定義為：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后序遍歷二叉樹的遞歸算法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中序遍歷二叉樹的非遞歸算法CBDFAGE中序遍歷二叉樹的非遞歸算法

示意圖ABCDGEFABCNULLSGetTop<--pAS

PoppCBDFA先序序列：ABCDEFG中序序列：CBEDAFG例：已知結(jié)點的先序序列和中序序列，求整棵二叉樹。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)造二叉鏈表表示的二叉樹

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

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

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

+

/f00

e

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

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

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

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

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

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

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

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

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

else{

Thrt->lchild=T;pre=Thrt;

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

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

Thrt->rchild=pre;

}

returnOK;

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

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

//一個全程指針pre

if(p){

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

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);//右子樹線索化

}

}//InThreading

中序遍歷進行中序線索化例如:

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

Thrt10

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

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

//可參見線索化算法。中序遍歷二叉線索樹T的非遞歸算法，

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

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

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

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

if(!Visit(p->data))returnERROR;//訪問其左子樹為空的結(jié)點

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

p=p->rchild;Visit(p->data);//訪問后繼結(jié)點

}

p=p->rchild;

}

returnOK;

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

）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 * 若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是（

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

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

）A．250B．500C．254D．505E．以上答案都不對某二叉樹中序序列為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．上面的都不對

一、雙親表示法（順序存儲）

//-----------樹的雙親表存儲表示----------//#defineMAX_TREE_SIZE100typedefstructPTNode{TElemTypedata;intparent;//雙親位置域

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

}PTree;6．4樹和森林

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

intchild2;//第2個孩子位置域

......intchildd;//第d個孩子位置域

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

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

二、孩子表示法（順序存儲）孩子表示法舉例RADEFCBGKH0123456789數(shù)組下標:*便于涉及孩子的操作；求雙親不方便；*采用同構(gòu)的結(jié)點，空間浪費。R1A4B0C6D0E0F7G0H0K023500000000089000000孩子鏈表存儲表示（鏈式存儲）typedefstructCTNode{//孩子結(jié)點

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

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

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

尋找值為x的雙親結(jié)點的算法如下:Statusparent(CtreeT,TElemTypex){//當值為x的結(jié)點不存在時返回-2;//當值為x的結(jié)點為根結(jié)點時返回-1,//否則返回x結(jié)點的雙親結(jié)點的下標值.if(T.nodes[T.r].data==x)return–1;//值為x的結(jié)點為根結(jié)點;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é)點

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

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

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

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號結(jié)點及其子樹

}}}Statusdelete(Ctree&T,TElemTypex,inti){//當值為x的結(jié)點不存在時返回-2;當值為x的結(jié)點為

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

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

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

if(i==1){//刪除長子時,特殊處理

j=p->child;//記住要刪除子樹的下標

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;//無第i棵子樹

//p指向第i-1個兒子

j=p->next->child;//記住要刪除子樹的下標

s=p->next;p->next=s->next;free(s);}deletej(T,j);//遞歸刪除第j號結(jié)點及其子樹

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

typedefstructCSNode{

ELemTypedata;

structCSNode*firstchild,*nextsibling;

}CSNode,*CSTree;

三.孩子兄弟表示法

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

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

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

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

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

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

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

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

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

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

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

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

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

DEABGHKFCR6.4.3樹和森林的遍歷RADEFCBGKH

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

路徑長度:

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

樹的路徑長度:

樹的路徑長度是從樹根到每一結(jié)點的路徑長度之和。

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

k=1

6.6赫夫曼樹及其應用

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

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

最優(yōu)二叉樹

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

或赫夫曼(Huffman)樹的定義例1：下面三棵二叉樹的四個葉子結(jié)點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個權(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中刪除這兩棵樹,同時將新得到的二叉樹加入F中.(4)重復(2)和(3),直到F只含一棵樹為止.這棵樹便是赫夫曼樹.構(gòu)造赫夫曼樹的算法思想構(gòu)造赫夫曼樹舉例cdab7524abc2d457abc6d57abcd117//-----夫曼樹和赫夫曼編碼的存儲表示-------typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree; //動態(tài)分配數(shù)組存儲赫夫曼樹

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

赫夫曼樹中沒有度為1的結(jié)點---嚴格的二叉樹VoidHuffmanCoding(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號單未用

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){ //建赫夫曼樹

//在HT[1..i-1]選擇parent為0且weight最小的兩個結(jié)點,//其序號分別為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;} //-----從葉子到根逆向求每個字符的赫夫曼編碼-----Hc=(HffmanCode)malloc((n+1*sizeof(char*)); //分配n個字符編碼的頭指針向量

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

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

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個字符編碼分配空間

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