第六章樹和二叉樹

第六章樹和二叉樹樹的概念和基本術(shù)語二叉樹二叉樹遍歷二叉樹的計(jì)數(shù)樹與森林霍夫曼樹樹的概念和基本術(shù)語樹的定義

樹是由n(n0)個(gè)結(jié)點(diǎn)的有限集合。如果n=0，稱為空樹；如果n>0，則

有且僅有一個(gè)特定的稱之為根(Root)的結(jié)點(diǎn)，它只有直接后繼，但沒有直接前驅(qū)；當(dāng)n>1，除根以外的其它結(jié)點(diǎn)劃分為m(m>0)個(gè)互不相交的有限集

T1,T2,…,Tm，其中每個(gè)集合本身又是一棵樹，并且稱為根的子樹(SubTree)。ACGBDEFKLHMIJ例如A只有根結(jié)點(diǎn)的樹有13個(gè)結(jié)點(diǎn)的樹其中：A是根；其余結(jié)點(diǎn)分成三個(gè)互不相交的子集，T1={B,E,F,K,L}；T2={C,G}；T3={D,H,I,J,M},T1,T2,T3都是根A的子樹，且本身也是一棵樹樹的基本術(shù)語1層2層4層3層height=4ACGBDEFKLHMIJ結(jié)點(diǎn)結(jié)點(diǎn)的度葉結(jié)點(diǎn)分支結(jié)點(diǎn)子女雙親兄弟祖先子孫結(jié)點(diǎn)層次樹的深度樹的度有序樹無序樹森林結(jié)點(diǎn)：一個(gè)數(shù)據(jù)元素及指向其子樹的分支。結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹個(gè)數(shù)。葉結(jié)點(diǎn)：度為零的結(jié)點(diǎn)。子女：結(jié)點(diǎn)子樹的根。兄弟：同一結(jié)點(diǎn)子女。祖先：根到該結(jié)點(diǎn)路徑上的所有結(jié)點(diǎn)。子孫：某結(jié)點(diǎn)為根的子樹上的任意結(jié)點(diǎn)。結(jié)點(diǎn)層次：從根開始，根為第一層，根的子女為第二層，以此類推。樹的深度（高度）：樹中結(jié)點(diǎn)的最大層次數(shù)。有序樹：樹中結(jié)點(diǎn)的子樹由左向右有序。森林：m(m0)棵互不相交的樹。二叉樹(BinaryTree)定義五種形態(tài) 一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。LLRR特點(diǎn)每個(gè)結(jié)點(diǎn)至多只有兩棵子樹（二叉樹中不存在度大于2的結(jié)點(diǎn)）性質(zhì)1 在二叉樹的第i層上至多有2i－1個(gè)結(jié)點(diǎn)。(i

1)[證明用歸納法]證明：當(dāng)i=1時(shí)，只有根結(jié)點(diǎn)，2i-1=20=1。假設(shè)對(duì)所有j，i>j1，命題成立，即第j層上至多有2j-1個(gè)結(jié)點(diǎn)。由歸納假設(shè)第i-1

層上至多有2i－2個(gè)結(jié)點(diǎn)。由于二叉樹的每個(gè)結(jié)點(diǎn)的度至多為2，故在第i層上的最大結(jié)點(diǎn)數(shù)為第i-1層上的最大結(jié)點(diǎn)數(shù)的2倍，即2*2i－2=2i-1。性質(zhì)性質(zhì)2

深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)(k1)。證明：由性質(zhì)1可見，深度為k的二叉樹的最大結(jié)點(diǎn)數(shù)為

＝20+21+…+2k-1=2k-1＝性質(zhì)3

對(duì)任何一棵二叉樹T,如果其葉結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則n0＝n2＋1.證明：若度為1的結(jié)點(diǎn)有n1個(gè)，總結(jié)點(diǎn)個(gè)數(shù)為n，總邊數(shù)為e，則根據(jù)二叉樹的定義，n=n0+n1+n2e=2n2+n1=n-1因此，有2n2+n1=n0+n1+n2

-1n2=n0

-1n0=n2+1定義1

滿二叉樹(FullBinaryTree) 一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。兩種特殊形態(tài)的二叉樹621754389101113141512滿二叉樹2154367216543非完全二叉樹定義2

