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

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

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

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

T1,T2,…,Tm，其中每個(gè)集合本身又是一棵樹(shù)，并且稱(chēng)為根的子樹(shù)(SubTree)。ACGBDEFKLHMIJ例如A只有根結(jié)點(diǎn)的樹(shù)有13個(gè)結(jié)點(diǎn)的樹(shù)其中：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ù)，且本身也是一棵樹(shù)樹(shù)的基本術(shù)語(yǔ)1層2層4層3層height=4ACGBDEFKLHMIJ結(jié)點(diǎn)結(jié)點(diǎn)的度葉結(jié)點(diǎn)分支結(jié)點(diǎn)子女雙親兄弟祖先子孫結(jié)點(diǎn)層次樹(shù)的深度樹(shù)的度有序樹(shù)無(wú)序樹(shù)森林結(jié)點(diǎn)：一個(gè)數(shù)據(jù)元素及指向其子樹(shù)的分支。結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹(shù)個(gè)數(shù)。葉結(jié)點(diǎn)：度為零的結(jié)點(diǎn)。子女：結(jié)點(diǎn)子樹(shù)的根。兄弟：同一結(jié)點(diǎn)子女。祖先：根到該結(jié)點(diǎn)路徑上的所有結(jié)點(diǎn)。子孫：某結(jié)點(diǎn)為根的子樹(shù)上的任意結(jié)點(diǎn)。結(jié)點(diǎn)層次：從根開(kāi)始，根為第一層，根的子女為第二層，以此類(lèi)推。樹(shù)的深度（高度）：樹(shù)中結(jié)點(diǎn)的最大層次數(shù)。有序樹(shù)：樹(shù)中結(jié)點(diǎn)的子樹(shù)由左向右有序。森林：m(m0)棵互不相交的樹(shù)。二叉樹(shù)(BinaryTree)定義五種形態(tài) 一棵二叉樹(shù)是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱(chēng)為左子樹(shù)和右子樹(shù)的、互不相交的二叉樹(shù)組成。LLRR特點(diǎn)每個(gè)結(jié)點(diǎn)至多只有兩棵子樹(shù)（二叉樹(shù)中不存在度大于2的結(jié)點(diǎn)）性質(zhì)1 在二叉樹(shù)的第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)。由于二叉樹(shù)的每個(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的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)(k1)。證明：由性質(zhì)1可見(jiàn)，深度為k的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)為

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

對(duì)任何一棵二叉樹(shù)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ù)二叉樹(shù)的定義，n=n0+n1+n2e=2n2+n1=n-1因此，有2n2+n1=n0+n1+n2

-1n2=n0

-1n0=n2+1定義1

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

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

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

證明： 設(shè)完全二叉樹(shù)的深度為h，則根據(jù)性質(zhì)2和完全二叉樹(shù)的定義有 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)的完全二叉樹(shù)自頂向下，同一層自左向右連續(xù)給結(jié)點(diǎn)編號(hào)0,1,2,…,n-1，則有以下關(guān)系：

若i=0,則i無(wú)雙親若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完全二叉樹(shù)一般二叉樹(shù)的順序表示的順序表示二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)112345678910912340567800910248910567312365478順序表示910

