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

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

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

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

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

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

n=n0+n1+n2設(shè)二叉樹中分支數(shù)目為B，因?yàn)槌Y(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均對(duì)應(yīng)一個(gè)進(jìn)入它的分支，所以有：n=B+1。又因?yàn)槎鏄渲械姆种Ф际怯啥葹?和度為2的結(jié)點(diǎn)發(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個(gè)結(jié)點(diǎn)的二叉樹。在滿二叉樹中，每層結(jié)點(diǎn)都是滿的，即每層結(jié)點(diǎn)都具有最大結(jié)點(diǎn)數(shù)。123456789101112131415滿二叉樹定義2：完全二叉樹：1234567891011121314關(guān)系：滿二叉樹必為完全二叉樹，而完全二叉樹不一定是滿二叉樹。若設(shè)二叉樹的高度為h，則共有h層。除第h層外，其它各層(0h-1)的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第h層從右向左連續(xù)缺若干結(jié)點(diǎn)，這就是完全二叉樹。2154367216543非完全二叉樹性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為

㏒2n

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

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

顯然有：

2k-1-1<n2k-1

2k-1

n

<2k

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

log2n

<

klog2n+1

因?yàn)閗是整數(shù)，k=

㏒2n

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

i/2

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

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

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

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

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

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

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

對(duì)于如下圖的二叉樹，其先序、中序、后序遍歷的序列為：先序遍歷：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以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，討論二叉樹的遍歷算法1)先序遍歷voidPreOrder(BiTreeroot)/*先序遍歷二叉樹,root為指向二叉樹(或某一子樹)根結(jié)點(diǎn)的指針*/{ if(root!=NULL) {Visit(root->data);/*訪問根結(jié)點(diǎn)*/ PreOrder(root->LChild);/*先序遍歷左子樹*/ PreOrder(root->RChild);/*先序遍歷右子樹*/ }}2)中序遍歷voidInOrder(BiTreeroot)/*中序遍歷二叉樹,root為指向二叉樹(或某一子樹)根結(jié)點(diǎn)的指針*/{if(root!=NULL){InOrder(root->LChild);/*中序遍歷左子樹*/Visit(root->data);/*訪問根結(jié)點(diǎn)*/InOrder(root->RChild);/*中序遍歷右子樹*/}}3)后序遍歷voidPostOrder(BiTreeroot)/*后序遍歷二叉樹，root為指向二叉樹(或某一子樹)根結(jié)點(diǎn)的指針{ if(root!=NULL) { PostOrder(root->LChild);/*后序遍歷左子樹*/ PostOrder(root->RChild);/*后序遍歷右子樹*

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

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

中序遍歷二叉樹的非遞歸算法初步如下：在大量復(fù)雜的情況下，遞歸的問題無(wú)法直接轉(zhuǎn)換成循環(huán)，需要采用工作棧消除遞歸。工作棧提供一種控制結(jié)構(gòu)，當(dāng)遞歸算法進(jìn)層時(shí)需要將信息保留；當(dāng)遞歸算法出層時(shí)需要從棧區(qū)退出信息。中序遍歷二叉樹的非遞歸算法（直接實(shí)現(xiàn)棧操作）/*s[m]表示棧，top表示棧頂指針*/Voidinorder(BiTreebt)/*中序遍歷二叉樹，bt為二叉樹的根結(jié)點(diǎn)*/{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é)點(diǎn)*/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)/*根指針進(jìn)棧，遍歷左子樹*/{Push(&S,p);p=p->LChild;}else{/*根指針退棧，訪問根結(jié)點(diǎn)，遍歷右子樹*/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))/*無(wú)右孩子，或右孩子已遍歷過*/ {visit(p->data);/*訪問根結(jié)點(diǎn)*/ q=p;/*保存到q，為下一次已處理結(jié)點(diǎn)前驅(qū)*/ top--;p=NULL;//p=NULL防止再次遍歷左子樹

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

p=p->RChild;}}free(s);}6.3.3遍歷算法應(yīng)用二叉樹的遍歷運(yùn)算是一個(gè)重要的基礎(chǔ)。在實(shí)際應(yīng)用中，一是重點(diǎn)理解訪問根結(jié)點(diǎn)操作的含義，二是注意對(duì)具體的實(shí)現(xiàn)問題是否需要考慮遍歷的次序問題。1.輸出二叉樹中的結(jié)點(diǎn)遍歷算法將走遍二叉樹中的每一個(gè)結(jié)點(diǎn)，故輸出二叉樹中結(jié)點(diǎn)并無(wú)次序要求，因此可用任一種算法來完成。先序遍歷輸出二叉樹中的結(jié)點(diǎn)voidPreOrder(BiTreeroot)/*先序遍歷輸出二叉樹結(jié)點(diǎn),root為指向二叉樹根結(jié)點(diǎn)的指針*/{ if(root!=NULL) { printf(root->data);/*輸出根結(jié)點(diǎn)*/ PreOrder(root->LChild);/*先序遍歷左子樹*/ PreOrder(root->RChild);/*先序遍歷右子樹*/ }}問題思考：若要求統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)個(gè)數(shù)應(yīng)如何去實(shí)現(xiàn)？2.輸出二叉樹中的葉子結(jié)點(diǎn)條件：判斷結(jié)點(diǎn)既沒有左孩子，又沒有右孩子時(shí)，則輸出該結(jié)點(diǎn)。voidPreOrder(BiTreeroot)/*先序遍歷輸出二叉樹中葉結(jié)點(diǎn),root為指向二叉樹根結(jié)點(diǎn)的指針*/{if(root!=NULL){if(root->LChild==NULL&&root->RChild==NULL)printf(root->data);/*輸出葉結(jié)點(diǎn)*/PreOrder(root->LChild);/*先序遍歷左子樹*/PreOrder(root->RChild);/*先序遍歷右子樹*/}}3.統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)目/*LeafCount保存葉子結(jié)點(diǎn)數(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；如果只有一個(gè)結(jié)點(diǎn)，返回1；否則為左右子樹的葉子結(jié)點(diǎn)數(shù)之和*/4.建立二叉鏈表方式存儲(chǔ)的二叉樹給定一棵二叉樹，可以得到它的遍歷序列；反過來，給定一個(gè)遍歷序列，也可以創(chuàng)建相應(yīng)的二叉鏈表。在這里所說的遍歷序列是一種“擴(kuò)展的遍歷序列”，通常用特定的元素表示空子樹。例如：ABCDFGEH右圖中的二叉樹的“擴(kuò)展的先序遍歷序列”為：AB.DF..G..C.E.H..其中用小圓點(diǎn)表示空子樹利用“擴(kuò)展先序遍歷序列”創(chuàng)建二叉鏈表的算法為：voidCreateBiTree(BiTree*bt)//注意此處的指向結(jié)點(diǎn)的指針的指針{charch;//傳遞指針的地址，否則結(jié)點(diǎn)之間無(wú)

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

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.基本概念二叉樹的遍歷運(yùn)算是將二叉樹中結(jié)點(diǎn)按一定規(guī)律線性化的過程。當(dāng)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí)，只能找到結(jié)點(diǎn)的左、右孩子信息，而不能直接得到結(jié)點(diǎn)在遍歷序列中的前驅(qū)和后繼信息。要得到這些信息，第一種方法是將二叉樹遍歷一遍，在遍歷過程中便可得到結(jié)點(diǎn)的前驅(qū)和后繼，但這種動(dòng)態(tài)訪問浪費(fèi)時(shí)間；第二種方法是充分利用二叉鏈表中的空鏈域，將遍歷過程中結(jié)點(diǎn)的前驅(qū)、后繼信息保存下來。

