經(jīng)濟學(xué)樹和二叉樹

6.1樹的概念與定義樹是n（n≥0）個結(jié)點的有限集合T。當(dāng)n=0時，稱為空樹；當(dāng)n>0時，該集合滿足如下條件：(1)其中必有一個稱為根（root）的特定結(jié)點，它沒有直接前驅(qū)，但有零個或多個直接后繼。(2)其余n-1個結(jié)點可以劃分成m（m≥0）個互不相交的有限集T1，T2，T3，…，Tm，其中Ti又是一棵樹，稱為根root的子樹。每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但有零個或多個直接后繼。例如：ACGBDEFKLHMIJA只有根結(jié)點的樹有13個結(jié)點的樹其中：A是根；其余結(jié)點分成三個互不相交的子集，T1={B,E,F,K,L}；T2={C,G}；T3={D,H,I,J,M},T1,T2,T3都是根A的子樹，且本身也是一棵樹1.樹型表示法2.嵌套集合表示法ABCDABCD3.廣義表表示法(A(B(D),C))3.凹入表示法樹的表示法ABDC樹的基本術(shù)語1層2層4層3層height=4ACGBDEFKLHMIJ結(jié)點結(jié)點的度葉結(jié)點分支結(jié)點子女雙親兄弟祖先子孫結(jié)點層次樹的深度樹的度森林有關(guān)樹的一些術(shù)語：結(jié)點：包含一個數(shù)據(jù)元素及若干指向其它結(jié)點的分支信息。結(jié)點的度：一個結(jié)點的子樹個數(shù)稱為此結(jié)點的度。葉結(jié)點：度為0的結(jié)點，即無后繼的結(jié)點，也稱為終端結(jié)點。分支結(jié)點：度不為0的結(jié)點，也稱為非終端結(jié)點。孩子結(jié)點：一個結(jié)點的直接后繼稱為該結(jié)點的孩子結(jié)點。如上圖的B、C、D是A的孩子。雙親結(jié)點：一個結(jié)點的直接前驅(qū)稱為該結(jié)點的雙親結(jié)點。上圖中A是B、C、D的雙親。兄弟結(jié)點：同一雙親結(jié)點的孩子結(jié)點之間互稱兄弟結(jié)點。上圖中的結(jié)點H、I、J互為兄弟結(jié)點。祖先結(jié)點：一個結(jié)點的祖先結(jié)點是指從根結(jié)點到該結(jié)點的路徑上的所有結(jié)點。如結(jié)點K的祖先結(jié)點是A、B、E。子孫結(jié)點：一個結(jié)點的直接后繼和間接后繼稱為該結(jié)點的子孫結(jié)點。如結(jié)點D的子孫是H、I、J、M。樹的度：樹中所有結(jié)點的度的最大值。堂兄弟結(jié)點：其雙親在同一層的結(jié)點。如結(jié)點G與結(jié)點E、F、H、I、J互為堂兄弟。結(jié)點的層次：從根結(jié)點開始定義，根結(jié)點的層次為1，根的直接后繼的層次為2，依此類推。樹的高度（深度）：樹中所有結(jié)點的層次的最大值。有序樹：在樹T中，如果各子樹Ti之間是有先后次序的，則稱為有序樹。森林：m（m≥0）棵互不相交的樹的集合。將一棵非空樹的根結(jié)點刪去，樹就變成一個森林；反之，給森林增加一個統(tǒng)一的根結(jié)點，森林就變成一棵樹。樹的抽象數(shù)據(jù)類型定義：數(shù)據(jù)對象D：一個集合，該集合中的所有元素具有相同的特性。數(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)除root以外，D中每個結(jié)點在關(guān)系H下都有且僅有一個前驅(qū)。基本操作：InitTree（Tree）：將Tree初始化為一棵空樹。(2)DestoryTree（Tree）：銷毀樹Tree。(3)CreateTree（Tree）：創(chuàng)建樹Tree。(4)TreeEmpty（Tree）：若Tree為空，則返回TRUE，否則返回FALSE。(5)Root（Tree）：返回樹Tree的根。(6)Parent（Tree，x）：樹Tree存在，x是Tree中的某個結(jié)點。若x為非根結(jié)點，則返回它的雙親，否則返回“空”。(7)FirstChild（Tree，x）：樹Tree存在，x是Tree中的某個結(jié)點。若x為非葉子結(jié)點，則返回它的第一個孩子結(jié)點，否則返回“空”。(8)NextSubing（Tree，x）：樹Tree存在，x是Tree中的某個結(jié)點。若x不是其雙親的最后一個孩子結(jié)點，則返回x后面的下一個兄弟結(jié)點，否則返回“空”。(9)InsertChild（Tree，p，Child）：樹Tree存在，p指向Tree中某個結(jié)點，非空樹Child與Tree不相交。將Child插入Tree中，做p所指向結(jié)點的子樹?；静僮?基本操作:(10)DeleteChild（Tree，p，i）：樹Tree存在，p指向Tree中某個結(jié)點，1≤i≤d，d為p所指向結(jié)點的度。刪除Tree中p所指向結(jié)點的第i棵子樹。(11)TraverseTree（Tree，Visit（））：樹Tree存在，Visit（）是對結(jié)點進行訪問的函數(shù)。按照某種次序?qū)銽ree的每個結(jié)點調(diào)用Visit（）函數(shù)訪問一次且最多一次。若Visit（）失敗，則操作失敗。6.2二叉數(shù)6.2.1二叉樹的定義與基本操作6.2.2二叉樹的性質(zhì)6.2.3二叉樹的存儲結(jié)構(gòu)6.2.1二叉樹的定義與基本操作定義：我們把滿足以下兩個條件的樹型結(jié)構(gòu)叫做二叉樹（BinaryTree）：（1）每個結(jié)點的度都不大于2；（2）每個結(jié)點的孩子結(jié)點次序不能任意顛倒。下面給出二叉樹的五種基本形態(tài)：(a)空二叉數(shù)(c)只有左子樹的二叉樹(b)只有根結(jié)點的二叉樹(d)左右子樹均非空的二叉樹(e)只有右子樹的二叉樹二叉樹的基本操作：Initiate（bt）：將bt初始化為空二叉樹。(2)Create(bt)：創(chuàng)建一棵非空二叉樹bt。(3)Destroy（bt）：銷毀二叉樹bt。(4)Empty（bt）：若bt為空，則返回TRUE，否則返回FALSE。(5)Root(bt)：求二叉樹bt的根結(jié)點。若bt為空二叉樹，則函數(shù)返回“空”。(6)Parent（bt，x）：求雙親函數(shù)。求二叉樹bt中結(jié)點x的雙親結(jié)點。若結(jié)點x是二叉樹的根結(jié)點或二叉樹bt中無結(jié)點x，則返回“空”。基本操作：(7)LeftChild（bt，x）：求左孩子。若結(jié)點x為葉子結(jié)點或x不在bt中，則返回“空”。(8)RightChild（bt，x）：求右孩子。若結(jié)點x為葉子結(jié)點或x不在bt中，則返回“空”。(9)Traverse（bt）:遍歷操作。按某個次序依次訪問二叉樹中每個結(jié)點一次且僅一次。(10)Clear（bt）：清除操作。將二叉樹bt置為空樹。6.2.2二叉樹的性質(zhì)性質(zhì)1：在二叉樹的第i層上至多有2i-1個結(jié)點(i≥1)。