單支樹(shù)由于一般二叉樹(shù)必須仿照完全二叉樹(shù)那樣存儲(chǔ)，可能會(huì)浪費(fèi)很多存儲(chǔ)空間，單支樹(shù)就是一個(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沒(méi)有空鏈域。所以空鏈域數(shù)＝2n0+n1將n0=n2+1代入得(根據(jù)性質(zhì)3)2n0+n1=n0+n1+n2+1=n+1二叉樹(shù)鏈表表示的示例AAABBBCCCDDDFFFEEErootrootroot二叉樹(shù)二叉鏈表三叉鏈表三叉鏈表的靜態(tài)結(jié)構(gòu)ABCDFErootdataparentleftChildrightChild012345A

-11-1B023C1

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

//根指針

二叉鏈表的定義二叉樹(shù)遍歷

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

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

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

PostOrder(T->leftChild);

PostOrder(T->rightChild);Visit(T->data);}}二叉樹(shù)遍歷應(yīng)用以遞歸方式建立二叉樹(shù)。輸入結(jié)點(diǎn)值的順序必須對(duì)應(yīng)二叉樹(shù)結(jié)點(diǎn)前序遍歷的順序。并約定以輸入序列中不可能出現(xiàn)的值作為空結(jié)點(diǎn)的值以結(jié)束遞歸,此值在RefValue中。例如用“@”或用“-1”表示字符序列或正整數(shù)序列空結(jié)點(diǎn)。按前序建立二叉樹(shù)(遞歸算法)如圖所示的二叉樹(shù)的前序遍歷順序?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ì)算二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)(遞歸算法)intLeaf_Count(BitreeT){//求二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目 if(!T)return0;//空樹(shù)沒(méi)有葉子 elseif(!T->lchild&&!T->rchild)return1;

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

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

}3. 求二叉樹(shù)中葉子結(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. 求二叉樹(shù)高度(遞歸算法)5. 復(fù)制二叉樹(shù)(遞歸算法)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. 判斷二叉樹(shù)等價(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ù)不等同，則函數(shù)返回0}中序遍歷二叉樹(shù)(非遞歸算法)用棧實(shí)現(xiàn)baabcdeadaaab入棧b退棧訪(fǎng)問(wèn)d入棧d退棧訪(fǎng)問(wèn)e退棧訪(fǎng)問(wèn)ecc?？?/p>

a退棧訪(fǎng)問(wèn)ce入棧c

退棧訪(fǎng)問(wèn)

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);//訪(fǎng)問(wèn)根Push(S,p->rchild);}//if}//whilereturnok;}abcde前序遍歷二叉樹(shù)(非遞歸算法)用棧實(shí)現(xiàn)acabcdedcc訪(fǎng)問(wèn)a進(jìn)棧c左進(jìn)b訪(fǎng)問(wèn)b進(jìn)棧d左進(jìn)空退棧d訪(fǎng)問(wèn)d左進(jìn)空退棧c訪(fǎng)問(wèn)c左進(jìn)e訪(fǎng)問(wèn)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)左子樹(shù)elsePop(S,p);}} abcde后序遍歷二叉樹(shù)(非遞歸算法)用棧實(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，表示從左子樹(shù)退出,訪(fǎng)問(wèn)右子樹(shù)。tag=R,表示從右子樹(shù)退出,訪(fǎng)問(wèn)根。ptrtag{L,R}

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

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í):交換二叉樹(shù)各結(jié)點(diǎn)的左、右子樹(shù)

(遞歸算法)

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

(遞歸算法)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è)遞歸語(yǔ)句

使用棧消去遞歸算法中的兩個(gè)遞歸語(yǔ)句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ù)遍歷的過(guò)程實(shí)質(zhì)上是對(duì)一個(gè)非線(xiàn)性結(jié)構(gòu)進(jìn)行線(xiàn)性化的操作.以二叉鏈表為存儲(chǔ)結(jié)構(gòu)時(shí),結(jié)點(diǎn)的左右孩子可以直接找到,但不能直接找到結(jié)點(diǎn)的前驅(qū)和后繼,而結(jié)點(diǎn)的前驅(qū)和后繼只有在遍歷二叉樹(shù)的過(guò)程中才能得到.用二叉鏈表表示的二叉樹(shù)中,n個(gè)結(jié)點(diǎn)的二叉樹(shù)有n+1個(gè)空鏈域，可利用這些空鏈域存儲(chǔ)結(jié)點(diǎn)的前驅(qū)或后繼。線(xiàn)索二叉樹(shù)

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

后繼為

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

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

else

出錯(cuò)情況

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

if(currentleftChild!=T.root)

前驅(qū)為currentleftChild

else

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

if(currentleftChild!=T.root)

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

