第6章樹與二叉樹6.1樹的基本概念6.2二叉樹6.3二叉樹的遍歷6.4線索二叉樹6.5哈夫曼樹6.6樹和森林 6.1樹的基本概念

6.1.1樹的概念與定義

現(xiàn)實生活中存在許多用樹形結(jié)構(gòu)描述的實際問題。例如，某家族的關(guān)系如下：張抗生有三個孩子：張衛(wèi)紅、張衛(wèi)兵和張衛(wèi)華；而張衛(wèi)兵有兩個孩子張明和張麗；張衛(wèi)華有一個孩子張群。這個家族關(guān)系可以很自然的用圖6-1所示的樹形圖來描述，它很像一棵倒置的樹；其中“樹根”是張抗生，樹的“分支結(jié)點”是張衛(wèi)兵和張衛(wèi)華，而其他家族成員則構(gòu)成了該樹的“樹葉”，而樹枝(即圖中的線條)則描述了家族成員之間的相互關(guān)系。從圖6-1可以看出：以張抗生為根的樹是一個大家庭，并可以分為張衛(wèi)紅、張衛(wèi)兵、張衛(wèi)華為根的三個小家庭，且每個小家庭又形成了一個樹形結(jié)構(gòu)。因此可以得出樹的遞歸定義。

第6章樹與二叉樹圖6-1家族樹示意樹的定義：樹是n(n≥0)個結(jié)點的有限集合T，當(dāng)n=0(即T為空)時稱為空樹；當(dāng)n＞0時非空。樹T滿足以下兩個條件：

(1)有且僅有一個稱為根的結(jié)點。

(2)其余結(jié)點可分為m(m≥0)個互不相交的子集T1、T2、…、Tm，其中每個子集Ti本身又是一棵樹，并稱為根的子樹。

樹的遞歸定義凸顯了樹的固有特性。即一棵非空樹是由若干棵子樹構(gòu)成，而子樹又可由更小的若干棵子樹構(gòu)成。樹中結(jié)點呈現(xiàn)出明顯的層次關(guān)系，一個結(jié)點必須且只能跟上一層的一個結(jié)點(雙親結(jié)點)有直接關(guān)系，并且可以跟下一層的多個結(jié)點(孩子結(jié)點)有直接關(guān)系。所以，凡是具有等級(層次)關(guān)系的的數(shù)據(jù)均可以用樹來描述。圖6-2樹的各種表示法6.1.2樹的基本術(shù)語

下面介紹樹形結(jié)構(gòu)中常用的基本術(shù)語。

(1)樹的結(jié)點：包含一個數(shù)據(jù)元素及若干指向其子樹的分支。

(2)結(jié)點的度：結(jié)點擁有子樹的個數(shù)。如圖6-2(a)中A的度為3，C的度為2，B、D、E、F的度為0。

(3)樹的度：樹內(nèi)個各結(jié)點度的最大值。如圖6-2(a)所示的樹的度為3。

(4)葉子：度為0的結(jié)點，又稱終端結(jié)點。如圖6-2(a)所示樹中的B、D、E、F。

(5)分支結(jié)點：度不為0的結(jié)點，又稱非終端結(jié)點。如圖6-2(a)所示樹中C。

(6)孩子：結(jié)點的子樹的根稱為該結(jié)點的孩子。如圖6-2(a)所示樹中B、C、D是A的孩子，E、F是C的孩子。

(7)雙親：若結(jié)點j是結(jié)點i的孩子，則結(jié)點i就是結(jié)點j的雙親。如圖6-2(a)所示樹中A是B、C、D的雙親，C是E、F的雙親。

(8)兄弟：同一雙親的孩子之間互稱兄弟。如圖6-2(a)所示樹中的B、C、D互為兄弟，E、F互為兄弟。

(9)祖先：從根到該結(jié)點所經(jīng)分支上的所有結(jié)點均為該結(jié)點的祖先。如圖6-2(a)所示樹中A、C是E或F的祖先。

(10)子孫：以某結(jié)點為根的子樹中任意結(jié)點稱為該根的子孫。如圖6-2(a)所示樹中C的子孫為E和F。

(11)結(jié)點層次：從根開始，根為第一層，根的孩子為第二層；若某結(jié)點在L層，則其子樹的根則在第L+1層。

(12)樹的深度：樹中結(jié)點的最大層次。圖6-2(a)所示樹的深度為3。

(13)有序樹或無序樹：若樹中每個結(jié)點的各個子樹從左到右的次序不能互換，則稱該樹為有序樹，否則為無序樹。

(14)森林：森林是m(m≥0)棵互不相交的樹構(gòu)成的集合。刪除一棵樹的根，就得到由m棵子樹構(gòu)成的森林；反之，給m棵樹的森林加上一個根結(jié)點，并且這m棵樹都是該結(jié)點的子樹，那么就由森林變?yōu)橐豢脴洹? 6.2二叉樹

6.2.1二叉樹的定義

二叉樹的定義：二叉樹是n(n≥0)個結(jié)點的有限集合，它或者是空樹(n=0)，或者是由一個根結(jié)點及兩棵互不相交、分別稱做該根結(jié)點的左子樹和右子樹的二叉樹組成。

二叉樹的定義與樹的定義一樣，都是遞歸的。并且，二叉樹具有如下兩個特點：

(1)二叉樹不存在度大于2的結(jié)點。

(2)二叉樹每個結(jié)點至多有兩棵子樹且有左、右之分，次序不能顛倒。二叉樹與樹的主要區(qū)別是：二叉樹任何一個結(jié)點的子樹都要區(qū)分為左、右子樹，即使這個結(jié)點只有一棵子樹時也要明確指出它是左子樹還是右子樹，而樹則無此要求，即樹中某個結(jié)點只有一棵子樹時并不區(qū)分左右。根據(jù)二叉樹的定義，二叉樹具有如圖6-3所示的五種基本形態(tài)：(a)為空二叉樹(用符號φ表示)；(b)為只有一個根結(jié)點而無子樹的的二叉樹；(c)為只有左子樹而無右子樹的二叉樹；(d)為只有右子樹而無左子樹的二叉樹；(e)為左、右子樹均非空的二叉樹。圖6-3二叉樹的五種基本形態(tài)

1.滿二叉樹

我們稱具有下列性質(zhì)的的二叉樹為滿二叉樹：

(1)不存在度為1的結(jié)點，即所有分支結(jié)點都有左子樹和右子樹。

(2)所有葉子結(jié)點都在同一層上。

例如，圖6-4(a)即為滿二叉樹，而圖6-4(b)則不是滿二叉樹，因為其葉子結(jié)點不在同一層上。圖6-4滿二叉樹與非滿二叉樹示意圖

2.完全二叉樹

對一棵具有n個結(jié)點的二叉樹，將樹中的結(jié)點按從上至下，從左之右的順序進行編號，如果編號i(1≤i≤n)的結(jié)點與滿二叉樹中的編號為i的結(jié)點在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。

完全二叉樹的特點是：葉子結(jié)點只能出現(xiàn)在最下層和次最下層，且最下層的葉子結(jié)點都集中在樹的左部。如果完全二叉樹中某個結(jié)點的右孩子存在，則其左孩子必定存在。此外，在完全二叉樹中如果存在度為1的結(jié)點，則該結(jié)點的孩子一定是結(jié)點編號中的最后一個葉子結(jié)點。顯然，一棵滿二叉樹必定是一棵完全二叉樹，而一棵完全二叉樹卻未必是一棵滿二叉樹，(可能存在葉子結(jié)點不在同一層上或者有度為一的結(jié)點)。例如，在圖6-5(a)和圖6-5(b)均為完全二叉樹，而圖6-5(c)則不是一棵完全二叉樹。圖6-5完全二叉樹與非完全二叉樹示意圖6.2.2二叉樹的性質(zhì)