當(dāng)i=1時，整個二叉樹只有一根結(jié)點，此時2i-1=20=1，結(jié)論成立。

證明：假設(shè)i=k時結(jié)論成立，即第k層上結(jié)點總數(shù)最多為2k-1個。

現(xiàn)證明當(dāng)i=k+1時，結(jié)論成立：因為二叉樹中每個結(jié)點的度最大為2，則第k+1層的結(jié)點總數(shù)最多為第k層上結(jié)點最大數(shù)的2倍，即2×2k-1=2(k+1)-1，故結(jié)論成立。性質(zhì)2：深度為k的二叉樹至多有2k-1個結(jié)點（k≥1）。證明：由性質(zhì)1可見，深度為k的二叉樹的最大結(jié)點數(shù)為故結(jié)論成立。

＝20+21+…+2k-1=2k-1＝性質(zhì)3：對任意一棵二叉樹T，若終端結(jié)點數(shù)為n0，而其度數(shù)為2的結(jié)點數(shù)為n2，則n0=n2+1。證明：設(shè)二叉樹中結(jié)點總數(shù)為n，n1為二叉樹中度為1的結(jié)點總數(shù)。因為二叉樹中所有結(jié)點的度小于等于2，所以有

n=n0+n1+n2設(shè)二叉樹中分支數(shù)目為B，因為除根結(jié)點外，每個結(jié)點均對應(yīng)一個進入它的分支，所以有：n=B+1。又因為二叉樹中的分支都是由度為1和度為2的結(jié)點發(fā)出，所以分支數(shù)目為： B=n1+2n2整理上述兩式可得到：n=B+1=n1+2n2+1將n=n0+n1+n2代入上式得出n0+n1+n2=n1+2n2+1，整理后得n0=n2+1，故結(jié)論成立。兩種特殊的二叉樹：定義1：滿二叉樹(FullBinaryTree)

深度為k且有2k-1個結(jié)點的二叉樹。在滿二叉樹中，每層結(jié)點都是滿的，即每層結(jié)點都具有最大結(jié)點數(shù)。123456789101112131415滿二叉樹定義2：完全二叉樹：1234567891011121314關(guān)系：滿二叉樹必為完全二叉樹，而完全二叉樹不一定是滿二叉樹。若設(shè)二叉樹的高度為h，則共有h層。除第h層外，其它各層(0h-1)的結(jié)點數(shù)都達到最大個數(shù)，第h層從右向左連續(xù)缺若干結(jié)點，這就是完全二叉樹。2154367216543非完全二叉樹性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為