在有n個(gè)結(jié)點(diǎn)的二叉鏈表中共有2n個(gè)鏈域，但只有n-1個(gè)有用非空鏈域，其余n+1個(gè)鏈域是空的。我們可以利用剩下的n+1個(gè)空鏈域來存放遍歷過程中結(jié)點(diǎn)的前驅(qū)和后繼信息。現(xiàn)作如下規(guī)定：若結(jié)點(diǎn)有左子樹，則其LChild域指向其左孩子，否則LChild域指向其前驅(qū)結(jié)點(diǎn)；若結(jié)點(diǎn)有右子樹，則其RChild域指向其右孩子，否則RChild域指向其后繼結(jié)點(diǎn)。LChildLtagDataRtagRChild為了區(qū)分孩子結(jié)點(diǎn)和前驅(qū)、后繼結(jié)點(diǎn)，為結(jié)點(diǎn)結(jié)構(gòu)增設(shè)兩個(gè)標(biāo)志域，如下圖所示：其中：Ltag=0LChild域指示結(jié)點(diǎn)的左孩子1LChild域指示結(jié)點(diǎn)的遍歷前驅(qū)Rtag=0RChild域指示結(jié)點(diǎn)的右孩子1RChild域指示結(jié)點(diǎn)的遍歷后繼線索：在這種存儲(chǔ)結(jié)構(gòu)中，指向前驅(qū)和后繼結(jié)點(diǎn)的指針叫做線索。線索鏈表：以這種結(jié)構(gòu)組成的二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，叫做線索鏈表。線索化：對(duì)二叉樹以某種次序進(jìn)行遍歷并且加上線索的過程叫做線索化。線索二叉樹：線索化了的二叉樹稱為線索二叉樹。2.二叉樹的線索化線索化實(shí)質(zhì)上是將二叉鏈表中的空指針域填上相應(yīng)結(jié)點(diǎn)的遍歷前驅(qū)或后繼結(jié)點(diǎn)的地址，而前驅(qū)和后繼的地址只能在動(dòng)態(tài)的遍歷過程中才能得到。因此線索化的過程是在遍歷過程中修改空指針域的過程。對(duì)二叉樹按照不同的遍歷次序進(jìn)行線索化，可以得到不同的線索二叉樹（先序線索二叉樹、中序線索二叉樹和后序線索二叉樹）。中序線索化算法：voidInthread(BiTreeroot)/*對(duì)root所指的二叉樹進(jìn)行中序線索化，其中pre始終指向剛訪問過的結(jié)點(diǎn)，其初值為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);/*線索化右子樹*/ }} 下面是對(duì)同一棵二叉樹的遍歷方法不同得到的不同線索樹。NULL(a)二叉樹ABCDGEFH(b)先序線索二叉樹ABCDGEFHNULLNULL（c）中序線索二叉樹ABCDGEFH（d）后序線索二叉樹NULLABCDGEFH3.在線索二叉樹中找前驅(qū)、后繼結(jié)點(diǎn)1）找結(jié)點(diǎn)的中序前驅(qū)結(jié)點(diǎn)根據(jù)線索二叉樹的基本概念和存儲(chǔ)結(jié)構(gòu)可知，對(duì)于結(jié)點(diǎn)p，當(dāng)p->Ltag=1時(shí)，p->LChild指向p的前驅(qū)。當(dāng)p->Ltag=0時(shí)，p->LChild指向p的左孩子。由中序遍歷的規(guī)律可知，作為根p的前驅(qū)結(jié)點(diǎn)，它是中序遍歷p的左子樹時(shí)訪問的最后一個(gè)結(jié)點(diǎn)，即左子樹的“最右下端”結(jié)點(diǎn)。其查找算法如下：在中序線索樹中找結(jié)點(diǎn)前驅(qū)算法：voidInPre(BiTNode*p,BiTNode*pre)/*在中序線索二叉樹中查找p的中序前驅(qū),并用pre指針返回結(jié)果*/{if(p->Ltag==1)pre=p->LChild;/*直接利用線索*/else{/*在p的左子樹中查找“最右下端”結(jié)點(diǎn)*/for(q=p->LChild;q->Rtag==0;q=q->RChild);pre=q;}}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