性質(zhì)1：非空二叉樹的第i層上最多有2i-1個結(jié)點(i≥1)。

證明：利用數(shù)學(xué)歸納法證明此性質(zhì)。

i=1時，只有一個根結(jié)點，顯然2i-1=20=1，命題成立。

假設(shè)對所有的j，1≤j≤i時命題成立，即第j層上至多有2j-1個結(jié)點。下面證明當(dāng)j?=?i時命題也成立。根據(jù)歸納假設(shè)，第i-1層上至多有2i-2個結(jié)點，由于二叉樹中每個結(jié)點至多有兩個孩子，因此第i層上最大結(jié)點數(shù)應(yīng)為第i-1層上最大結(jié)點數(shù)的2倍，即2×2i-2＝2i-1，即命題成立，證畢。

性質(zhì)2：深度為k的二叉樹至多有2k-1個結(jié)點(k≥1)。

證明：由性質(zhì)1可知，深度為k的二叉樹最多含有的結(jié)點數(shù)為每層最多結(jié)點數(shù)之和，即：

性質(zhì)3：在任意非空二叉樹中，如果葉子結(jié)點(度為0)數(shù)為n0，度為2的結(jié)點數(shù)為n2，則有n0=n2+1證明：設(shè)n1為二叉樹中度為1的結(jié)點數(shù)，則二叉樹中全部結(jié)點數(shù)(設(shè)為n)為：n=n0+n1+n2。從孩子結(jié)點考慮：除根結(jié)點之外，其余結(jié)點均屬于孩子結(jié)點，故二叉樹中的孩子結(jié)點總數(shù)為n-1，由于二叉樹中度為1的結(jié)點有1個孩子、度為2的結(jié)點有2個孩子，因此二叉樹中孩子結(jié)點總數(shù)又為n1+2n2，即有：n-1=n1+2n2。故可得方程如下：解之可得到：n0=n2+1。性質(zhì)5：對一個具有n個結(jié)點的完全二叉樹按層次自上而下且每層從左到右的順序?qū)λ薪Y(jié)點從1開始到n進行編號，則對任一序號為i的結(jié)點有：

(1)若i＞1，則i的雙親結(jié)點序號是；若i=1，則i為根結(jié)點序號。

(2)若2i≤n，則i的左孩子序號是2i，否則i無左孩子。

(3)若2i+1≤n，則i的右孩子序號是2i+1；否則i無右孩子。

證明略。例6.1

已知一棵完全二叉樹共有892個結(jié)點，試求：

(1)樹的高度；

(2)單支結(jié)點數(shù)；

(3)葉子結(jié)點數(shù)；

(4)最后一個分支(非葉子)結(jié)點的序號。

【解】(1)已知深度為k的二叉樹至多有2k-1個結(jié)點(k≥1)，由于：29-1＜892＜210-1，故樹的高度為10。

(2)對完全二叉樹來說，度為1的結(jié)點只能是0個或1個。由性質(zhì)3可知：n0=n2+1，即n0+n2一定是奇數(shù)，由題設(shè)完全二叉樹共有892個結(jié)點可知n1(即度為1的結(jié)點)=1。

(3)?892÷2=446，由n0=n2+1可知n0=446，n2=445。

(4)最后一個分支結(jié)點恰為去掉全部葉子結(jié)點后的那個結(jié)點，即892-446(葉子結(jié)點數(shù))=446，故最后一個分支結(jié)點的序號為446。6.2.3二叉樹的存儲結(jié)構(gòu)

1.順序存儲結(jié)構(gòu)

二叉樹的順序存儲是用一組地址連續(xù)的存儲單元來存放二叉樹中的結(jié)點數(shù)據(jù)。一般是按照二叉樹結(jié)點自上而下、從左到右的順序進行存儲。但是在這種順序存儲方式下，結(jié)點在存儲位置上的前驅(qū)、后繼關(guān)系并不一定就能反映結(jié)點之間的孩子和雙親這種邏輯關(guān)系。也即，如果存在某種方法能夠?qū)崿F(xiàn)根據(jù)結(jié)點存放的相對位置就能反映結(jié)點之間的邏輯關(guān)系，這種順序存儲才有意義。由二叉樹的性質(zhì)可知，完全二叉樹和滿二叉樹采用順序存儲比較合適，這是因為樹中的結(jié)點序號可以唯一地反映出結(jié)點之間的邏輯關(guān)系，而用于實現(xiàn)順序存儲結(jié)構(gòu)的數(shù)組元素下標(biāo)又恰好與序號對應(yīng)。因此，用一維數(shù)組作為完全二叉樹的順序存儲結(jié)構(gòu)既能節(jié)省存儲空間，又能通過數(shù)組元素的下標(biāo)值來確定結(jié)點在二叉樹中的位置以及結(jié)點之間的邏輯關(guān)系。圖6-6給出了一棵完全二叉樹及其順序存儲結(jié)構(gòu)的示意圖。圖6-6完全二叉樹及其順序存儲結(jié)構(gòu)示意圖在圖6-6(b)的順序存儲結(jié)構(gòu)中，我們可以通過性質(zhì)5找到任一結(jié)點的雙親或孩子結(jié)點，即結(jié)點之間的邏輯關(guān)系可通過結(jié)點在數(shù)組中的位置(數(shù)組元素的下標(biāo))準(zhǔn)確地反映出來。注意，如果由數(shù)組的下標(biāo)0開始順序存放完全二叉樹的結(jié)點數(shù)據(jù)，則相應(yīng)的第i號結(jié)點的雙親結(jié)點編號為 ，左孩子編號為2i+1,右孩子編號為2(i+1)。對于一般二叉樹，如果仍按自上而下、從左到右的順序存放二叉樹中的所有結(jié)點數(shù)據(jù)到一維數(shù)組中，則數(shù)組元素的下標(biāo)并不能反映一般二叉樹結(jié)點之間的邏輯關(guān)系。為了利用數(shù)組元素下標(biāo)來反映結(jié)點之間的邏輯關(guān)系，則只能添加一些并不存在的“空結(jié)點”，從而將一般二叉樹轉(zhuǎn)化為完全二叉樹，然后再用一維數(shù)組存儲。圖6-7給出了一棵一般二叉樹以及改造后的完全二叉樹及其順序存儲示意圖。顯然，這種改造后的存儲造成了存儲空間的浪費。因此，順序存儲適用于完全二叉樹和滿二叉樹，但不適用于一般二叉樹。最壞的情況是單支樹，一棵深度為k的右單支樹雖然只有k個結(jié)點，卻需給其分配2k-1個結(jié)點的存儲空間。圖6-7一般二叉樹及其順序存儲

2.鏈?zhǔn)酱鎯Y(jié)構(gòu)

二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)不但要存儲結(jié)點的數(shù)據(jù)信息，而且要使用指針來反映結(jié)點之間的邏輯關(guān)系。最常用的二叉樹鏈?zhǔn)酱鎯Y(jié)構(gòu)是二叉鏈表，其結(jié)點的存儲結(jié)構(gòu)如下：