㏒2n

+1。證明：設(shè)n個結(jié)點的完全二叉樹的深度為k，根據(jù)性質(zhì)2可知，k-1層滿二叉樹的結(jié)點總數(shù)為：2k-1-1

k層滿二叉樹的結(jié)點總數(shù)為：2k-1

顯然有：

2k-1-1<n2k-1

2k-1

n

<2k

取對數(shù)有：k-1log2n<k

log2n

<

klog2n+1

因為k是整數(shù)，k=

㏒2n

+1結(jié)論成立。性質(zhì)5：對于具有n個結(jié)點的完全二叉樹，如果按照從上到下和從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點從1開始順序編號，則對于任意的序號為i的結(jié)點有：(1)若i=1,則i無雙親結(jié)點若i>1,則i的雙親結(jié)點為

i/2

(2)若2*i>n,則i無左孩子若2*i≤n,則i結(jié)點的左孩子結(jié)點為2*i(3)若2*i+1

>n,則i無右孩子若2*i+1≤n,則i的右孩子結(jié)點為2*i+1用歸納法證明其中的(2)和(3)。124891056736.2.3二叉樹的存儲結(jié)構(gòu)

二叉樹的結(jié)構(gòu)是非線性的，每一結(jié)點最多可有兩個后繼。

二叉樹的存儲結(jié)構(gòu)有兩種：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。完全二叉樹一般二叉樹的順序表示的順序表示二叉樹的存儲結(jié)構(gòu)123456789109123405678009101248910567312365478順序表示910

對于一般的二叉樹，我們必須按照完全二叉樹的形式來存儲，就會造成空間的浪費。單支樹就是一個極端情況。ABCDA^B^^^C^^^^^^^D單支樹鏈表表示lChilddatarChilddatalChildrChild二叉鏈表含兩個指針域的結(jié)點結(jié)構(gòu)lChilddataparentrChild含三個指針域的結(jié)點結(jié)構(gòu)parentdatalChildrChild三叉鏈表二叉樹鏈表表示的示例

AAABBBCCCDDDFFFEEErootrootroot二叉樹二叉鏈表三叉鏈表

有時，為了找到父結(jié)點，可以增加一個Parent域，Parent域指向該結(jié)點的父結(jié)點。該結(jié)點結(jié)構(gòu)如下：RChildParentDataLChild三叉鏈表typedefstructNode{DataTypedata;structNode*LChild;structNode*RChild;}BiTNode,*BiTree;二叉樹的二叉鏈表結(jié)點的結(jié)構(gòu)用C語言描述為：結(jié)論：若一個二叉樹含有n個結(jié)點，則它的二叉鏈表中必含有2n個指針域，其中必有n＋1個空的鏈域。證明結(jié)論：分支數(shù)目B=n-1，即非空的鏈域有n-1個，故空鏈域有2n-(n-1)=n+1個。6.3二叉樹的遍歷與線索化二叉樹的遍歷：指按一定規(guī)律對二叉樹中的每個結(jié)點進行訪問且僅訪問一次。二叉樹的基本結(jié)構(gòu)由根結(jié)點、左子樹和右子樹組成RChildDataLChildDataLChildLChildRChild如圖示用L、D、R分別表示遍歷左子樹、訪問根結(jié)點、遍歷右子樹，那么對二叉樹的遍歷順序就可以有：訪問根，遍歷左子樹，遍歷右子樹(記做DLR)。訪問根，遍歷右子樹，遍歷左子樹(記做DRL)。遍歷左子樹，訪問根，遍歷右子樹(記做LDR)。遍歷左子樹，遍歷右子樹，訪問根(記做LRD)。遍歷右子樹，訪問根，遍歷左子樹(記做RDL)。遍歷右子樹，遍歷左子樹，訪問根(記做RLD)。在以上六種遍歷方式中，如果我們規(guī)定按先左后右的順序，那么就只剩有DLR、LDR和LRD三種。根據(jù)對根的訪問先后順序不同，分別稱DLR為先序遍歷(先根遍歷)；LDR為中序遍歷（對稱遍歷）；LRD為后序遍歷。注意：先序、中序、后序遍歷是遞歸定義的，即在其子樹中亦按上述規(guī)律進行遍歷。三種遍歷方法的遞歸定義：先序遍歷（DLR）操作過程：若二叉樹為空，則空操作，否則依次執(zhí)行如下操作：（1）訪問根結(jié)點；（2）按先序遍歷左子樹；（3）按先序遍歷右子樹。若二叉樹為空，則空操作，否則依次執(zhí)行如下操作：（1）按中序遍歷左子樹；（2）訪問根結(jié)點；（3）按中序遍歷右子樹。中序遍歷（LDR）操作過程后序遍歷（LRD）操作過程：若二叉樹為空，則空操作，否則依次執(zhí)行如下操作：（1）按后序遍歷左子樹；（2）按后序遍歷右子樹；（3）訪問根結(jié)點。