將森林F看作樹的有序集F={T1，T2，…,TN}，它對(duì)應(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é)點(diǎn)是其雙親的左孩子，則把該結(jié)點(diǎn)的右孩子、右孩子的右孩子、……都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線連起來。

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

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

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

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

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

（2）B非空，則F（B）中第一棵樹T1的根為二叉樹B的根T；T1中根結(jié)點(diǎn)的子樹森林由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é)點(diǎn)。（2）從左到右，依次先根遍歷根結(jié)點(diǎn)的每一棵子樹。

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

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

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

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

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

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

p139有對(duì)圖6.17有實(shí)例6.5哈夫曼樹及其應(yīng)用6.5.1哈夫曼樹基本概念：路徑：指從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支序列。路徑長(zhǎng)度：指從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)所經(jīng)過的分支數(shù)目。結(jié)點(diǎn)的權(quán)：給樹的每個(gè)結(jié)點(diǎn)賦予一個(gè)具有某種實(shí)際意義的實(shí)數(shù)，我們稱該實(shí)數(shù)為這個(gè)結(jié)點(diǎn)的權(quán)。帶權(quán)路徑長(zhǎng)度：在樹形結(jié)構(gòu)中，我們把從樹根到某一結(jié)點(diǎn)的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積，叫做該結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度。樹的帶權(quán)路徑長(zhǎng)度：為樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，通常記為：WPL=wi×lii=1n其中n為葉子結(jié)點(diǎn)的個(gè)數(shù)，wi為第i個(gè)葉子結(jié)點(diǎn)的權(quán)值，li為第i個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度。例如下圖所示的具有不同帶權(quán)路徑長(zhǎng)度的二叉樹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：什么樣的二叉樹的路徑長(zhǎng)度WPL最??？一棵樹的路徑長(zhǎng)度為0結(jié)點(diǎn)至多只有1個(gè)（根）；路徑長(zhǎng)度為1結(jié)點(diǎn)至多只有2個(gè)（兩個(gè)孩子）；路徑長(zhǎng)度為2結(jié)點(diǎn)至多只有4個(gè)；以此類推：路徑長(zhǎng)度為K結(jié)點(diǎn)至多只有2k個(gè)，所以n個(gè)結(jié)點(diǎn)二叉樹其路徑長(zhǎng)度至少等于如下序列的前n項(xiàng)之和。路徑長(zhǎng)度

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

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

1+22×

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