也即，二叉鏈表中每個結(jié)點由三個域(成員)組成：一個是數(shù)據(jù)域data，用于存放結(jié)點的數(shù)據(jù)；另外兩個是指針域lchild和rchild，分別用來存放結(jié)點的左孩子結(jié)點和右孩子結(jié)點的存儲地址。二叉鏈表的結(jié)點類型定義如下：

typedefstructnode

{

datatypedata; //結(jié)點數(shù)據(jù)

structnode*lchild,*rchild; //左、右子孩子指針

}BSTree;圖6-8(b)給出了圖6-8(a)所示二叉樹的二叉鏈表存儲表示，當(dāng)左孩子或右孩子不存在時，相應(yīng)指針域值為空(用符號“”或NULL表示)。此外，在圖6-8中還給出了一個指針變量tree來指向根結(jié)點。

為了便于找到結(jié)點的雙親，也可以在結(jié)點中增加指向雙親結(jié)點的指針parent，這就是三叉鏈表。三叉鏈表中每個結(jié)點由4個域組成：圖6-8二叉樹及其鏈表存儲結(jié)構(gòu) 6.3二叉樹的遍歷

6.3.1二叉樹的遍歷方法

由于二叉樹的定義是遞歸的，因此一棵非空二叉樹可以看作是由根結(jié)點、左子樹和右子樹這三個基本部分組成。如果能依次遍歷這三個部分的信息，也就遍歷了整個二叉樹。因此，二叉樹的遍歷就是按某種策略訪問二叉樹中每一個結(jié)點并且僅訪問一次的過程。若以字母D、L、R分別表示訪問根結(jié)點、遍歷根結(jié)點的左子樹、遍歷根結(jié)點的右子樹，則二叉樹的遍歷方式有6種：DLR、LDR、LRD、DRL、RDL和RLD。如果限定先左后右則只有前3種方式：即DLR、LDR和LRD，分別被稱之為先序(又稱前序)遍歷、中序遍歷和后序遍歷。

遍歷二叉樹的實質(zhì)就是對二叉樹線性化的過程，即遍歷的結(jié)果是將非線性結(jié)構(gòu)的二叉樹中的結(jié)點排成一個線性序列，而且三種遍歷的結(jié)果都是線性序列。遍歷二叉樹的基本操作就是訪問結(jié)點，對含有n個結(jié)點的二叉樹不論按哪種次序遍歷，其時間復(fù)雜度均為O(n)，這是因為在遍歷過程中實際是按照結(jié)點的左、右指針遍歷二叉樹的每一個結(jié)點。此外，遍歷所需的輔助空間為棧的容量，在遍歷中每遞歸調(diào)用一次都要將有關(guān)結(jié)點的信息壓入棧中，棧的容量恰為樹的深度，最壞情況下是n個結(jié)點的單支樹，這時樹的深度為n，所以空間復(fù)雜度為O(n)。6.3.2遍歷二叉樹的遞歸算法及遍歷示例

1.先序遍歷二叉樹的遞歸算法

voidPreorder(BSTree*p) //先序遍歷二叉樹

{

if(p!=NULL)

{

printf("%3c",p->data); //訪問根結(jié)點

Preorder(p->lchild); //先序遍歷左子樹

Preorder(p->rchild); //先序遍歷右子樹

}

}

2.中序遍歷二叉樹的遞歸算法

voidInorder(BSTree*p) //中序遍歷二叉樹

{

if(p!=NULL)

{

Inorder(p->lchild); //中序遍歷左子樹

printf("%3c",p->data); //訪問根結(jié)點

Inorder(p->rchild); //中序遍歷右子樹

}

}

3.后序遍歷二叉樹的遍歷算法

voidPostorder(BSTree*p) //后序遍歷二叉樹

{

if(p!=NULL)

{

Postorder(p->lchild); //后序遍歷左子樹

Postorder(p->rchild); //后序遍歷右子樹

printf("%3c",p->data); //訪問根結(jié)點

}

}

例6.2

給出圖6-9所示二叉樹的先序、中序和后序遍歷序列。

【解】因為二叉樹的定義是遞歸的，所以一棵非空二叉樹可以看作由根結(jié)點、左子樹和右子樹這三個基本部分組成，即依次遍歷這三個部分就遍歷了整個二叉樹。對左子樹或右子樹又可看作為一棵二叉樹并繼續(xù)往下分為根結(jié)點、左子樹和右子樹三個部分，這種劃分可以一直持續(xù)到葉子結(jié)點。圖6-10的虛線框即為圖6-9中二叉樹不斷遞歸劃分為根結(jié)點、左子樹和右子樹這三個部分的示意圖。圖6-9二叉樹圖6-10二叉樹不斷劃分為根結(jié)點、左子樹和右子樹的示意圖

(1)先序為“根左右”，由圖6-10可得到如圖6-11所示的先序示意圖。圖6-11先序序列生成示意圖即從左到右排列的先序序列為：fdbacegihj。

(2)中序為“左根右”，由圖6-10可得如圖6-12所示的中序示意圖。圖6-12中序序列生成示意圖

(3)后序為“左右根”，由圖6-10可得如圖6-13所示的后序示意圖。圖6-13后序序列生成示意圖

例6.3

有一個二叉樹，左、右子樹均有三個結(jié)點，其左子樹的先序序列與中序序列相同，其右子樹的中序序列與后序序列相同，試構(gòu)造該二叉樹。

【解】根據(jù)題意，左子樹的先序序列與中序序列相同，即有：先序：根左右中序：左根右

也即，以左子樹為根的二叉樹無左孩子。此外，右子樹的中序序列與后序序列相同，即有：中序：左根右后序：左右根圖6-14題設(shè)二叉樹示意圖

例6.4

二叉樹以二叉鏈表為存儲結(jié)構(gòu)，試設(shè)計一個算法，若結(jié)點左孩子的data域值大于右孩子的data值域，則交換其左右子樹。

【解】因為是交換左右子樹，所以只有先找到(定位于)某一符合條件的結(jié)點作為根結(jié)點時才能交換其左右子樹，故采用先序遍歷的方法實現(xiàn)。算法設(shè)計如下：

voidChange(BSTree*p)

{

BSTree*q;

if(p!=NULL)

{

if(p->lchild!=NULL&&p->rchild!=NULL&&p->lchild->data>p->rchild->data)

{//交換左、右孩子的指針

q=p->lchild;

p->lchild=p->rchild;

p->rchild=q;

}

Change(p->lchild);

Change(p->rchild);

}

}6.3.3遍歷二叉樹的非遞歸算法

1.先序遍歷二叉樹的非遞歸算法

先序非遞歸遍歷二叉樹的方法是：由根結(jié)點沿左子樹(即p->lchild所指)一直遍歷下去，在遍歷過程中每經(jīng)過一個結(jié)點時就輸出(訪問)該結(jié)點的信息并同時將其壓棧。當(dāng)某個結(jié)點無左子樹時就將這個結(jié)點由棧中彈出，并從這個結(jié)點的右子樹的根開始繼續(xù)沿其左子樹向下遍歷(對此時右子樹的根結(jié)點也進行輸出和壓棧操作)，直到棧中無任何結(jié)點時就實現(xiàn)了先序遍歷。先序遍歷二叉樹的非遞歸算法如下：

voidPreorder(BSTree*p) //先序遍歷二叉樹