對于如下圖的二叉樹，其先序、中序、后序遍歷的序列為：先序遍歷：A、B、D、F、G、C、E、H。中序遍歷：B、F、D、G、A、C、E、H。后序遍歷：F、G、D、B、H、E、C、A。ABCDFGEH以二叉鏈表作為存儲結(jié)構(gòu)，討論二叉樹的遍歷算法1)先序遍歷voidPreOrder(BiTreeroot)/*先序遍歷二叉樹,root為指向二叉樹(或某一子樹)根結(jié)點的指針*/{ if(root!=NULL) {Visit(root->data);/*訪問根結(jié)點*/ PreOrder(root->LChild);/*先序遍歷左子樹*/ PreOrder(root->RChild);/*先序遍歷右子樹*/ }}2)中序遍歷voidInOrder(BiTreeroot)/*中序遍歷二叉樹,root為指向二叉樹(或某一子樹)根結(jié)點的指針*/{if(root!=NULL){InOrder(root->LChild);/*中序遍歷左子樹*/Visit(root->data);/*訪問根結(jié)點*/InOrder(root->RChild);/*中序遍歷右子樹*/}}3)后序遍歷voidPostOrder(BiTreeroot)/*后序遍歷二叉樹，root為指向二叉樹(或某一子樹)根結(jié)點的指針{ if(root!=NULL) { PostOrder(root->LChild);/*后序遍歷左子樹*/ PostOrder(root->RChild);/*后序遍歷右子樹*

Visit(root->data);/*訪問根結(jié)點*/ }}以中序遍歷為例來說明中序遍歷二叉樹的遞歸過程ABDCEBDФФФ第一次經(jīng)過第二次經(jīng)過第三次經(jīng)過6.3.2基于棧的遞歸消除1)中序遍歷二叉樹的非遞歸算法

首先應(yīng)用遞歸進棧與遞歸退棧的原則,直接先給出中序遍歷二叉樹的非遞歸算法基本實現(xiàn)思路。

中序遍歷二叉樹的非遞歸算法初步如下：在大量復(fù)雜的情況下，遞歸的問題無法直接轉(zhuǎn)換成循環(huán)，需要采用工作棧消除遞歸。工作棧提供一種控制結(jié)構(gòu)，當(dāng)遞歸算法進層時需要將信息保留；當(dāng)遞歸算法出層時需要從棧區(qū)退出信息。中序遍歷二叉樹的非遞歸算法（直接實現(xiàn)棧操作）/*s[m]表示棧，top表示棧頂指針*/Voidinorder(BiTreebt)/*中序遍歷二叉樹，bt為二叉樹的根結(jié)點*/{top=0;p=bt;do{while(p!=NULL){if(top>m)return(‘overflow’);top=top+1;s[top]=p;p=p->Lchild;

}/*遍歷左子樹*/if(top!=0)

{p=s[top];top=top-1;Visit(p->data);/*訪問根結(jié)點*/p=p->Rchild;}/*遍歷右子樹*/}}while(p!=NULL||top!=0)}中序遍歷二叉樹的非遞歸算法（調(diào)用棧操作的函數(shù)）voidInOrder（BiTreeroot）/*中序遍歷二叉樹的非遞歸算法*/{InitStack(&S);p=root;while(p!=NULL||!IsEmpty(S)){if(p!=NULL)/*根指針進棧，遍歷左子樹*/{Push(&S,p);p=p->LChild;}else{/*根指針退棧，訪問根結(jié)點，遍歷右子樹*/Pop(&S,&p);Visit(p->data);p=p->RChild;}}}2)后序遍歷的二叉樹的非遞歸算法voidPostOrder（BiTreeroot）{BiTNode*p,*q；BiTNode**S；

inttop=0;q=NULL;p=root;S=（BiTNode**）malloc（sizeof（BiTNode*）*NUM）;/*NUM為預(yù)定義的常數(shù)*/while(p!=NULL||top!=0){while(p!=NULL) {top++;s[top]=p;p=p->LChild;}/*左子樹遍歷*/ if(top>0) {p=s[top]; if((p->RChild==NULL)||(p->RChild==q))/*無右孩子，或右孩子已遍歷過*/ {visit(p->data);/*訪問根結(jié)點*/ q=p;/*保存到q，為下一次已處理結(jié)點前驅(qū)*/ top--;p=NULL;//p=NULL防止再次遍歷左子樹

} else //右孩子不為空且每訪問過

p=p->RChild;}}free(s);}6.3.3遍歷算法應(yīng)用二叉樹的遍歷運算是一個重要的基礎(chǔ)。在實際應(yīng)用中，一是重點理解訪問根結(jié)點操作的含義，二是注意對具體的實現(xiàn)問題是否需要考慮遍歷的次序問題。1.輸出二叉樹中的結(jié)點遍歷算法將走遍二叉樹中的每一個結(jié)點，故輸出二叉樹中結(jié)點并無次序要求，因此可用任一種算法來完成。先序遍歷輸出二叉樹中的結(jié)點voidPreOrder(BiTreeroot)/*先序遍歷輸出二叉樹結(jié)點,root為指向二叉樹根結(jié)點的指針*/{ if(root!=NULL) { printf(root->data);/*輸出根結(jié)點*/ PreOrder(root->LChild);/*先序遍歷左子樹*/ PreOrder(root->RChild);/*先序遍歷右子樹*/ }}問題思考：若要求統(tǒng)計二叉樹中結(jié)點個數(shù)應(yīng)如何去實現(xiàn)？2.輸出二叉樹中的葉子結(jié)點條件：判斷結(jié)點既沒有左孩子，又沒有右孩子時，則輸出該結(jié)點。voidPreOrder(BiTreeroot)/*先序遍歷輸出二叉樹中葉結(jié)點,root為指向二叉樹根結(jié)點的指針*/{if(root!=NULL){if(root->LChild==NULL&&root->RChild==NULL)printf(root->data);/*輸出葉結(jié)點*/PreOrder(root->LChild);/*先序遍歷左子樹*/PreOrder(root->RChild);/*先序遍歷右子樹*/}}3.統(tǒng)計葉子結(jié)點數(shù)目/*LeafCount保存葉子結(jié)點數(shù)目的全局變量,調(diào)用之前初始化值為0*/voidleaf(BiTreeroot){

if(root!=NULL){if(root->LChild==NULL&&root->RChild==NULL)LeafCount++;

leaf(root->LChild);leaf(root->RChild);}}