中序下的最后一個(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中序遍歷線(xiàn)索二叉樹(shù)后序線(xiàn)索二叉樹(shù)中尋找后繼后繼：(1)根的后繼為空。 (2)如果結(jié)點(diǎn)是雙親的右孩子或是左孩子但雙親沒(méi)有右子樹(shù)，則后繼是其雙親。 (3)如果結(jié)點(diǎn)是雙親的左孩子且雙親有右子樹(shù)，則后繼是雙親右子樹(shù)上先遍歷到的結(jié)點(diǎn)?？傊?，如果二叉樹(shù)的應(yīng)用主要是遍歷或查找結(jié)點(diǎn)的前驅(qū)和后繼則使用線(xiàn)索二叉樹(shù)更為合適。后序線(xiàn)索化二叉樹(shù)后序序列

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

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

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

data

child1child2child3childdABCDEFG空鏈域n(d-1)+1個(gè)第二種解決方案孩子鏈表將每個(gè)結(jié)點(diǎn)的孩子鏈在該結(jié)點(diǎn)之后組成鏈表，再將所有頭結(jié)點(diǎn)組成一個(gè)線(xiàn)性表。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è)樹(shù)的左子女-右兄弟表示（二叉鏈表表示）BCDGFEAtypedefcharTreeData;typedefstructnode{TreeDatadata;structnode*firstChild,*nextSibling;}TreeNode;typedefTreeNode*Tree;用左子女-右兄弟表示實(shí)現(xiàn)的樹(shù)定義T1T2T3T1T2T3AFHBCDGIJEKAFBCDEGHIKJABCEDHIKJFG3棵樹(shù)的森林各棵樹(shù)的二叉樹(shù)表示森林的二叉樹(shù)表示森林與二叉樹(shù)的轉(zhuǎn)換樹(shù)的二叉樹(shù)表示:樹(shù)的遍歷深度優(yōu)先遍歷先根次序遍歷后根次序遍歷ABCDEFGABCEDGF深度優(yōu)先遍歷當(dāng)樹(shù)非空時(shí){訪(fǎng)問(wèn)根結(jié)點(diǎn)依次先根遍歷根的各棵子樹(shù)}樹(shù)先根遍歷ABEFCDG對(duì)應(yīng)二叉樹(shù)前序遍歷ABEFCDG樹(shù)的先根遍歷結(jié)果與其對(duì)應(yīng)二叉樹(shù)表示的前序遍歷結(jié)果相同樹(shù)的先根遍歷可以借助對(duì)應(yīng)二叉樹(shù)的前序遍歷算法實(shí)現(xiàn)ABCEDGF樹(shù)的先根次序遍歷ABCDEFG樹(shù)的后根次序遍歷:當(dāng)樹(shù)非空時(shí){依次后根遍歷根的各棵子樹(shù)訪(fǎng)問(wèn)根結(jié)點(diǎn)}樹(shù)后根遍歷EFBCGDA對(duì)應(yīng)二叉樹(shù)中序遍歷EFBCGDA樹(shù)的后根遍歷結(jié)果與其對(duì)應(yīng)二叉樹(shù)表示的中序遍歷結(jié)果相同樹(shù)的后根遍歷可以借助對(duì)應(yīng)二叉樹(shù)的中序遍歷算法實(shí)現(xiàn)ABCEDGFABCDEFG二叉樹(shù)的計(jì)數(shù)

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

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

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

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

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

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

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

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

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

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

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

(WeightedPathLength,WPL)

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

wi

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

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)(外部)路徑長(zhǎng)度達(dá)到最小霍夫曼樹(shù)帶權(quán)路徑長(zhǎng)度達(dá)到最小的二叉樹(shù)即為霍夫曼樹(shù)。在霍夫曼樹(shù)中，權(quán)值大的結(jié)點(diǎn)離根最近。

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

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

①在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的擴(kuò)充二叉樹(shù),做為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)。置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和。②在F中刪去這兩棵二叉樹(shù)。③把新的二叉樹(shù)加入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舉例霍夫曼樹(shù)的構(gòu)造過(guò)程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過(guò)程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];霍夫曼樹(shù)的定義建立霍夫曼樹(shù)的算法voidCreateHuffmanTree(HuffmanTreeT,floatfr[]){