{

BSTree*stack[MAXSIZE]; //MAXSIZE為大于二叉樹結(jié)點個數(shù)的常量

inti=0;

stack[0]=NULL; //棧初始化

while(p!=NULL||i>0) //當(dāng)指針p不空或棧stack不空(i>0)時

if(p!=NULL) //當(dāng)指針p不空時

{

printf("%3c",p->data); //輸出結(jié)點的信息

stack[++i]=p; //將該結(jié)點壓棧

p=p->lchild; //沿左子樹向下遍歷

}

else //當(dāng)指針p為空時

{

p=stack[i--]; //將這個無左子樹的結(jié)點由棧中彈出

p=p->rchild; //從該結(jié)點右子樹的根開始繼續(xù)沿左子樹向下遍歷

}

}

2.中序遍歷二叉樹的非遞歸算法

中序非遞歸遍歷二叉樹與先序非遞歸遍歷二叉樹的過程基本相同，僅是輸出結(jié)點信息的語句位置發(fā)生了變化，即每當(dāng)需要沿當(dāng)前結(jié)點的右子樹根開始繼續(xù)沿其左子樹向下遍歷時(即此時已經(jīng)遍歷過當(dāng)前結(jié)點的左子樹了)，就先輸出這個當(dāng)前結(jié)點的信息。中序遍歷二叉樹非遞歸算法如下：

voidInorder(BSTree*p) //中序遍歷二叉樹

{

BSTree*stack[MAXSIZE]; //MAXSIZE為大于二叉樹結(jié)點個數(shù)的常量

inti=0;

stack[0]=NULL; //棧初始化

while(i>=0) //當(dāng)棧stack不空(i>0)時

{

if(p!=NULL) //當(dāng)指針p不空時

{

stack[++i]=p; //將該結(jié)點壓棧

p=p->lchild; //沿左子樹向下遍歷

}

else //當(dāng)指針p為空時

{

p=stack[i--]; //將這個無左子樹的結(jié)點由棧中彈出

printf("%3c",p->data); //輸出結(jié)點的信息

p=p->rchild;//從該結(jié)點右子樹的根開始繼續(xù)沿左子樹向下遍歷

}

if(p==NULL&&i==0) //當(dāng)指針p為空且棧stack也為空時結(jié)束循環(huán)

break;

}

}

3.后序遍歷二叉樹的非遞歸算法

后序非遞歸遍歷二叉樹與前面兩種非遞歸遍歷算法有所不同，它除了使用棧stack之外，還需使用一個數(shù)組b來記錄二叉樹中結(jié)點i(i=1,2,3,…,n)當(dāng)前遍歷的情況：如果b[i]為0，則表示僅遍歷過結(jié)點i的左子樹，它的右子樹還沒遍歷過；如果b[i]為1，則表示結(jié)點i的左、右子樹都已經(jīng)遍歷過。后序非遞歸遍歷二叉樹的過程仍然是由根結(jié)點開始沿左子樹向下進行遍歷，并且將遇到的所有結(jié)點順序壓棧。當(dāng)某個結(jié)點j無左子樹時就將結(jié)點j由棧stack中彈出，然后檢查b[j]是否為0，如果b[j]為0則表示結(jié)點j的右子樹還未遍歷過，也即必須遍歷過結(jié)點j的右子樹后方可輸出結(jié)點j的信息，所以必須先遍歷結(jié)點j的右子樹，即將結(jié)點j重新壓棧并置b[j]為1(作為遍歷過左、右子樹的標(biāo)識)，然后再將結(jié)點j的右孩子壓棧并沿右孩子的左子樹繼續(xù)向下遍歷。直到某一時刻該結(jié)點j再次由棧中彈出，因為此時b[j]已經(jīng)為1，即表示此時結(jié)點j的左、右子樹都已遍歷過(結(jié)點j的左、右子樹上的所有結(jié)點信息都已輸出)，或者結(jié)點j本身就是一個葉結(jié)點，這時就可以輸出結(jié)點j的信息了。為了統(tǒng)一，對于前者，在輸出了結(jié)點j的信息后即置結(jié)點j的父結(jié)點指向結(jié)點j的指針值為NULL。這樣，當(dāng)某個結(jié)點的左、右孩子指針都為NULL時，則意味著或者該結(jié)點本身就為葉結(jié)點，或者該結(jié)點左、右子樹中的結(jié)點信息都已輸出過，此時就可以輸出該結(jié)點的信息了。后序遍歷二叉樹非遞歸算法如下：

voidPostorder(BSTree*p) //后序遍歷二叉樹

{

BSTree*stack[MAXSIZE];//MAXSIZE為大于二叉樹結(jié)點個數(shù)的常量

intb[MAXSIZE],i=0; //數(shù)組b用于標(biāo)識每個結(jié)點是否已遍歷過其左、右子樹

stack[0]=NULL; //棧初始化

do

{

if(p!=NULL) //當(dāng)指針p不空時

{

stack[++i]=p; //將遍歷中遇到的所有結(jié)點依次壓棧

b[i]=0; //置該結(jié)點右子樹未訪問過的標(biāo)志

p=p->lchild; //沿該結(jié)點左子樹繼續(xù)向下遍歷

}

else //當(dāng)指針p為空時

{

p=stack[i--]; //將這個無左子樹(或左子樹已遍歷過)的當(dāng)前結(jié)點由棧中彈出

if(!b[i+1]) //b[i+1]為0則當(dāng)前結(jié)點的右子樹未遍歷

{

stack[++i]=p; //將當(dāng)前結(jié)點重新壓棧

b[i]=1; //置當(dāng)前結(jié)點右子樹已訪問過標(biāo)志

p=p->rchild; //沿當(dāng)前結(jié)點右孩子繼續(xù)向下遍歷

}

else //當(dāng)前結(jié)點的左、右子樹都已遍歷(即結(jié)點信息都已輸出)

{

printf("%3c",p->data); //輸出當(dāng)前結(jié)點的信息

p=NULL; //將指向當(dāng)前結(jié)點的指針置為空

}

}

}while(p!=NULL||i>0);//當(dāng)指針p不空或棧stack不空(i>0)時繼續(xù)遍歷

}這種后序遍歷二叉樹的非遞歸算法，其優(yōu)點是只需一重循環(huán)即可實現(xiàn)，而缺點是遍歷之后原二叉樹就被破壞。另一種不破壞二叉樹卻需兩重循環(huán)實現(xiàn)的后序遍歷非遞歸算法如下：

voidPostorder1(BSTree*p)