方法一：intleaf(BiTreeroot){intLeafCount;if(root==NULL) LeafCount=0;elseif((root->LChild==NULL)&&(root->RChild==NULL)) LeafCount=1;else LeafCount=leaf(root->LChild)+leaf(root->RChild); /*葉子數(shù)為左右子樹的葉子數(shù)目之和*/returnLeafCount;}方法二/*采用遞歸算法，如果是空樹，返回0；如果只有一個結(jié)點，返回1；否則為左右子樹的葉子結(jié)點數(shù)之和*/4.建立二叉鏈表方式存儲的二叉樹給定一棵二叉樹，可以得到它的遍歷序列；反過來，給定一個遍歷序列，也可以創(chuàng)建相應(yīng)的二叉鏈表。在這里所說的遍歷序列是一種“擴展的遍歷序列”，通常用特定的元素表示空子樹。例如：ABCDFGEH右圖中的二叉樹的“擴展的先序遍歷序列”為：AB.DF..G..C.E.H..其中用小圓點表示空子樹利用“擴展先序遍歷序列”創(chuàng)建二叉鏈表的算法為：voidCreateBiTree(BiTree*bt)//注意此處的指向結(jié)點的指針的指針{charch;//傳遞指針的地址，否則結(jié)點之間無

ch=getchar();//法進行連接。

if(ch=='.')*bt=NULL;else{*bt=(BiTree)malloc(sizeof(BiTNode));(*bt)->data=ch;CreateBiTree(&((*bt)->LChild));CreateBiTree(&((*bt)->RChild));}}5.求二叉樹的高度設(shè)函數(shù)表示二叉樹bt的高度，則遞歸定義如下:

若bt為空，則高度為0

若bt非空，其高度應(yīng)為其左右子樹高度的最大值加1

左子樹右子樹bthlhrHigh=max(hl+hr)+1后序遍歷求二叉樹的高度遞歸算法：intPostTreeDepth(BiTreebt)/*后序遍歷求二叉樹的高度遞歸算法*/{inthl,hr,max;if(bt!=NULL){hl=PostTreeDepth(bt->LChild);/*求左子樹的深度*/hr=PostTreeDepth(bt->RChild);/*求右子樹的深度*/max=hl>hr?hl:hr;/*得到左、右子樹深度較大者*/return(max+1);/*返回樹的深度*/}elsereturn(0);/*如果是空樹，則返回0*/}6.3.4線索二叉樹1.基本概念二叉樹的遍歷運算是將二叉樹中結(jié)點按一定規(guī)律線性化的過程。當(dāng)以二叉鏈表作為存儲結(jié)構(gòu)時，只能找到結(jié)點的左、右孩子信息，而不能直接得到結(jié)點在遍歷序列中的前驅(qū)和后繼信息。要得到這些信息，第一種方法是將二叉樹遍歷一遍，在遍歷過程中便可得到結(jié)點的前驅(qū)和后繼，但這種動態(tài)訪問浪費時間；第二種方法是充分利用二叉鏈表中的空鏈域，將遍歷過程中結(jié)點的前驅(qū)、后繼信息保存下來。