完全二叉樹(CompleteBinaryTree)若設(shè)二叉樹的高度為h，則共有h層。除第h層外，其它各層(0h-1)的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第h層從右向左連續(xù)缺若干結(jié)點(diǎn)，這就是完全二叉樹。621754389101112完全二叉樹性質(zhì)4

具有n(n0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2(n)＋1

證明： 設(shè)完全二叉樹的深度為h，則根據(jù)性質(zhì)2和完全二叉樹的定義有 2h－1

-1<n2h-1或2h－1

n<2h取對(duì)數(shù)h－1<log2nh，又h是整數(shù)，因此有h=log2(n)＋1性質(zhì)5

如將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹自頂向下，同一層自左向右連續(xù)給結(jié)點(diǎn)編號(hào)0,1,2,…,n-1，則有以下關(guān)系：

若i=0,則i無雙親若i>0,則i的雙親為(i-1)/2

若2*i+1<n,則i的左子女為2*i+1，若2*i+2<n,則i的右子女為2*i+2若結(jié)點(diǎn)編號(hào)i為偶數(shù)，且i!=0,則左兄弟結(jié)點(diǎn)i-1.若結(jié)點(diǎn)編號(hào)i為奇數(shù)，且i!=n-1,則右兄弟結(jié)點(diǎn)為i+1.結(jié)點(diǎn)i所在層次為log2(i+1)

0712345689完全二叉樹一般二叉樹的順序表示的順序表示二叉樹的存儲(chǔ)結(jié)構(gòu)112345678910912340567800910248910567312365478順序表示910

單支樹由于一般二叉樹必須仿照完全二叉樹那樣存儲(chǔ)，可能會(huì)浪費(fèi)很多存儲(chǔ)空間，單支樹就是一個(gè)極端情況。鏈表表示lChilddatarChilddatalChildrChild二叉鏈表含兩個(gè)指針域的結(jié)點(diǎn)結(jié)構(gòu)lChilddataparentrChild含三個(gè)指針域的結(jié)點(diǎn)結(jié)構(gòu)parentdatalChildrChild三叉鏈表性質(zhì)：含有n個(gè)結(jié)點(diǎn)的二叉鏈表中有n+1個(gè)空鏈域。證明：對(duì)于葉結(jié)點(diǎn)n0有兩個(gè)空鏈域，n1有1個(gè)空鏈域，n2沒有空鏈域。所以空鏈域數(shù)＝2n0+n1將n0=n2+1代入得(根據(jù)性質(zhì)3)2n0+n1=n0+n1+n2+1=n+1二叉樹鏈表表示的示例AAABBBCCCDDDFFFEEErootrootroot二叉樹二叉鏈表三叉鏈表三叉鏈表的靜態(tài)結(jié)構(gòu)ABCDFErootdataparentleftChildrightChild012345A

-11-1B023C1

-1-1D145E3-1-1F3-1-1typedefcharTreeData; //結(jié)點(diǎn)數(shù)據(jù)類型typedefstructnode{ //結(jié)點(diǎn)定義TreeDatadata;structnode*leftChild,*rightchild;}BinTreeNode;typedefBinTreeNode*BinTree;

//根指針

二叉鏈表的定義二叉樹遍歷

樹的遍歷就是按某種次序訪問樹中的結(jié)點(diǎn)，要求每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次。設(shè)訪問根結(jié)點(diǎn)記作V遍歷根的左子樹記作L遍歷根的右子樹記作R則可能的遍歷次序有前序VLR中序LVR后序LRVVLR中序遍歷二叉樹算法的定義： 若二叉樹為空，則空操作； 否則 中序遍歷左子樹(L)； 訪問根結(jié)點(diǎn)(V)； 中序遍歷右子樹(R)。遍歷結(jié)果a+b*c-d-e/f中序遍歷(InorderTraversal)--/+*abcdefvoidInOrder(BinTreeNode*T){if(T!=NULL){InOrder(T->leftChild);Visit(T->data);InOrder(T->rightChild);}}中序遍歷二叉樹的遞歸算法中序遍歷二叉樹的遞歸過程圖解--/+*abcdef

if(T!=NULL){InOrder(T->leftChild);Visit(T->data);InOrder(T->rightChild);}前序遍歷二叉樹算法的定義：若二叉樹為空，則空操作；否則訪問根結(jié)點(diǎn)(V)；前序遍歷左子樹(L)；前序遍歷右子樹(R)。 遍歷結(jié)果

-+a*b-cd/ef前序遍歷(PreorderTraversal)--/+*abcdef前序遍歷二叉樹的遞歸算法voidPreOrder(BinTreeNode*T){if(T!=NULL){Visit(T->data);PreOrder(T->leftChild);PreOrder(T->rightChild);}}后序遍歷二叉樹算法的定義：若二叉樹為空，則空操作；否則后序遍歷左子樹(L)；后序遍歷右子樹(R)；訪問根結(jié)點(diǎn)(V)。遍歷結(jié)果abcd-*+ef/-后序遍歷(PostorderTraversal)--/+*abcdef后序遍歷二叉樹的遞歸算法：voidPostOrder(BinTreeNode*T){if(T!=NULL){

PostOrder(T->leftChild);

PostOrder(T->rightChild);Visit(T->data);}}二叉樹遍歷應(yīng)用以遞歸方式建立二叉樹。輸入結(jié)點(diǎn)值的順序必須對(duì)應(yīng)二叉樹結(jié)點(diǎn)前序遍歷的順序。并約定以輸入序列中不可能出現(xiàn)的值作為空結(jié)點(diǎn)的值以結(jié)束遞歸,此值在RefValue中。例如用“@”或用“-1”表示字符序列或正整數(shù)序列空結(jié)點(diǎn)。按前序建立二叉樹(遞歸算法)如圖所示的二叉樹的前序遍歷順序?yàn)锳BC@@DE@G@@F@@@ABCDEGF@@@@@@@@