{

BSTree*stack[MAXSIZE],*q; //MAXSIZE為大于二叉樹結(jié)點個數(shù)的常量

intb,i=-1;

do

{

while(p!=NULL) //將*p結(jié)點左分支上的所有左孩子入棧

{

stack[++i]=p;

p=p->lchild;

}

//棧頂結(jié)點已沒有左孩子或其左子樹上的結(jié)點都已訪問過

q=NULL;

b=1; //置已訪問過的標(biāo)記

while(i>=0&&b) //棧stack不空且當(dāng)前棧頂結(jié)點的左子樹已經(jīng)遍歷過

{

p=stack[i]; //取出當(dāng)前棧頂結(jié)點

if(p->rchild==q) //當(dāng)前棧頂結(jié)點*p無右孩子或*p的右孩子已訪問過

{

printf("%3c",p->data); //輸出當(dāng)前棧頂結(jié)點*p的信息

i--;

q=p; //q指向剛訪問過的結(jié)點*p

}

else //當(dāng)前棧頂結(jié)點*p有右子樹

{

p=p->rchild; //p指向當(dāng)前棧頂結(jié)點*p的右孩子結(jié)點

b=0; //置該右孩子結(jié)點未遍歷過其右子樹標(biāo)記

}

}

}while(i>=0); //當(dāng)棧stack非空時繼續(xù)遍歷

}算法中，表達式“p->rchild==q”的含義是：若q等于NULL，則表示結(jié)點*p的右孩子不存在且*p的左子樹或不存在或已遍歷過，所以現(xiàn)在可以訪問結(jié)點*p了；若q不等于NULL，則表示*p的右孩子已訪問過(因為q指向p的右子樹中剛被訪問過的結(jié)點，而*q此時又是*p的右孩子，即意味著p的右子樹中所有結(jié)點都訪問過)，所以現(xiàn)在可以訪問*p。6.3.4二叉樹的層次遍歷算法

二叉樹的層次遍歷是指從二叉樹的第一層(即根結(jié)點)開始，對整棵二叉樹進行自上而下的逐層遍歷。在同一層中，則按從左至右的順序逐個訪問該層的每一個結(jié)點。例如，對圖6-9所示的二叉樹，按層次遍歷所得到的遍歷序列為：

fdgbeiachj在進行層次遍歷時，對某一層結(jié)點訪問完后，再按照它們的訪問次序?qū)Ω鱾€結(jié)點的左孩子和右孩子順序訪問。這樣一層一層的進行，先訪問的結(jié)點其左、右孩子也必定先訪問，這恰好與隊列的操作相吻合。因此，在進行層次遍歷時可設(shè)置一個隊列結(jié)構(gòu)，遍歷從二叉樹的根結(jié)點開始，即首先訪問根結(jié)點并同時將根結(jié)點的指針t入隊，然后在隊不為空的情況下循環(huán)執(zhí)行下述操作：先從隊頭取出一個結(jié)點*p，若*p有左孩子則訪問左孩子并將指向左孩子的指針入隊；若*p有右孩子則訪問右孩子并將指向右孩子的指針入隊。這種不斷入隊、出隊的操作一直持續(xù)到隊空為止，而此時二叉樹的所有結(jié)點都已遍歷。

voidTransleve(BSTree*t) //層次遍歷二叉樹

{

SeQueue*Q;

BSTree*p;

Init_SeQueue(&Q); //隊列Q初始化

if(t!=NULL) //二叉樹t非空

printf("%2c",t->data); //輸出根結(jié)點信息

In_SeQueue(Q,t); //指針t入隊

while(!Empty_SeQueue(Q)) //隊Q非空

{

Out_SeQueue(Q,&p); //隊頭結(jié)點(即指針值)出隊并賦給p

if(p->lchild!=NULL) //*p有左孩子

{

printf("%2c",p->lchild->data); //輸出左孩子信息

In_SeQueue(Q,p->lchild); //*p左孩子指針入隊

}

if(p->rchild!=NULL) //*p有右孩子

{

printf("%2c",p->rchild->data); //輸出右孩子信息

In_SeQueue(Q,p->rchild); //*p右孩子指針入隊

}

}

}6.3.5由遍歷序列恢復(fù)二叉樹

由二叉樹遍歷算法可知：任意給定一棵二叉樹，其遍歷得到的先序序列和中序序列都是唯一的。反之，如果知道一棵二叉樹的先序遍歷序列和中序遍歷序列，則根據(jù)這兩個序列是否能唯一恢復(fù)這棵二叉樹？根據(jù)二叉樹的定義，二叉樹的先序遍歷是先訪問根結(jié)點，然后先序遍歷根結(jié)點的左子樹，最后再先序遍歷根結(jié)點的右子樹。因此，在先序遍歷序列中的第一個結(jié)點一定是二叉樹的根結(jié)點。此外，二叉樹的中序遍歷是先中序遍歷根結(jié)點的左子樹，然后訪問根結(jié)點，最后再中序遍歷根結(jié)點的右子樹。由此可知，根結(jié)點在中序遍歷序列中必然將該中序序列分割成兩個子序列：根結(jié)點之前是根結(jié)點的左子樹所對應(yīng)的中序遍歷序列；根結(jié)點之后是根結(jié)點的右子樹所對應(yīng)的中序遍歷序列。根據(jù)這兩個子樹的中序序列，在先序遍歷序列中找到對應(yīng)的左子樹序列和右子樹序列，而此時左子樹序列中的第一個結(jié)點就是左子樹的根結(jié)點，右子樹序列中的第一個結(jié)點就是右子樹的根結(jié)點。這樣，就確定了二叉樹的根結(jié)點及其左、右子樹的根結(jié)點。接下來再分別對左、右子樹的根結(jié)點繼續(xù)劃分其左子樹序列和右子樹序列。如此遞歸劃分下去，當(dāng)取盡先序遍歷序列中的結(jié)點時，就唯一恢復(fù)了這棵二叉樹。與此類似，由二叉樹的后序遍歷序列和中序遍歷序列也可以唯一恢復(fù)這棵二叉樹。因為后序遍歷序列中的最后一個結(jié)點是二叉樹的根結(jié)點(它就是先序遍歷序列中的第一個結(jié)點)，即同樣可將中序遍歷序列分割成兩個子序列：根結(jié)點之前是根結(jié)點的左子樹所對應(yīng)的中序遍歷序列；根結(jié)點之后是根結(jié)點的右子樹所對應(yīng)的中序遍歷序列。根據(jù)這兩個子樹的中序序列，在后序遍歷序列中找到對應(yīng)的左子樹序列和右子樹序列，而此時左子樹序列中的最后一個結(jié)點就是左子樹的根結(jié)點，右子樹序列中的最后一個結(jié)點就是右子樹的根結(jié)點。然后再分別對左、右子樹的根結(jié)點繼續(xù)劃分其左子樹序列和右子樹序列。如此遞歸劃分下去，當(dāng)逆序取盡后序遍歷序列中的結(jié)點時，就唯一恢復(fù)了這棵二叉樹。

如果已知先序和后序的遍歷序列，但先序是“根、左、右”，后序是“左、右、根”，即由這兩種遍歷序列僅可獲得根結(jié)點的信息但卻無法區(qū)分左、右子樹，所以也就無法確定一棵二叉樹。根據(jù)二叉樹的先序序列和中序序列恢復(fù)二叉樹的遞歸思想是：先根據(jù)先序序列的第一個結(jié)點建立根結(jié)點，然后在中序序列中找到該結(jié)點，從而劃分出根結(jié)點的左、右子樹的中序序列。接下來再在先序序列中確定左、右子樹的先序序列，并由左子樹的先序序列與中序序列繼續(xù)遞歸建立左子樹，由右子樹的先序序列與中序序列繼續(xù)遞歸建立右子樹。

為了能夠?qū)⒒謴?fù)的二叉樹傳回給主調(diào)函數(shù)，在函數(shù)Pre_In_order中使用了二級指針**p。在下面的算法中，二叉樹的先序遍歷序列和中序遍歷序列分別存放在一維數(shù)組pred和ind中。算法如下：voidPre_In_order(charpred[],charind[],inti,intj,intk,inth,BSTree**p)