在有n個結(jié)點的二叉鏈表中共有2n個鏈域，但只有n-1個有用非空鏈域，其余n+1個鏈域是空的。我們可以利用剩下的n+1個空鏈域來存放遍歷過程中結(jié)點的前驅(qū)和后繼信息。現(xiàn)作如下規(guī)定：若結(jié)點有左子樹，則其LChild域指向其左孩子，否則LChild域指向其前驅(qū)結(jié)點；若結(jié)點有右子樹，則其RChild域指向其右孩子，否則RChild域指向其后繼結(jié)點。LChildLtagDataRtagRChild為了區(qū)分孩子結(jié)點和前驅(qū)、后繼結(jié)點，為結(jié)點結(jié)構(gòu)增設(shè)兩個標(biāo)志域，如下圖所示：其中：Ltag=0LChild域指示結(jié)點的左孩子1LChild域指示結(jié)點的遍歷前驅(qū)Rtag=0RChild域指示結(jié)點的右孩子1RChild域指示結(jié)點的遍歷后繼線索：在這種存儲結(jié)構(gòu)中，指向前驅(qū)和后繼結(jié)點的指針叫做線索。線索鏈表：以這種結(jié)構(gòu)組成的二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，叫做線索鏈表。線索化：對二叉樹以某種次序進行遍歷并且加上線索的過程叫做線索化。線索二叉樹：線索化了的二叉樹稱為線索二叉樹。2.二叉樹的線索化線索化實質(zhì)上是將二叉鏈表中的空指針域填上相應(yīng)結(jié)點的遍歷前驅(qū)或后繼結(jié)點的地址，而前驅(qū)和后繼的地址只能在動態(tài)的遍歷過程中才能得到。因此線索化的過程是在遍歷過程中修改空指針域的過程。對二叉樹按照不同的遍歷次序進行線索化，可以得到不同的線索二叉樹（先序線索二叉樹、中序線索二叉樹和后序線索二叉樹）。中序線索化算法：voidInthread(BiTreeroot)/*對root所指的二叉樹進行中序線索化，其中pre始終指向剛訪問過的結(jié)點，其初值為NULL*/{if(root!=NULL){Inthread(root->LChild);/*線索化左子樹*/if(root->LChild==NULL){root->Ltag=1;root->LChild=pre;/*置前驅(qū)線索*/}if(pre!=NULL&&pre->RChild==NULL)/*置后繼線索*/pre->RChild=root;pre=root；

Inthread(root->RChild);/*線索化右子樹*/ }} 下面是對同一棵二叉樹的遍歷方法不同得到的不同線索樹。NULL(a)二叉樹ABCDGEFH(b)先序線索二叉樹ABCDGEFHNULLNULL（c）中序線索二叉樹ABCDGEFH（d）后序線索二叉樹NULLABCDGEFH3.在線索二叉樹中找前驅(qū)、后繼結(jié)點1）找結(jié)點的中序前驅(qū)結(jié)點根據(jù)線索二叉樹的基本概念和存儲結(jié)構(gòu)可知，對于結(jié)點p，當(dāng)p->Ltag=1時，p->LChild指向p的前驅(qū)。當(dāng)p->Ltag=0時，p->LChild指向p的左孩子。由中序遍歷的規(guī)律可知，作為根p的前驅(qū)結(jié)點，它是中序遍歷p的左子樹時訪問的最后一個結(jié)點，即左子樹的“最右下端”結(jié)點。其查找算法如下：在中序線索樹中找結(jié)點前驅(qū)算法：voidInPre(BiTNode*p,BiTNode*pre)/*在中序線索二叉樹中查找p的中序前驅(qū),并用pre指針返回結(jié)果*/{if(p->Ltag==1)pre=p->LChild;/*直接利用線索*/else{/*在p的左子樹中查找“最右下端”結(jié)點*/for(q=p->LChild;q->Rtag==0;q=q->RChild);pre=q;}}

2）在中序線索樹中找結(jié)點后繼對于結(jié)點p，若要找其后繼結(jié)點，當(dāng)p->Rtag=1時，p->RChild即為p的后繼結(jié)點；當(dāng)p->Rtag=0時，說明p有右子樹，此時p的中序后繼結(jié)點即為其右子樹的“最左下端”的結(jié)點。其查找算法如下：voidInSucc(BiTNode*p,BiTNode*succ)/*在中序線索二叉樹中查找p的后繼結(jié)點，并用succ指針返回結(jié)果*/{if(p->Rtag==1)succ=p->RChild;/*直接利用線索*/else{/*在p的右子樹中查找“最左下端”結(jié)點*/for(q=p->RChild;q->Ltag==0;q=q->LChild);succ=q;}}6.4樹、森林和二叉樹的關(guān)系討論的重點：樹的存儲結(jié)構(gòu)樹、森林與二叉樹的轉(zhuǎn)換關(guān)系6.4.1樹的存儲結(jié)構(gòu)樹的主要存儲方法有：1.雙親表示法2.孩子表示法3.孩子兄弟表示法1.雙親表示法：用一組連續(xù)的空間來存儲樹中的結(jié)點，在保存每個結(jié)點的同時附設(shè)一個指示器來指示其雙親結(jié)點在表中的位置，其結(jié)點的結(jié)構(gòu)如下：