StatusCreateBiTree(BiTree&T){scanf(&ch);if(ch==‘’)T=NULL;//讀入根結(jié)點(diǎn)的值else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);//建立根結(jié)點(diǎn)T->data=ch;

CreateBiTree(T->leftChild);

CreateBiTree(T->rightChild);}returnOK;}//CreateBiTreeintCount(BinTreeNode*T){if(T==NULL)return0;elsereturn1+Count(T->leftChild)+Count(T->rightChild);}2. 計(jì)算二叉樹結(jié)點(diǎn)個(gè)數(shù)(遞歸算法)intLeaf_Count(BitreeT){//求二叉樹中葉子結(jié)點(diǎn)的數(shù)目 if(!T)return0;//空樹沒有葉子 elseif(!T->lchild&&!T->rchild)return1;

//葉子結(jié)點(diǎn)

elsereturnLeaf_Count(T-lchild)+Leaf_Count(T-rchild);//左子樹的葉子數(shù)加上右子樹的葉子數(shù)

}3. 求二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)intHeight(BinTreeNode*T){if(T==NULL)return0;else { intm=Height(T->leftChild); intn=Height(T->rightChild)); return(m>n)?m+1:n+1; }}4. 求二叉樹高度(遞歸算法)5. 復(fù)制二叉樹(遞歸算法)BiTNode*Copy(BinTreeNode*T){ if(T==NULL)returnNULL; if(!(Temp=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW); Temp->data=T->data; Temp->leftChild=Copy(T->leftChild);

Temp->rightChild=Copy(T->rightChild); returnTemp;}6. 判斷二叉樹等價(jià)(遞歸算法)intEqual(BinTreeNode*a,BinTreeNode*b){if(a==NULL&&b==NULL)return1;if(a!==NULL&&b!==NULL &&a->data==b->data &&equal(a->leftChild,b->leftChild) &&equal(a->rightChild,b->rightChild)) return1;return0;//如果a和b的子樹不等同，則函數(shù)返回0}中序遍歷二叉樹(非遞歸算法)用棧實(shí)現(xiàn)baabcdeadaaab入棧b退棧訪問d入棧d退棧訪問e退棧訪問ecc?？?/p>

a退棧訪問ce入棧c

退棧訪問

voidInOrder(BinTreeT){

stackS;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);//退棧Visit(p->data);//訪問根Push(S,p->rchild);}//if}//whilereturnok;}abcde前序遍歷二叉樹(非遞歸算法)用棧實(shí)現(xiàn)acabcdedcc訪問a進(jìn)棧c左進(jìn)b訪問b進(jìn)棧d左進(jìn)空退棧d訪問d左進(jìn)空退棧c訪問c左進(jìn)e訪問e左進(jìn)空退棧結(jié)束voidPreOrder(BinTreeT){stackS;InitStack(S);//遞歸工作棧BinTreeNode*p=T;Push(S,NULL);while(p!=NULL){Visit(p->data);if(p->rightChild!=NULL)Push(S,p->rightChild);if(p->leftChild!=NULL)p=p->leftChild;//進(jìn)左子樹elsePop(S,p);}} abcde后序遍歷二叉樹(非遞歸算法)用棧實(shí)現(xiàn)后序遍歷時(shí)使用的棧的結(jié)點(diǎn)定義typedefstruct{BinTreeNode*ptr;//結(jié)點(diǎn)指針enumtag{L,R};//該結(jié)點(diǎn)退棧標(biāo)記}StackNode;

根結(jié)點(diǎn)的tag=L，表示從左子樹退出,訪問右子樹。tag=R,表示從右子樹退出,訪問根。ptrtag{L,R}

voidPostOrder(BinTreeT){stackS;InitStack(S);StackNodew;BinTreeNode*p=T;do{ while(p!=NULL){//向左子樹走

w.ptr=p;w.tag=L;Push(S,w);p=p->leftChild; }intcontinue=1; //繼續(xù)循環(huán)標(biāo)記

while(continue&&!StackEmpty(S)){Pop(S,w);p=w.ptr;switch(w.tag){//判斷棧頂tag標(biāo)記 caseL:w.tag=R;Push(S,w); continue=0; p=p->rightChild;break; caseR:Visit(p->data);}}}while(p!=NULL||!StackEmpty(S));}練習(xí):交換二叉樹各結(jié)點(diǎn)的左、右子樹

(遞歸算法)

練習(xí):交換二叉樹各結(jié)點(diǎn)的左、右子樹

(遞歸算法)voidunknown(BinTreeNode*T){BinTreeNode*p=T,*temp;if(p!=NULL){temp=p->leftChild;p->leftChild=p->rightChild;p->rightChild=temp;

unknown(p->leftChild);unknown(p->rightChild);}}voidunknown(BinTreeNode*T){BinTreeNode*p=T,*temp;

while(p!=NULL){temp=p->leftChild;p->leftChild=p->rightChild;p->rightChild=temp;

unknown(p->leftChild);

p=p->rightChild;}}不用棧消去遞歸算法中的第二個(gè)遞歸語句

使用棧消去遞歸算法中的兩個(gè)遞歸語句voidunknown(BinTreeNode*T){BinTreeNode*p,*temp;stackS;InitEmpty(&S);

if(T!=NULL){push(&S,T);while(!StackEmpty(&S)){

Pop(&S,p);

//棧中退出一個(gè)結(jié)點(diǎn)temp=p->leftChild;//交換子女p->leftChild=p->rightChild;p->rightChild=temp;

if(p->rightChild!=NULL)push(&S,p->rightChild);if(p->leftChild!=NULL)push(&S,p->leftChild);}}}對(duì)二叉樹遍歷的過程實(shí)質(zhì)上是對(duì)一個(gè)非線性結(jié)構(gòu)進(jìn)行線性化的操作.以二叉鏈表為存儲(chǔ)結(jié)構(gòu)時(shí),結(jié)點(diǎn)的左右孩子可以直接找到,但不能直接找到結(jié)點(diǎn)的前驅(qū)和后繼,而結(jié)點(diǎn)的前驅(qū)和后繼只有在遍歷二叉樹的過程中才能得到.用二叉鏈表表示的二叉樹中,n個(gè)結(jié)點(diǎn)的二叉樹有n+1個(gè)空鏈域，可利用這些空鏈域存儲(chǔ)結(jié)點(diǎn)的前驅(qū)或后繼。線索二叉樹

(ThreadedBinaryTree)LeftThread=0,LeftChild為左子女指針LeftThread=1,LeftChild為前驅(qū)線索RightThread=0,RightChild為右子女指針RightThread=1,RightChild為后繼指針LeftChildRightChilddataLeftThreadRightThread結(jié)點(diǎn)結(jié)構(gòu)typedefenum{Link,Thread}PointerTag;//PointerTag為標(biāo)志，Link=0代表指針，Thread=1代表線索typedefstructBiThrNode{ TElemTypedata; structBiThrNode*lchild,*rchild; PointerTagLTag,RTag;}BiThrNode,*BiThrTree;中序線索二叉樹BDAEC帶表頭結(jié)點(diǎn)的中序線索二叉樹if(currentrightThread==1)if(currentrightChild!=T.root)

后繼為

currentrightChildelse無后繼else//currentrightThread!=1if(currentrightChild!=T.root)

后繼為當(dāng)前結(jié)點(diǎn)右子樹的中序下的第一個(gè)結(jié)點(diǎn)

else

出錯(cuò)情況

尋找當(dāng)前結(jié)點(diǎn)在中序下的后繼ABDECFHIKGJLif(currentleftThread==1)

if(currentleftChild!=T.root)

前驅(qū)為currentleftChild

else

無前驅(qū)else//currentleftThread==0

if(currentleftChild!=T.root)

前驅(qū)為當(dāng)前結(jié)點(diǎn)左子樹的

中序下的最后一個(gè)結(jié)點(diǎn)

else

出錯(cuò)情況

尋找當(dāng)前結(jié)點(diǎn)在中序下的前驅(qū)ABDECFHIKGJLStatusInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(TElemTypee)){ p=T->lchild; while(p!=T){ while(p->LTag==Link)p=p->lchild; if(!Visit(p->data))returnERROR; while(p->RTag==Thread&&p->rchild!=T){ p=p->rchild;Visit(p->data); } p=p->rchild; }}//InOrderTraverse_Thr中序遍歷線索二叉樹后序線索二叉樹中尋找后繼后繼：(1)根的后繼為空。 (2)如果結(jié)點(diǎn)是雙親的右孩子或是左孩子但雙親沒有右子樹，則后繼是其雙親。 (3)如果結(jié)點(diǎn)是雙親的左孩子且雙親有右子樹，則后繼是雙親右子樹上先遍歷到的結(jié)點(diǎn)?？傊?，如果二叉樹的應(yīng)用主要是遍歷或查找結(jié)點(diǎn)的前驅(qū)和后繼則使用線索二叉樹更為合適。后序線索化二叉樹后序序列

DBECA在后序線索化二叉樹中尋找當(dāng)前結(jié)點(diǎn)的后繼前序線索化二叉樹前序序列

ABDCE在前序線索化二叉樹中尋找當(dāng)前結(jié)點(diǎn)的后繼通過中序遍歷建立中序線索化二叉樹StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//中序遍歷并線索化二叉樹，Thrt為頭結(jié)點(diǎn) if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(OVERFLOW);//建頭結(jié)點(diǎn) Thrt->LTag=Link; Thrt->RTag=Thread; Thrt->rchild=Thrt;//頭結(jié)點(diǎn)右指針回指 if(!T)Thrt->lchild=Thrt;//如果二叉樹為空，則左指針也回指 else{ Thrt->lchild=T;pre=Thrt;//pre總是指向最后一個(gè)訪問過的結(jié)點(diǎn)，也就是其后要訪問結(jié)點(diǎn)的前驅(qū) InThreading(T);//線索化的主過程 pre->rchild=Thrt;pre->RTag=Thread; Thrt->rchild=pre;//將最后一個(gè)結(jié)點(diǎn)線索化 } returnOK;}//InOrderThreadingvoidInThreading(BiThrTreep){ 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為下一結(jié)點(diǎn)的前驅(qū) InThreading(p->rchild);//右子樹線索化 }}//InThreading樹的存儲(chǔ)結(jié)構(gòu)雙親表示：以一組連續(xù)空間存儲(chǔ)樹的結(jié)點(diǎn)，同時(shí)在結(jié)點(diǎn)中附設(shè)一個(gè)指針，存放雙親結(jié)點(diǎn)在鏈表中的位置。該方法利用每個(gè)結(jié)點(diǎn)只有一個(gè)雙親的特點(diǎn)，可以很方便求結(jié)點(diǎn)的雙親，但不方便求結(jié)點(diǎn)的孩子。樹與森林ABCDEFGdataparentABCDEFG-10001130123456用雙親表示實(shí)現(xiàn)的樹定義#defineMaxSize 100//最大結(jié)點(diǎn)個(gè)數(shù)typedefcharTreeData;//結(jié)點(diǎn)數(shù)據(jù)typedefstruct{//樹結(jié)點(diǎn)定義TreeDatadata;intparent;}TreeNode;typedefTreeNodeTree[MaxSize];//樹ABCDEFG孩子表示法(多重鏈表

)第一種解決方案等數(shù)量的鏈域(d為樹的度)

data

child1child2child3childdABCDEFG空鏈域n(d-1)+1個(gè)第二種解決方案孩子鏈表將每個(gè)結(jié)點(diǎn)的孩子鏈在該結(jié)點(diǎn)之后組成鏈表，再將所有頭結(jié)點(diǎn)組成一個(gè)線性表。typedefstructCTNode{ intchild; structCTNode*next;}*ChildPtr;typedefstruct{ TElemTypedata; ChildPtrfirstchild;}CTBox;typedefstruct{ CTBoxnodes[MAX_TREE_SIZE]; intn,r;//結(jié)點(diǎn)數(shù)和根的位置}CTree;ABCDEFG0A1B2C^3D4E^5F^6G^123^45^6^結(jié)點(diǎn)結(jié)構(gòu)

datafirstChildnextSiblingABCDEFG空鏈域n+1個(gè)樹的左子女-右兄弟表示（二叉鏈表表示）BCDGFEAtypedefcharTreeData;typedefstructnode{TreeDatadata;structnode*firstChild,*nextSibling;}TreeNode;typedefTreeNode*Tree;用左子女-右兄弟表示實(shí)現(xiàn)的樹定義T1T2T3T1T2T3AFHBCDGIJEKAFBCDEGHIKJABCEDHIKJFG3棵樹的森林各棵樹的二叉樹表示森林的二叉樹表示森林與二叉樹的轉(zhuǎn)換樹的二叉樹表示:樹的遍歷深度優(yōu)先遍歷先根次序遍歷后根次序遍歷ABCDEFGABCEDGF深度優(yōu)先遍歷當(dāng)樹非空時(shí){訪問根結(jié)點(diǎn)依次先根遍歷根的各棵子樹}樹先根遍歷ABEFCDG對(duì)應(yīng)二叉樹前序遍歷ABEFCDG樹的先根遍歷結(jié)果與其對(duì)應(yīng)二叉樹表示的前序遍歷結(jié)果相同樹的先根遍歷可以借助對(duì)應(yīng)二叉樹的前序遍歷算法實(shí)現(xiàn)ABCEDGF樹的先根次序遍歷ABCDEFG樹的后根次序遍歷:當(dāng)樹非空時(shí){依次后根遍歷根的各棵子樹訪問根結(jié)點(diǎn)}樹后根遍歷EFBCGDA對(duì)應(yīng)二叉樹中序遍歷EFBCGDA樹的后根遍歷結(jié)果與其對(duì)應(yīng)二叉樹表示的中序遍歷結(jié)果相同樹的后根遍歷可以借助對(duì)應(yīng)二叉樹的中序遍歷算法實(shí)現(xiàn)ABCEDGFABCDEFG二叉樹的計(jì)數(shù)

由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹。例,前序序列{ABHFDECKG}和中序序列{HBDFAEKCG},構(gòu)造二叉樹過程如下：HBDFEKCGAEKCGABHDFKCGEKCGABHDFEKCGABHFDEABHFDEABHFDCKG

如果前序序列固定不變，給出不同的中序序列，可得到不同的二叉樹。612345789612375849問題是有n

個(gè)數(shù)據(jù)值，可能構(gòu)造多少種不同的二叉樹？我們可以固定前序排列，選擇所有可能的中序排列。

例如,有3個(gè)數(shù)據(jù){1,2,3}，可得5種不同的二叉樹。它們的前序排列均為

123，中序序列可能是321，231，213，132，123.123123123123123

具有n個(gè)結(jié)點(diǎn)不同形態(tài)的樹的數(shù)目和具有n-1個(gè)結(jié)點(diǎn)互不相似的二叉樹的數(shù)目相同。

有0個(gè),1個(gè),2個(gè),3個(gè)結(jié)點(diǎn)的不同二叉樹如下b0=1b1=1b2=2b3=5

b4=14計(jì)算具有n個(gè)結(jié)點(diǎn)的不同二叉樹的棵數(shù)最終結(jié)果：bibn-i-11霍夫曼樹(HuffmanTree)路徑長度(PathLength)

兩個(gè)結(jié)點(diǎn)之間的路徑長度

PL是連接兩結(jié)點(diǎn)的路徑上的分支數(shù)。樹的外部路徑長度是各葉結(jié)點(diǎn)(外結(jié)點(diǎn))到根結(jié)點(diǎn)的路徑長度之和EPL。樹的內(nèi)部路徑長度是各非葉結(jié)點(diǎn)(內(nèi)結(jié)點(diǎn))到根結(jié)點(diǎn)的路徑長度之和IPL。

樹的路徑長度PL=EPL+IPL123456782345678樹的外部路徑長度EPL=3*1+2*3=9樹的外部路徑長度EPL=1*1+2*1+3*1+4*1=101帶權(quán)路徑長度

(WeightedPathLength,WPL)

二叉樹的帶權(quán)(外部)路徑長度是樹的各葉結(jié)點(diǎn)所帶的權(quán)值

wi

與該結(jié)點(diǎn)到根的路徑長度

li

的乘積的和。WPL=2*2+WPL=2*1+WPL=7*1+4*2+5*2+4*2+5*3+5*2+2*3+7*2=367*3=464*3=35222444555777帶權(quán)(外部)路徑長度達(dá)到最小霍夫曼樹帶權(quán)路徑長度達(dá)到最小的二叉樹即為霍夫曼樹。在霍夫曼樹中，權(quán)值大的結(jié)點(diǎn)離根最近。

(1)由給定的n個(gè)權(quán)值{w0,w1,w2,…,wn-1}，構(gòu)造具有n棵擴(kuò)充二叉樹的森林F={T0,T1,T2,…,Tn-1}，其中每棵擴(kuò)充二叉樹Ti只有一個(gè)帶權(quán)值wi的根結(jié)點(diǎn),其左、右子樹均為空。霍夫曼算法

(2)重復(fù)以下步驟,直到F中僅剩下一棵樹為止：

①在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的擴(kuò)充二叉樹,做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。②在F中刪去這兩棵二叉樹。③把新的二叉樹加入F。

F:{7}{5}{2}{4}F:{7}{5}{6}F:{7}{11}7524初始合并{2}{4}75246F:{18}1175246合并{5}{6}5合并{7}{11}27461118舉例霍夫曼樹的構(gòu)造過程5274WeightparentleftChildrightChild7

-1-1-15

-1-1-12

-1-1-14

-1-1-1

-1-1-1

-1-1-1

-1-1-10123456上例存儲(chǔ)結(jié)構(gòu)初態(tài)52746WeightparentleftChildrightChild7

-1-1-15

-1-1-12

-1-1-14

-1-1-16

-1-1-1

-1-1-1

-1-1-10123456p1p24423i過程5274611WeightparentleftChildrightChild7

-1-1-15

-1-1-12

4

-1-14

4

-1-16

-12

311

-1-1-1

-1-1-10123456p1p25514i5274611WeightparentleftChildrightChild7

-1-1-15

5

-1-12

4

-1-14

4

-1-16

5

2

311

-11

418

-1-1-10123456p1p26605i18終態(tài)constintn=20;//葉結(jié)點(diǎn)數(shù)constintm=2*n-1;//結(jié)點(diǎn)數(shù)

typedefstruct{floatweight;intparent,leftChild,rightChild;}HTNode;typedefHTNodeHuffmanTree[m];霍夫曼樹的定義建立霍夫曼樹的算法voidCreateHuffmanTree(HuffmanTreeT,floatfr[]){