{//i、j和k、h分別為當(dāng)前子樹先序序列和中序序列的下、上界

intm;

*p=(BSTree*)malloc(sizeof(BSTree));//在主調(diào)函數(shù)空間申請一個結(jié)點

(*p)->data=pred[i];//根據(jù)pred數(shù)組生成二叉樹的根結(jié)點

m=k;//m指向ind數(shù)組所存儲的中序序列中第一個結(jié)點

while(ind[m]!=pred[i])//找到根結(jié)點在中序序列所在的位置

m++;

if(m==k)//根結(jié)點是中序序列的第一個結(jié)點時則無左子樹

(*p)->lchild=NULL;

else

Pre_In_order(pred,ind,i+1,i+m-k,k,m-1,&(*p)->lchild);

//根據(jù)根結(jié)點所劃分出中序序列的兩個部分繼續(xù)構(gòu)造左、右兩棵子樹

if(m==h)//根結(jié)點是中序序列的最后一個結(jié)點時則無右子樹

(*p)->rchild=NULL;

else

Pre_In_order(pred,ind,i+m-k+1,j,m+1,h,&(*p)->rchild);

//根據(jù)根結(jié)點所劃分出中序序列的兩個部分繼續(xù)構(gòu)造左、右兩棵子樹

}

例6.5

已知一個非空二叉樹，其中序和后序遍歷的結(jié)果為

中序：CGBAHEDJFI

后序：GBCHEJIFDA

試將該二叉樹構(gòu)造出來。

【解】根據(jù)定義，二叉樹的后序遍歷為：左、右、根。也就是說，后序序列中的最后一個結(jié)點一定是二叉樹的根結(jié)點。而二叉樹的中序遍歷為：左、根、右，因此，根結(jié)點在中序序列中必然把這個中序序列分割為兩個子序列，根結(jié)點前面的子序列就是根結(jié)點的左子樹，根結(jié)點后面的子序列就是根結(jié)點的右子樹。對于各左、右子樹，我們可以繼續(xù)上述的劃分，如此遞歸下去，最終就可以得到一棵二叉樹，為了便于區(qū)分左、右子樹，我們在左子樹序列的下面加上下劃線“

”，在右子樹序列的下面加上下劃線“

”，而加粗的字母則為當(dāng)前子樹的根結(jié)點。即有：

(1)先由后序序列：GBCHEJIFDA(A即為根結(jié)點)得到中序序列的劃分：CGBAHEDJFI。

(2)對左子樹：CGB，由后序序列：GBC(C為根結(jié)點)得到中序序列的劃分：CGB。

(3)對右子樹：GB，由后序序列：GB(B為根結(jié)點)得到中序序列的劃分：GB。

(4)對右子樹：HEDJFI，由后序序列：HEJIFD(D為根結(jié)點)得到中序序列的劃分：HEDJFI。

(5)對左子樹：HE，由后序序列：HE(E為根結(jié)點)得到中序序列的劃分：HE。

(6)對右子樹：JFI，由后序序列：JIF(F為根結(jié)點)得到中序序列的劃分：JFI。圖6-15根據(jù)中序和后序序列構(gòu)造的二叉樹6.3.6二叉樹遍歷的應(yīng)用

1.查找數(shù)據(jù)元素

在p為根結(jié)點指針的二叉樹中進行中序非遞歸遍歷來查找數(shù)據(jù)元素x(即結(jié)點數(shù)據(jù))。查找成功時返回該結(jié)點的指針；查找失敗時則返回空指針，算法實現(xiàn)如下：

BSTree*Search(BSTree*p,charx) //中序遍歷查找數(shù)據(jù)元素

{

BSTree*stack[MAXSIZE]; //MAXSIZE為大于二叉樹結(jié)點個數(shù)的常量

inti=0;

stack[0]=NULL; //棧初始化

while(i>=0) //當(dāng)指針p不空或棧stack不空(i>0)

{

if(p!=NULL) //當(dāng)指針p不空時

{

if(p->data==x)

returnp; //查找成功返回p指針值

else

stack[++i]=p; //將該結(jié)點壓棧

p=p->lchild; //沿左子樹向下遍歷

}

else //當(dāng)指針p為空時

{

p=stack[i--]; //將這個無左子樹的結(jié)點由棧中彈出

p=p->rchild; //從該結(jié)點右子樹的根開始繼續(xù)沿左子樹向下遍歷

}

if(p==NULL&&i==0)

break; //當(dāng)指針p為空且棧stack也為空時結(jié)束循環(huán)

}

returnNULL; //查找失敗

}注意，用下面先序遍歷二叉樹的遞歸函數(shù)也可以查找數(shù)據(jù)元素。

BSTree*Search(BSTree*bt,datatypex)//查找數(shù)據(jù)元素

{

BSTree*p;

if(bt!=NULL) //當(dāng)指針bt非空時

{

if(bt->data==x) //如果當(dāng)前結(jié)點*bt的data值等于x

returnbt; //查找成功返回bt指針值

if(bt->lchild!=NULL)

{ //在bt->lchid為根結(jié)點指針的二叉樹中查找

p=Search(bt->lchild,x);

if(p!=NULL)

returnp; //查找成功返回p指針值

}

if(bt->rchild!=NULL)

{ //在bt->rchild為根結(jié)點指針的二叉樹中查找

p=Search(bt->rchild,x);

if(p!=NULL)

returnp; //查找成功返回p指針值

}

}

returnNULL; //查找失敗

}

2.統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)

算法實現(xiàn)如下：

intCountleaf(BSTree*p) //統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)

{

if(p==NULL)

return0; //空二叉樹

if(p->rchild==NULL&&p->lchild==NULL)

return1; //只有根結(jié)點

return(Countleaf(p->lchild)+Countleaf(p->rchild));

}

3.求二叉樹深度

如果二叉樹為空，則深度為0；如果二叉樹不為空，則令其深度等于左子樹和右子樹深度大者加1，即：Depth(p)=0 當(dāng)p=NULLDepth(p)=MAX{Depth(p->lchild),Depth(p->rchild)+1其他情況

算法實現(xiàn)如下(后序遍歷)：

intDepth(BSTree*p)//求二叉樹深度(后序遍歷)

{

intlchild,rchild;

if(p==NULL)

return0; //樹的深度為0

else

{

lchild=Depth(p->lchild); //求左子樹高度

rchild=Depth(p->rchild); //求右子樹高度

returnlchild>rchild?(lchild+1):(rchild+1);

}

}

4.建立二叉樹的二叉鏈表并輸出其中序遍歷序列

建立二叉樹的方法是：按二叉樹帶空指針的先序序列來輸入結(jié)點值，結(jié)點值的類型為字符型，并且按先序輸入中遇到的空指針一律輸入“.”字符。例如，對圖6-16所示的二叉樹存儲結(jié)構(gòu)，則相應(yīng)地輸入為：abc.d..e..fg...↙。

程序?qū)崿F(xiàn)如下：

#include<stdio.h>

#include<stdlib.h>

#defineMAXSIZE30

typedefstructnode

{圖6-16二叉樹存儲結(jié)構(gòu)示意圖

chardata; //結(jié)點數(shù)據(jù)

structnode*lchild,*rchild; //左、右子孩子指針

}BSTree;

voidInorder(BSTree*p) //中序遍歷二叉樹

{

if(p!=NULL)

{

Inorder(p->lchild); //中序遍歷左子樹

printf("%3c",p->data); //訪問根結(jié)點

Inorder(p->rchild); //中序遍歷右子樹

}

}

voidCreateb(BSTree**p)