數(shù)據(jù)雙親DataParent12456371615140302-11ParentData543210結(jié)點序號樹的雙親表示法如下圖：雙親表示法的優(yōu)點：利用了樹中每個結(jié)點（根結(jié)點除外）只有一個雙親結(jié)點的性質(zhì)，使得查找某個結(jié)點的雙親結(jié)點非常容易。

雙親表示法的缺點：在求某個結(jié)點的孩子時，需要遍歷整個向量。

雙親表示法的形式說明如下：#defineMAX100typedefstructTNode{ DataTypedata; intparent;}TNode;

一棵樹可以定義為：typedefstruct{TNodetree[MAX];intnodenum;/*結(jié)點數(shù)*/}ParentTree;2.孩子表示法：通常是把每個結(jié)點的孩子結(jié)點排列起來，構(gòu)成一個單鏈表，稱為孩子鏈表。n個結(jié)點共有n個孩子鏈表（葉結(jié)點的孩子鏈表為空表），而n個結(jié)點的數(shù)據(jù)和n個孩子鏈表的頭指針又組成一個順序表。

樹的孩子鏈表表示法見p137的圖6.14孩子表示法的形式說明如下：typedefstructChildNode/*孩子鏈表結(jié)點的定義*/{ intChild;/*該孩子結(jié)點在線性表中的位置*/ structChildNode*next;/*指向下一個孩子結(jié)點的指針*/}ChildNode;

typedefstruct/*順序表結(jié)點的結(jié)構(gòu)定義*/{ DataTypedata;/*結(jié)點的信息*/ ChildNode*FirstChild;/*指向孩子鏈表的頭指針*/}DataNode;返回主目錄

typedefstruct/*樹的定義*/{DataNodenodes[MAX];/*順序表*/introot,num;/*該樹的根結(jié)點在線性表中的位置和該樹的結(jié)點個數(shù)*/}ChildTree;

返回主目錄3.孩子兄弟表示法（二叉鏈表表示法）：鏈表中每個結(jié)點設(shè)有兩個鏈域，分別指向該結(jié)點的第一個孩子結(jié)點和下一個兄弟（右兄弟）結(jié)點。

樹的孩子兄弟表示法見p137的圖6.15孩子兄弟表示法的類型定義如下：typedefstructCSNode{DataTypedata;/*結(jié)點信息*/StructCSNode*FirstChild,*Nextsibling;/*第一個孩子,下一個兄弟*/}CSNode,*CSTree;

優(yōu)點：便于實現(xiàn)樹的各種操作。6.4.2樹、森林與二叉樹的相互轉(zhuǎn)換1.樹轉(zhuǎn)換為二叉樹

我們約定樹中每一個結(jié)點的孩子結(jié)點按從左到右的次序順序編號，也就是說，把樹作為有序樹看待。

例如：右圖的樹ABECDFGH將一棵樹轉(zhuǎn)換為二叉樹的方法：⑴樹中所有相鄰兄弟之間加一條連線。⑵對樹中的每個結(jié)點，只保留其與第一個孩子結(jié)點之間的連線，刪去其與其它孩子結(jié)點之間的連線。⑶

以樹的根結(jié)點為軸心，將整棵樹順時針旋轉(zhuǎn)一定的角度，使之結(jié)構(gòu)層次分明。

樹轉(zhuǎn)換為二叉樹的轉(zhuǎn)換過程示意見p137圖6.162.森林轉(zhuǎn)換為二叉樹森林轉(zhuǎn)換為二叉樹的方法為：（1）將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹。（2）第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點作為前一棵二叉樹根結(jié)點的右孩子，當(dāng)所有二叉樹連在一起后，所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。

森林轉(zhuǎn)換為二叉樹的過程見p138的圖6.17用遞歸的方法描述森林轉(zhuǎn)換為二叉樹的過程為：

將森林F看作樹的有序集F={T1，T2，…,TN}，它對應(yīng)的二叉樹為B（F）：

（1）若N＝0，則B（F）為空。

（2）若N>0，二叉樹B（F）的根為森林中第一棵樹T1的根；

B（F）的左子樹為B（{T11，…，T1m}），其中{T11，…，T1m}是T1的子樹；B（F）的右子樹是B（{T2，…，TN}）。