{

charch;

scanf("%c",&ch); //讀入一個字符

if(ch!='.') //如果該字符不為'.'

{

*p=(BSTree*)malloc(sizeof(BSTree)); //在主調(diào)函數(shù)空間申請一個結(jié)點

(*p)->data=ch;//將讀入的字符送結(jié)點的數(shù)據(jù)域

Createb(&(*p)->lchild);//沿左孩子分支繼續(xù)生成二叉樹

Createb(&(*p)->rchild);//沿右孩子分支繼續(xù)生成二叉樹

}

else//如果讀入的字符為'.'則置指針域為空

*p=NULL;

}

voidmain()

{

BSTree*root;

printf("Preorderentetbitreewith'..':\n");

Createb(&root); //建立一棵以root為根指針的二叉樹

printf("Inorderoutput:\n");

Inorder(root); //中序遍歷二叉樹

printf("\n");

}

程序運行后得到的中序序列結(jié)果如下：abcdefg。

6.4線索二叉樹

6.4.1線索二叉樹的定義及結(jié)構(gòu)

我們知道，二叉樹遍歷的實質(zhì)是對非線性結(jié)構(gòu)的樹進行線性化的過程，它使得每個結(jié)點(除第一個和最后一個結(jié)點外)在這種線性序列中有且僅有一個直接前驅(qū)和一個直接后繼。但是在二叉鏈表的存儲方式中，我們只能找到每個結(jié)點的左、右孩子信息，而不能直接得到一個結(jié)點在先序、中序和后序遍歷這任一序列中的前驅(qū)和后繼信息，這些信息只有在遍歷二叉樹的動態(tài)過程中才能獲得。為了保留結(jié)點在某種遍歷序列中其直接前驅(qū)和直接后繼的位置信息，可以在每個結(jié)點中增加兩個指針域來存放在遍歷時所得到的有關(guān)前驅(qū)和后繼的信息，但這種方法卻降低了存儲空間的利用率。

對于采用二叉鏈表存儲結(jié)構(gòu)的二叉樹來說，如果該二叉樹有n個結(jié)點，則存放這n個結(jié)點的二叉鏈表中就有2n個指針域，且只有n-1個指針域是用來存儲孩子結(jié)點地址的，而另外n+1個指針域為空。因此，可以利用結(jié)點空的左指針域(lchild)來指向該結(jié)點在某種遍歷序列中的直接前驅(qū)結(jié)點；利用結(jié)點空的右指針域(rchild)來指向該結(jié)點在某種遍歷序列中的直接后繼結(jié)點。對于那些非空的指針域，則仍然存放指向該結(jié)點左、右孩子的指針。這些指向直接前驅(qū)結(jié)點或直接后繼結(jié)點的指針被稱為線索(Thread)，加了線索的二叉樹被稱為線索二叉樹。將二叉樹中所有結(jié)點排列成一個線性序列可采用不同的遍歷方法(即先序、中序、后序)得到。因此，線索樹有先序線索二叉樹、中序線索二叉樹和后序線索二叉樹三種。并且，我們把二叉樹改造成線索二叉樹的過程稱為線索化。

例如，對圖6-17(a)所示的二叉樹進行線索化，得到的先序線索二叉樹、中序線索二叉樹和后序線索二叉樹分別如圖6-17(b)、圖6-17(c)和6-17(d)所示，圖中的實線表示指針，虛線表示線索。圖6-17二叉樹及線索后的三種線索二叉樹接下來的問題是：在二叉鏈表存儲中如何區(qū)分一個結(jié)點的指針域存放的是指針還是線索？這種區(qū)分可以采用下面兩種方法實現(xiàn)。

(1)為每個結(jié)點增設(shè)兩個標(biāo)志位ltag和rtag，并令：0lchild指向結(jié)點的左孩子1lchild指向結(jié)點的直接前驅(qū)結(jié)點0rchild指向結(jié)點的右孩子1rchild指向結(jié)點的直接后繼每個標(biāo)志位只占一個bit，這樣就只需增加很少的存儲空間。這種情況下的結(jié)點結(jié)構(gòu)為：

(2)不改變結(jié)點的結(jié)構(gòu)，僅在作為線索的地址前加一個負號。也即，負地址表示線索而正地址表示指針。

在此，我們按第一種方法來介紹線索二叉樹的存儲。為了將二叉樹中所有的空指針都利用起來以及操作方便的需要，在存儲線索二叉樹時通常增加一個頭結(jié)點，其結(jié)構(gòu)與其他線索二叉樹的結(jié)點結(jié)構(gòu)完全一樣，只是其數(shù)據(jù)域不存放數(shù)據(jù)而已。這個頭結(jié)點的左指針指向二叉樹的根結(jié)點，而右指針則指向某種遍歷序列的最后一個結(jié)點。并且，二叉樹在某種遍歷下的第一個結(jié)點的前驅(qū)線索和最后一個結(jié)點的后繼線索都指向這個頭結(jié)點。

圖6-18給出了圖6–17(b)所示的先序線索二叉樹的存儲結(jié)構(gòu)。圖6-18先序線索樹的存儲結(jié)構(gòu)6.4.2線索化二叉樹

為了實現(xiàn)線索化二叉樹，我們將二叉樹結(jié)點的類型定義修改為：

typedefstructnode

{

datatypedata; //結(jié)點數(shù)據(jù)

intltag,rtag;

//線索標(biāo)記

structnode*lchild;

//左孩子或直接前驅(qū)線索指針

structnode*rchild;

//右孩子或直接后繼線索指針

}TBTree;將二叉樹線索化的過程，實際上是在二叉樹遍歷過程中用線索取代空指針的過程。對同一棵二叉樹遍歷的方式不同，所得到的線索樹也不同。但無論哪種遍歷，實現(xiàn)線索的方法是一樣的，即都是設(shè)置一個指針pre始終指向剛被訪問過的結(jié)點，而指針p則用來指向正在訪問的結(jié)點，由此記錄下遍歷過程中訪問結(jié)點的先后關(guān)系，并對當(dāng)前訪問的結(jié)點*p做如下處理：

(1)若p所指結(jié)點有空指針域，則置相應(yīng)標(biāo)志位為1。

(2)若pre≠NULL，則看pre所指結(jié)點的右標(biāo)志是否為1，若為1則pre->rchild指向p所指向的當(dāng)前結(jié)點(即結(jié)點*p為結(jié)點*pre的直接后繼)。

(3)若p所指當(dāng)前結(jié)點的左標(biāo)志為1，則p->lchild指向pre所指的結(jié)點(即結(jié)點*pre為結(jié)點*p的直接前驅(qū))。

(4)將指針pre指向剛訪問的當(dāng)前結(jié)點*p(即pre=p;)，而p則下移指向新的當(dāng)前結(jié)點。

需要注意的是，在給一棵二叉樹添加線索時先要創(chuàng)建一個頭結(jié)點，并建立頭結(jié)點與二叉樹根結(jié)點的線索。當(dāng)二叉樹線索化后，還需建立最后一個結(jié)點與頭結(jié)點之間的線索。

下面，我們以建立中序線索二叉樹的算法為例予以說明，該算法分為Thread(p)算法和CreatThread(b)算法兩部分。

Thread(p)算法用于對以*p為根結(jié)點的二叉樹進行中序線索化。在該算法中，p總是指向當(dāng)前被線索化的結(jié)點，而pre作為全局變量則指向剛訪問過的結(jié)點。也即，*pre是*p的前驅(qū)結(jié)點，而*p是*pre的后繼結(jié)點。Thread(p)算法類似中序遍歷的遞歸算法，在p指針不為NULL時，先對*p結(jié)點的左子樹線索化，若*p結(jié)點沒有左孩子結(jié)點，則將其lchild指針線索化為指向其前驅(qū)結(jié)點*pre并將其標(biāo)志位ltag置為1；否則lchild指向左孩子結(jié)點。若*pre結(jié)點的rchild指針為NULL，則將rchild指針線索化為指向其后繼結(jié)點*p并將其標(biāo)志位rtag置為1；否則rchild指向其右孩子結(jié)點。然后將pre指向*p結(jié)點，再對*p結(jié)點的右子樹進行線索化。

CreatThread(b)算法是對以二叉鏈表存儲的二叉樹b進行中序線索化，并返回線索化后的頭結(jié)點指針root。實現(xiàn)方法是：先創(chuàng)建頭結(jié)點*root，其rchild域為線索，lchild域為鏈指針并指向二叉樹根結(jié)點*b。如果二叉樹b為空，則將lchild指向頭結(jié)點自身；否則將*root的lchild指向*b結(jié)點，并使pre也指向*root結(jié)點。然后調(diào)用Thread(b)對整個二叉樹線索化，即將指針b傳給形參指針p，從而使得*pre是*p的前驅(qū)結(jié)點。最后，加入指向頭結(jié)點的線索，并將頭結(jié)點的rchild指針域線索化為指向最后一個結(jié)點(由于線索化過程是進行到p等于NULL為止，所以最后一個結(jié)點就是*pre)。中序線索二叉樹算法如下：

TBTree*pre; //全局變量

voidThread(TBTree*p) //對二叉樹進行中序線索化

{

if(p!=NULL)

{

Thread(p->lchild); //先對*p的左子樹線索化

//到此，*p結(jié)點的左子樹不存在或已線索化，接下來對*p線索化

if(p->lchild==NULL) //*p的左孩子不存在則進行前驅(qū)線索

{

p->lchild=pre; //建立當(dāng)前結(jié)點*p的前驅(qū)線索

p->ltag=1;

}

else

p->ltag=0; //置*p的lchild指針為指向左孩子標(biāo)志

if(pre->rchild==NULL) //*pre的右孩子不存在則進行后繼線索

{

pre->rchild=p; //建立結(jié)點*pre的后繼線索

pre->rtag=1;

}

else

pre->rtag=0; //置*p的rchild指針為指向右孩子標(biāo)志

pre=p; //pre移至*p結(jié)點

Thread(p->rchild); //對*p的右子樹線索化

}

}

TBTree*CreatThread(TBTree*b) //建立中序線索二叉樹

{

TBTree*root;

root=(TBTree*)malloc(sizeof(TBTree));

//創(chuàng)建頭結(jié)點

root->ltag=0;

root->rtag=1;

if(b==NULL) //二叉樹為空

root->lchild=root;

else

{

root->lchild=b; //root的lchild指針指向二叉樹根結(jié)點*b

pre=root; //*pre是*p的前驅(qū)結(jié)點，pre指針用于線索

Thread(b); //對二叉樹b進行中序線索化

pre->rchild=root;

//最后處理，加入指向頭結(jié)點的線索

pre->rtag=1;

root->rchild=pre; //頭結(jié)點的rchild指針線索化為指向最后一個結(jié)點

}

returnroot; //返回線索化后指向二叉樹的頭結(jié)點的指針

}6.4.3訪問線索二叉樹

1.在中序線索二叉樹上查找任意結(jié)點的中序前驅(qū)結(jié)點

對中序線索二叉樹上的任一結(jié)點*p，尋找其中序前驅(qū)結(jié)點可分為下面兩種情況：

(1)若p->ltag等于1，則p->lchild即指向前驅(qū)結(jié)點(p->lchild為線索指針)。

(2)若p->ltag等于0，則表明*p有左孩子。根據(jù)中序遍歷的定義，*p的前驅(qū)結(jié)點是以*p的左孩子為根結(jié)點的子樹的最右結(jié)點。也即，沿*p左子樹的右指針鏈向下查找，直到某個結(jié)點的右標(biāo)志rtag為1時，則該結(jié)點就是所找的前驅(qū)結(jié)點。在中序線索樹上尋找結(jié)點*p的中序前驅(qū)結(jié)點算法如下：

TBTree*Inpre(TBTree*p)

{

TBTree*pre;

pre=p->lchild;

if(p->ltag==0) //*p有左孩子時

while(pre->rtag==0) //沿*p左子樹的右指針鏈向下查找直到某結(jié)點的rtag為1

pre=pre->rchild;

returnpre; //返回指向*p的中序前驅(qū)結(jié)點的指針值

}

2.在中序線索二叉樹上查找任意結(jié)點的中序后繼結(jié)點

對中序線索二叉樹上的任一結(jié)點*p，尋找其中序后繼結(jié)點可分為下面兩種情況：

(1)若p->rtag等于1，則p->rchild即指向后繼結(jié)點。

(2)若p->rtag等于0，則表明*p有右孩子。根據(jù)中序遍歷的定義，*p的后繼結(jié)點是以*P的右孩子為根結(jié)點的子樹的最左結(jié)點。也即，沿*p右子樹的左指針鏈向下查找，直到某個結(jié)點的左標(biāo)志ltag為1時，則該結(jié)點就是所找的后繼結(jié)點。在中序線索樹上尋找結(jié)點*p的中序后繼結(jié)點算法如下：

TBTree*InPost(TBTree*p)

{

TBTree*post;

post=p->rchild;

if(p->rtag==0) //*p有右孩子時

while(post->ltag==0) //沿*p右子樹的左指針鏈向下查找直到某結(jié)點的ltag為1

post=post->lchild;

returnpost;//返回指向*p的中序后繼結(jié)點的指針值

}

3.中序遍歷中序線索二叉樹

在中序線索二叉樹中，開始結(jié)點就是根結(jié)點的最左下結(jié)點，而求當(dāng)前結(jié)點在中序序列中的后繼和前驅(qū)結(jié)點方法如前所述，并且最后一個結(jié)點的rchild指針被線索化為指向頭結(jié)點。利用這些條件，在中序線索二叉樹中實現(xiàn)中序遍歷的算法如下：

voidInorder(TBTree*b) //中序遍歷中序線索二叉樹

{ //*b為中序線索二叉樹的頭結(jié)點

TBTree*p;

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

while(p!=b) //當(dāng)p不等于指向頭結(jié)點的指針b時

{

while(p->ltag==0) //尋找中序序列的第一個結(jié)點

p=p->lchild;

printf(“%3c”,p->data); //輸出中序序列的第一個結(jié)點數(shù)據(jù)

while(p->rtag==1&&p->rchild!=b)

{

//后繼線索存在且后繼線索不為頭結(jié)點時

p=p->rchild; //根據(jù)后繼線索找到后繼結(jié)點

printf("%3c",p->data); //輸出后繼結(jié)點信息

}

p=p->rchild; //無后繼線索則p指向右孩子結(jié)點

}

} 6.5哈夫曼樹

6.5.1哈夫曼樹的基本概念及構(gòu)造方法

哈夫曼(Huffman)樹又稱最優(yōu)二叉樹，是指對于一組帶有確定權(quán)