3.二叉樹還原為樹或森林一棵二叉樹還原為樹或森林，具體方法為：（1）若某結(jié)點是其雙親的左孩子，則把該結(jié)點的右孩子、右孩子的右孩子、……都與該結(jié)點的雙親結(jié)點用線連起來。

（2）刪掉原二叉樹中所有雙親結(jié)點與右孩子結(jié)點的連線。

（3）整理由（1）、（2）兩步所得到的樹或森林，使之結(jié)構(gòu)層次分明。

用遞歸的方法描述其轉(zhuǎn)換過程為：

若B是一棵二叉樹，T是B的根結(jié)點，L是B的左子樹，R為B的右子樹，且B對應(yīng)的森林F（B）中含有的n棵樹為T1,T2,…,Tn，則有：

（1）B為空，則F（B）為空的森林（n＝0）。

（2）B非空，則F（B）中第一棵樹T1的根為二叉樹B的根T；T1中根結(jié)點的子樹森林由B的左子樹L轉(zhuǎn)換而成，即F（L）={T11,…,T1m}；B的右子樹R轉(zhuǎn)換為F（B）中其余樹組成的森林，即F(R)＝{T2,T3,…,Tn}。

6.4.3樹與森林的遍歷1.樹的遍歷樹的遍歷方法主要有以下兩種：1）先根遍歷若樹非空，則遍歷方法為：（1）訪問根結(jié)點。（2）從左到右，依次先根遍歷根結(jié)點的每一棵子樹。

ABECDFGH如圖中樹的先根遍歷序列為：ABECFHGD。2）后根遍歷若樹非空，則遍歷方法為：（1）從左到右，依次后根遍歷根結(jié)點的每一棵子樹。（2）訪問根結(jié)點。ABECDFGH如圖中樹的后根遍歷序列為：EBHFGCDA。2.森林的遍歷森林的遍歷方法主要有以下三種：1）先序遍歷若森林非空，則遍歷方法為：（1）訪問森林中第一棵樹的根結(jié)點。（2）先序遍歷第一棵樹的根結(jié)點的子樹森林。（3）先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。2）中序遍歷若森林非空，則遍歷方法為：（1）中序遍歷森林中第一棵樹的根結(jié)點的子樹森林。

（2）訪問第一棵樹的根結(jié)點。

（3）中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。

3）后序遍歷若森林非空，則遍歷方法為：（1）后序遍歷森林中第一棵樹的根結(jié)點的子樹森林。

（2）后序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。

（3）訪問第一棵樹的根結(jié)點。

p139有對圖6.17有實例6.5哈夫曼樹及其應(yīng)用6.5.1哈夫曼樹基本概念：路徑：指從一個結(jié)點到另一個結(jié)點之間的分支序列。路徑長度：指從一個結(jié)點到另一個結(jié)點所經(jīng)過的分支數(shù)目。結(jié)點的權(quán)：給樹的每個結(jié)點賦予一個具有某種實際意義的實數(shù)，我們稱該實數(shù)為這個結(jié)點的權(quán)。帶權(quán)路徑長度：在樹形結(jié)構(gòu)中，我們把從樹根到某一結(jié)點的路徑長度與該結(jié)點的權(quán)的乘積，叫做該結(jié)點的帶權(quán)路徑長度。樹的帶權(quán)路徑長度：為樹中所有葉子結(jié)點的帶權(quán)路徑長度之和，通常記為：WPL=wi×lii=1n其中n為葉子結(jié)點的個數(shù)，wi為第i個葉子結(jié)點的權(quán)值，li為第i個葉子結(jié)點的路徑長度。例如下圖所示的具有不同帶權(quán)路徑長度的二叉樹WPL(a)=7×2＋5×2＋2×2＋4×2＝36WPL(b)=4×2＋7×3＋5×3＋2×1＝46WPL(c)=7×1＋5×2＋2×3＋4×3＝35CDBA圖例見p144的圖6.22所示問題1：什么樣的二叉樹的路徑長度WPL最?。恳豢脴涞穆窂介L度為0結(jié)點至多只有1個（根）；路徑長度為1結(jié)點至多只有2個（兩個孩子）；路徑長度為2結(jié)點至多只有4個；以此類推：路徑長度為K結(jié)點至多只有2k個，所以n個結(jié)點二叉樹其路徑長度至少等于如下序列的前n項之和。路徑長度

0，1，1，2，2，2，2，3，3，3，3，3，3，3，3，4，4，...結(jié)點數(shù)nn=1n=2n=3n=4n=5n=6n=7n=8...n=15由此可知，結(jié)點n對應(yīng)的路徑長度為

log2n，所以前n項之和為:nk=1log2k完全二叉樹的路徑長度為：20×0+21×

1+22×

2+…+2h×h=hk=1log2kh為樹的深度，其路徑長度可達到最小，所以完全二叉樹具有最小路徑長度的性質(zhì)，但不具有唯一性。例如：下列不同形狀的二叉樹具有最小的路徑長度ABCDE