5.樹(shù)

前面幾章介紹的線性表、隊(duì)列、棧、串等都是線性數(shù)據(jù)結(jié)構(gòu),其特點(diǎn)是除頭結(jié)點(diǎn)和尾結(jié)點(diǎn)外,每個(gè)結(jié)點(diǎn)間具有唯一的前驅(qū)、后繼的關(guān)系,在物理存儲(chǔ)上,可以采用順序結(jié)構(gòu),也可以采用鏈?zhǔn)浇Y(jié)構(gòu)?，F(xiàn)實(shí)生活中還有一種非線性的數(shù)據(jù)結(jié)構(gòu),即在該結(jié)構(gòu)中至少一個(gè)結(jié)點(diǎn)有多個(gè)直接前驅(qū)或后繼結(jié)點(diǎn)。其中樹(shù)狀結(jié)構(gòu)和圖形結(jié)構(gòu)就是兩種十分重要的非線性結(jié)構(gòu)。樹(shù)狀結(jié)構(gòu)在計(jì)算機(jī)信息處理中應(yīng)用相當(dāng)廣泛,如文件系統(tǒng)、目錄組織、菜單管理等。樹(shù)狀結(jié)構(gòu)中常見(jiàn)的是樹(shù)（包括森林）和二叉樹(shù),本章介紹這兩種結(jié)構(gòu)的概念、存儲(chǔ)結(jié)構(gòu)和相關(guān)算法,并研究樹(shù)、森林、二叉樹(shù)之間的相互轉(zhuǎn)換,最后給出樹(shù)狀結(jié)構(gòu)在現(xiàn)實(shí)生活中的一些具體應(yīng)用。5.1樹(shù)、森林的基本概念5.1.1樹(shù)的定義樹(shù)是n(n>=0)個(gè)有限元素(習(xí)慣稱作結(jié)點(diǎn))的集合T。當(dāng)n=0時(shí),稱這棵樹(shù)為空樹(shù);當(dāng)n>0時(shí),集合T滿足如下條件:(1)有且只有一個(gè)稱為根(root)的結(jié)點(diǎn),它沒(méi)有直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼;(2)其余的n-1個(gè)結(jié)點(diǎn)可以劃分為m個(gè)互不相交的有限集T1,T2,T3,….Tm,其中每個(gè)集合Ti又是一棵樹(shù),稱為根(root)的子樹(shù)。每棵子樹(shù)的根結(jié)點(diǎn)有且只有一個(gè)直接前驅(qū),但有零個(gè)或多個(gè)直接后繼?？梢钥闯?樹(shù)的定義用到了遞歸的方法,即用樹(shù)來(lái)定義樹(shù),這種方法在后面樹(shù)(特別是二叉樹(shù))的遍歷、構(gòu)造等算法中經(jīng)常用到。

樹(shù)這種數(shù)據(jù)結(jié)構(gòu)在客觀世界中普遍存在,如一本書(shū)按章節(jié)劃分的目錄、一些計(jì)算機(jī)軟件中常見(jiàn)的操作菜單、自然界中的物種分類、一個(gè)國(guó)家的行政區(qū)域劃分等,都是這種層次性的結(jié)構(gòu)。如圖5.1中所示的樹(shù)表示了一個(gè)學(xué)院的行政關(guān)系。在樹(shù)狀結(jié)構(gòu)中,人們最熟悉的是一個(gè)家族的血緣關(guān)系,在后面樹(shù)狀結(jié)構(gòu)的描述中,也會(huì)經(jīng)常用到血緣關(guān)系的一些術(shù)語(yǔ)。5.1學(xué)院行政關(guān)系層次結(jié)構(gòu)樹(shù)

圖5.2樹(shù)的示例T

樹(shù)的表示常見(jiàn)的有樹(shù)狀表示法和邏輯表示法兩種,圖5.2給出了樹(shù)狀表示法的一個(gè)實(shí)例。樹(shù)的邏輯表示法則給出樹(shù)中的結(jié)點(diǎn)的集合及這個(gè)集合上的關(guān)系。如圖5.2中的樹(shù)可描述為T=(N,R)。其中結(jié)點(diǎn)集合N={A,B,C,D,E,F,G,HJ,J,K,L}N上的關(guān)系R={<A,B>,<A,C>,<A,D>,<B,E>,<B,F>,<C,G>,<D,H>,<D,I>,<D,J>,<E,K>,<E,L>}5.1.2基本術(shù)語(yǔ)下面結(jié)合圖5.2介紹樹(shù)的有關(guān)術(shù)語(yǔ):(1)結(jié)點(diǎn)的度(degree):結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù),如結(jié)點(diǎn)A的度為3,結(jié)點(diǎn)K的度為0。

(2)樹(shù)的度:一棵樹(shù)中各結(jié)點(diǎn)度的最大值,如樹(shù)T中各結(jié)點(diǎn)度的最大值為3.故樹(shù)T的度為3。

(3)葉子結(jié)點(diǎn)(leaf):度為0的結(jié)點(diǎn),又稱終端結(jié)點(diǎn),如樹(shù)T中的所有葉子結(jié)點(diǎn)分別為K、L、F、G、H、I、J。

(4)分支結(jié)點(diǎn)(branch)：度不為O的結(jié)點(diǎn),又稱非終端結(jié)點(diǎn),如樹(shù)T中的所有分支結(jié)點(diǎn)分別為B、C、D、E。

(5)孩子結(jié)點(diǎn)(child)：樹(shù)中一個(gè)結(jié)點(diǎn)的子樹(shù)的根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn),如結(jié)點(diǎn)B的孩子結(jié)點(diǎn)為E、F;結(jié)點(diǎn)G沒(méi)有孩子結(jié)點(diǎn)。(6)雙親結(jié)點(diǎn)(parents)：孩子結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)稱為該結(jié)點(diǎn)的雙親結(jié)點(diǎn),如結(jié)點(diǎn)B、C、D的雙親結(jié)點(diǎn)均為A;根結(jié)點(diǎn)A沒(méi)有雙親結(jié)點(diǎn)。

(7)兄弟結(jié)點(diǎn)(sibling)和堂兄弟結(jié)點(diǎn):具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱為兄弟,雙親在同一層的結(jié)點(diǎn)互稱為堂兄弟,如結(jié)點(diǎn)E的兄弟結(jié)點(diǎn)為F,堂兄弟結(jié)點(diǎn)為G、H、I、J。(8)祖先(ancestor)和子孫（Offspring):一個(gè)結(jié)點(diǎn)的祖先是從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn),反之,以某結(jié)點(diǎn)為根的子樹(shù)中的任一結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子孫,如K結(jié)點(diǎn)的祖先結(jié)點(diǎn)有A、B、E,B結(jié)點(diǎn)的子孫結(jié)點(diǎn)有E、F、K、L。(9)結(jié)點(diǎn)的層次(layer）：從根開(kāi)始,樹(shù)的根結(jié)點(diǎn)的層次(也稱層數(shù))定義為1,其余結(jié)點(diǎn)的層數(shù)等于它的雙親結(jié)點(diǎn)的層數(shù)加1,如A結(jié)點(diǎn)的層數(shù)為1,K結(jié)點(diǎn)的層數(shù)為4。(10)樹(shù)的深度(depth)：樹(shù)中所有結(jié)點(diǎn)的最大層數(shù)稱為樹(shù)的深度(也稱高度),如樹(shù)T的高度為4。(11)有序樹(shù)和無(wú)序樹(shù):樹(shù)T中,如果各子樹(shù)Ti之間是有先后次序的,則稱為有序樹(shù),否則稱為無(wú)序樹(shù)。(12)森林:m(m>0)棵互不相交的樹(shù)的集合。一棵樹(shù)刪除根結(jié)點(diǎn)所剩子樹(shù)的集合即為森林。5.1.3樹(shù)的基本操作對(duì)樹(shù)的基本操作主要有如下幾種:(1)InitTree(Tree):將Tree初始化為一棵空樹(shù)。(2)CreateTree(Tree）：創(chuàng)建樹(shù)Tree。(3)DestoryTree(Tree）：銷毀樹(shù)Tree。(4)isNull(Tree）：判斷樹(shù)Tree是否為空,為空則返回True;否則,返回False。(5)Root(Tree）：返回樹(shù)Tree的根。(6)Parent(Tree,x):返回結(jié)點(diǎn)x的父結(jié)點(diǎn)。當(dāng)結(jié)點(diǎn)x為根時(shí),返回空值Null。(7)FirstChild(Tree,x）：返回結(jié)點(diǎn)x的第一個(gè)孩子結(jié)點(diǎn)。當(dāng)結(jié)點(diǎn)x為葉子結(jié)點(diǎn)時(shí),返回空值Null。（8）NextSlibling(Tree,x):若x不是其雙親的最后一個(gè)孩子結(jié)點(diǎn),則返回x后面的下一個(gè)兄弟結(jié)點(diǎn);否則,返回空值Null。(9)InertChild(Tree，p,child)：樹(shù)Tree存在,p指向Tree中某個(gè)結(jié)點(diǎn),非空樹(shù)Child與Tree不相交,將Child插入Tree中,作為p所指向結(jié)點(diǎn)的子樹(shù)。(10)DeleteChild(Tmh，P，I）:樹(shù)Tree存在,p指向Tree中某個(gè)結(jié)點(diǎn),1<i<=d,d為p所指向結(jié)點(diǎn)的度。用于刪除Tree中p所指向結(jié)點(diǎn)的第i棵子樹(shù)。(11)TraverseTree(Tree,visit()):樹(shù)Tree存在,visit()是對(duì)結(jié)點(diǎn)進(jìn)行訪問(wèn)的函數(shù)。按照某種次序?qū)?shù)Tree的每個(gè)結(jié)點(diǎn)調(diào)用visit()函數(shù)訪問(wèn)一次且最多一次(又叫遍歷該樹(shù))。若visit()函數(shù)調(diào)用失敗,則操作失敗。5.2二叉樹(shù)5.2.1二叉樹(shù)的定義與基本操作把滿足以下條件的樹(shù)定義為二叉樹(shù)(binarytree):(1)每個(gè)結(jié)點(diǎn)的度都不大于2。(2)每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)不能任意顛倒。由二叉樹(shù)的定義可知,每個(gè)結(jié)點(diǎn)只能有0、1或2個(gè)子樹(shù)(孩子),且每個(gè)子樹(shù)(孩子)有左右之分。把位于左邊的叫做左子樹(shù)(孩子),右邊的叫做右子樹(shù)(孩子)。即使只有一棵子樹(shù)時(shí),也要區(qū)分它是左子樹(shù)還是右子樹(shù)。可見(jiàn)二叉樹(shù)具有5種形態(tài),如圖5.3所示。

下面再介紹兩種特殊的二叉樹(shù):滿二叉樹(shù)和完全二叉樹(shù)。滿二叉樹(shù):在一棵二叉樹(shù)中,除最后一層外,每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn),這樣的二叉樹(shù)稱為滿二叉樹(shù),如圖5.4所示。圖5.4滿二叉樹(shù)完全二叉樹(shù):在一棵深度為k,結(jié)點(diǎn)為n的二叉樹(shù)中,對(duì)樹(shù)中結(jié)點(diǎn)按從上到下,從左到右的順序編號(hào),如果編號(hào)為1~n的結(jié)點(diǎn)分別與滿二叉樹(shù)中編號(hào)為1~n的結(jié)點(diǎn)位置一一對(duì)應(yīng),則稱這樣的二叉樹(shù)為完全二叉樹(shù),如圖5.5所示。圖5.5滿二叉樹(shù)

二叉樹(shù)是一種特殊的樹(shù),故有關(guān)樹(shù)的術(shù)語(yǔ)也適用于二叉樹(shù)。與樹(shù)的基本操作類似,二叉樹(shù)有如下基本操作。(1)InitBiTree(BT）：將BT初始化為一棵空二叉樹(shù)。(2)CreateBiTree(BT）：創(chuàng)建一棵空二叉樹(shù)BT。(3)DestoryBiTree(BT）:銷毀二叉樹(shù)BT。(4)Root(BT):返回二叉樹(shù)BT的根結(jié)點(diǎn)。若BT為空二叉樹(shù),則返回空值Null。(5)Parent(BT,X):返回結(jié)點(diǎn)x的雙親結(jié)點(diǎn)。當(dāng)結(jié)點(diǎn)x為根時(shí),返回空值Null。(6)LeftChild(BT,x):返回結(jié)點(diǎn)x的左孩子.當(dāng)結(jié)點(diǎn)x為葉子結(jié)點(diǎn)或無(wú)左孩子時(shí),返回空值Null。(7)RightChild(BT,x):返回結(jié)點(diǎn)x的右孩子。當(dāng)結(jié)點(diǎn)x為葉子結(jié)點(diǎn)或無(wú)右孩子時(shí),返回空值Null。(8)TraverseTree(BT):遍歷二叉樹(shù)BT。按某種次序依次訪問(wèn)二叉樹(shù)中每個(gè)結(jié)點(diǎn)一次且僅一次。5.2.2二叉樹(shù)的性質(zhì)二叉樹(shù)具有如下重要的性質(zhì)：性質(zhì)1:在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i>=1〉。性質(zhì)2:深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)(k>=1)。性質(zhì)3:對(duì)任何一棵二叉樹(shù),如果其葉子結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則有:n0=n2+1。性質(zhì)4:具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n+1;性質(zhì)5:對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù),如果按照從上到下、從左到右的順序?qū)Χ鏄?shù)中的所有結(jié)點(diǎn)從1開(kāi)始編號(hào),則對(duì)于任意的序號(hào)i的結(jié)點(diǎn)有:(1)若i=1,則序號(hào)為i的結(jié)點(diǎn)是根結(jié)點(diǎn),無(wú)雙親結(jié)點(diǎn);若i>1,則序號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的序號(hào)為[i/2]。(2)若2i>n,則序號(hào)為i的結(jié)點(diǎn)無(wú)左孩子;若2i<n,則序號(hào)為i的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的序號(hào)為2i。(3)若21+1>n,則序號(hào)為i的結(jié)點(diǎn)無(wú)右孩子;若2i+1<=n,則序號(hào)為i的結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的序號(hào)為2i+1.5.2.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

二叉樹(shù)在存儲(chǔ)時(shí)有順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)兩種結(jié)構(gòu)。這里分別加以介紹。1.順序存儲(chǔ)結(jié)構(gòu)該方法是將二叉樹(shù)的所有結(jié)點(diǎn),按照一定的次序存儲(chǔ)到連續(xù)的存儲(chǔ)單元中。如對(duì)于一棵滿二叉樹(shù)或完全二叉樹(shù),將其結(jié)點(diǎn)從上到下,從左到右順序編號(hào),可以像存儲(chǔ)線性表一樣,存儲(chǔ)在連續(xù)的存儲(chǔ)空間中,如圖5.6所示。而大多數(shù)二叉樹(shù)結(jié)點(diǎn)只能按其所對(duì)應(yīng)的完全二叉樹(shù)位置進(jìn)行存儲(chǔ),如圖5.7所示圖5.6完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)圖5.7一般二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)

使用順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)是可以利用前一節(jié)所講的二叉樹(shù)的性質(zhì)計(jì)算出結(jié)點(diǎn)間的層次關(guān)系,實(shí)現(xiàn)相應(yīng)的操作。如可以利用地址公式計(jì)算結(jié)點(diǎn)的位置:結(jié)點(diǎn)i的左孩子的位置為L(zhǎng)oc-LChild(i)=2i,右孩子的位置為L(zhǎng)oc-RChildU)=2i+1。但這樣將導(dǎo)致存儲(chǔ)空間的浪費(fèi),極端的情況是對(duì)于一個(gè)二叉樹(shù),每個(gè)結(jié)點(diǎn)只有右孩子而無(wú)左孩子時(shí),假設(shè)該樹(shù)的深度為k,則需要2k-1個(gè)存儲(chǔ)單元,而實(shí)際只利用了其中的k個(gè)存儲(chǔ)單元。2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

解決上述順序存儲(chǔ)方法中空間浪費(fèi)的最自然的辦法就是采用指針。由二叉樹(shù)的定義可知,二叉樹(shù)的結(jié)點(diǎn)由一個(gè)數(shù)據(jù)元素和指向其左、右子樹(shù)的兩個(gè)分支構(gòu)成,這樣可以將其結(jié)點(diǎn)分為3個(gè)域:數(shù)據(jù)域(Data)、左指針域(Lchild)和右指針域(Rchild),。|Lchild|Data|Rchild|其中Data域存儲(chǔ)結(jié)點(diǎn)的信息,Lchild域和Rchild域分別指向該結(jié)點(diǎn)的左右孩子。由這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)構(gòu)成的二叉樹(shù)稱為二叉鏈表?？梢杂肅語(yǔ)言聲明二叉樹(shù)的二叉鏈表結(jié)點(diǎn)的結(jié)構(gòu):Structbtnode{datatypeData;/*datatype代表一種數(shù)據(jù)類型,如int、cha等*/struetbtnode*Lchild;struet

btnode*Rchild;};圖5.9(a)所示的任意一棵二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)如圖5.9(b)所示。

有時(shí)為了便于找到某結(jié)點(diǎn)的雙親結(jié)點(diǎn),可以增加一個(gè)Parent域,用于指向其雙親結(jié)點(diǎn),其結(jié)構(gòu)如圖5.10所示。

Lchild|data|Parent|Rchild|

帶Parent域的二叉樹(shù)結(jié)點(diǎn)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)5.3二叉樹(shù)的遍歷及應(yīng)用

遍歷是指按某種規(guī)則訪問(wèn)樹(shù)中的每個(gè)結(jié)點(diǎn)一次且僅訪問(wèn)一次。在二叉樹(shù)的一些具體應(yīng)用中,經(jīng)常要對(duì)樹(shù)中所有結(jié)點(diǎn)進(jìn)行某種計(jì)算(如計(jì)算結(jié)點(diǎn)的度和權(quán)值等),或者訪問(wèn)具有某種特征的結(jié)點(diǎn),這就涉及到遍歷的問(wèn)題。由于二叉樹(shù)是非線性結(jié)構(gòu),對(duì)二叉樹(shù)的遍歷比對(duì)線性結(jié)構(gòu)的遍歷要復(fù)雜得多。由前面二叉樹(shù)的定義,一棵二叉樹(shù)由根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)3部分組成,若依次遍歷這3部分,也就遍歷了整棵樹(shù)。這里用L、D、R分別表示遍歷左子樹(shù)、訪問(wèn)根結(jié)點(diǎn)、遍歷右子樹(shù),則對(duì)二叉樹(shù)的遍歷就有LDR、DLR、LRD、RDL、DRL、RLD6種方式。若按照從左到右的順序進(jìn)行遍歷,則有LDR、DLR、LRD3種方式,它們分別稱為中序遍歷、前序遍歷和后序遍歷。下面分別介紹這3種遍歷方式。1.前序遍歷(DLR)

前序遍歷二叉樹(shù)的算法為:若二叉樹(shù)為空,則遍歷結(jié)束,否則依次執(zhí)行以下操作。(1)訪問(wèn)根結(jié)點(diǎn);(2)前序遍歷根結(jié)點(diǎn)的左子樹(shù);(3)前序遍歷根結(jié)點(diǎn)的右子樹(shù)。;其具體算法實(shí)現(xiàn)如下:Preorder(Structbtnode*root)/*前序遍歷二叉樹(shù),root為指向二叉樹(shù)(或某一子樹(shù))根結(jié)點(diǎn)的指針*/{if(root!=NULL){Visit(root->data)/*訪問(wèn)根結(jié)點(diǎn)*/

preorder(root->Lchild)/*前序遍歷左子樹(shù)*/

preorder(root->Rchild)/*前序遍歷右子樹(shù)*/對(duì)于圖5.9(a)所示的二叉樹(shù),前序遍歷所得到的結(jié)點(diǎn)序列為:A、B、D、E、G、C、F【例】試按前序遍歷算法構(gòu)造一棵二叉樹(shù)。分析:可以參照上述前序遍歷的算法設(shè)定二叉樹(shù)各結(jié)點(diǎn)的值:(1)輸入根結(jié)點(diǎn)的值;(2)若左子樹(shù)不空,則輸入左子樹(shù),否則輸入一個(gè)結(jié)束符;(3)若右子樹(shù)不空,則輸入右子樹(shù),否則輸入一個(gè)結(jié)束符。例如對(duì)于圖5.9(a)所示的二叉樹(shù),如果以@代表結(jié)束符,則按該算法輸入的順序?yàn)?ABD@@EG@@@C@F@@該算法用C語(yǔ)言完整描述如下:#definenull0struetbtnode{chardata;structbtnode*Lchild;struetbtnode*Rchild;};struetbtnode*createbt(struet

btnode*bt,intk){charC;struet

btnode*p,*t;scanf(“%c",&c);if(c!=‘@’)/*@為結(jié)點(diǎn)符號(hào)*/{p=(struetbtnode*)malloc(sizeof(struet

btnode));p->data=C/*新結(jié)點(diǎn)的數(shù)據(jù)域?yàn)镃*/p->LChild=null;p->RChild=null;/*新結(jié)點(diǎn)的左右子樹(shù)為空*/

if(k==0)t=p;/*p的根結(jié)點(diǎn)*/

if(k==1)bt一>Ichild=p;/*鏈接到左子樹(shù)*/

if(k==2)bt->Rchild=p;/*鏈接到右子樹(shù)*/createbt(p,1);createbt(p,2);}return(t);/*返回根指針*/main()struet

btnode*root,*createbt();printf("inputnode:");root=createbt(root,0);/*創(chuàng)建一棵空二叉樹(shù)*/2.中序遍歷(LDR)

中序遍歷二叉樹(shù)的算法為:若二叉樹(shù)為空,則遍歷結(jié)束,否則依次執(zhí)行以下操作。(1)中序遍歷根結(jié)點(diǎn)的左子樹(shù);(2)訪問(wèn)根結(jié)點(diǎn);(3)中序遍歷根結(jié)點(diǎn)的右子樹(shù)。其具體算法實(shí)現(xiàn)如下:MidOrder(struet

btnode*root)//中序遍歷二叉樹(shù),root為指向二叉樹(shù)(或某一子樹(shù))根結(jié)點(diǎn)的指針{if(root!=NUIl){midorder(root->Lchild);//中序遍歷左子樹(shù)

visit(root->data);//訪問(wèn)根結(jié)點(diǎn)

Midorder(root->Rchild);//中序遍歷右子樹(shù)

}}同樣對(duì)于圖5.9(a)所示的二叉樹(shù),中序遍歷所得到的結(jié)點(diǎn)序列為:D、B、G、E、A、C、F3.后序遍歷(LRD)后序遍歷二叉樹(shù)的算法為:若二叉樹(shù)為空,則遍歷結(jié)束,否則依次執(zhí)行以下操作。(1)后序遍歷根結(jié)點(diǎn)的左子樹(shù);(2)后序遍歷根結(jié)點(diǎn)的右子樹(shù);(3)訪問(wèn)根結(jié)點(diǎn)。其具體算法實(shí)現(xiàn)如下:postOrder(struct

btnode*root)//后序遍歷二叉樹(shù),root為指向二叉樹(shù)(或某一子樹(shù))根結(jié)點(diǎn)的指針

{if(root!=NULL){postorde(root->Lchild);//后序遍歷左子樹(shù)

postorder(root->Rchild);//后序遍歷右子樹(shù)

visit(root->data)//訪問(wèn)根結(jié)點(diǎn)

}}對(duì)于圖5.9(a)所示的二叉樹(shù),后序遍歷所得到的結(jié)點(diǎn)序列為:D、G、E、B、F、C、A

為了便于理解二叉樹(shù)遍歷時(shí)的遞歸算法,我們以一個(gè)簡(jiǎn)單的二叉樹(shù)的中序遍歷為例,闡述遍歷時(shí)的遞歸過(guò)程,如圖5.11所示。（a）二叉樹(shù)（b）中序遍歷時(shí)經(jīng)過(guò)結(jié)點(diǎn)的情形

圖5.11：中序遍歷時(shí)的遞歸過(guò)程

當(dāng)中序遍歷圖5.11(a)所示的二叉樹(shù)時(shí),p指針首先指向A結(jié)點(diǎn)。按中序遍歷算法,先遍歷A的左子樹(shù),由此遞歸進(jìn)第2層,p指向B結(jié)點(diǎn),進(jìn)一步遞歸到B的左子樹(shù)。由于B的左子樹(shù)為空,對(duì)B的左子樹(shù)遍歷結(jié)束,退回到B結(jié)點(diǎn),訪問(wèn)B結(jié)點(diǎn)(這里用小黑點(diǎn)表示訪問(wèn)到的結(jié)點(diǎn))。遞歸進(jìn)入第3層,訪問(wèn)B的右子樹(shù),即以D為根結(jié)點(diǎn)的子樹(shù),由于D的左子樹(shù)為空,對(duì)D的左子樹(shù)遍歷結(jié)束,返回訪問(wèn)D結(jié)點(diǎn)。接著訪問(wèn)D結(jié)點(diǎn)的右子樹(shù),由于D的右子樹(shù)也為空,又返回D結(jié)點(diǎn),完成對(duì)D的遍歷,退到第2層。此時(shí)已完成對(duì)B的遍歷,退到第1層,訪問(wèn)A結(jié)點(diǎn)。再遞歸進(jìn)人第2層遍歷A的右子樹(shù),由于右子樹(shù)根結(jié)點(diǎn)C有左子樹(shù),故遞歸進(jìn)入第3層遍歷C的左子樹(shù)。由于結(jié)點(diǎn)E沒(méi)有左子樹(shù),故返回訪問(wèn)E結(jié)點(diǎn)。接著訪問(wèn)E結(jié)點(diǎn)的右子樹(shù),由于E的右子樹(shù)為空,又返回E結(jié)點(diǎn),完成對(duì)E的遍歷,退到第2層,訪問(wèn)C結(jié)點(diǎn)。接著訪問(wèn)C結(jié)點(diǎn)的右子樹(shù),由于C的右子樹(shù)為空,又返回C結(jié)點(diǎn),完成對(duì)C的遍歷,遞歸返回第1層,完成對(duì)A的遍歷。至此整個(gè)中序遍歷過(guò)程完成。通過(guò)上述遞歸過(guò)程可知,二叉樹(shù)的遍歷實(shí)際上是前面所學(xué)習(xí)的進(jìn)棧和出棧的過(guò)程,而且堆棧的深度與二叉樹(shù)的深度密切相關(guān)。[例題]：二叉樹(shù)以二叉鏈表的方式進(jìn)行存儲(chǔ),試寫(xiě)出求二叉樹(shù)高度的算法。分析:空樹(shù)的高度為0,一個(gè)結(jié)點(diǎn)的二叉樹(shù)的高度為1,結(jié)點(diǎn)數(shù)大于1的二叉樹(shù)的高度為左、右子樹(shù)的最大高度加1。根據(jù)前面的二叉樹(shù)遍歷過(guò)程的分析,二叉樹(shù)的深度與遞歸時(shí)所用堆棧的深度密切相關(guān),由此對(duì)遞歸算法稍加修改即可。int

High(struet

btnode*T)/*前序遍歷二叉樹(shù),root為指向二叉樹(shù)(或某一子樹(shù))根結(jié)點(diǎn)的指針*/{int

Lhight,Rhight;

if(T==NULL)return(0);else{Lhight=High(T->Lchild);/*考慮左子樹(shù)*/

Rhight=High(T->Rchild);/*考慮有子樹(shù)*/

if(Rhight>Lhight)return(Rhight+1);return(Lhight+1};}{例題：有一棵二叉樹(shù)的前序遍歷序列為A、C、I、K、N、H、L、M,中序遍歷序列為I、C、N、K、A、L、M、H,試畫(huà)出此二叉樹(shù)。分析:由于在前序遍歷中首先訪問(wèn)根結(jié)點(diǎn),因此,前序序列中的第一個(gè)結(jié)點(diǎn)為二叉樹(shù)的根結(jié)點(diǎn),即A為二叉樹(shù)的根結(jié)點(diǎn)。又由于在中序遍歷中訪問(wèn)根結(jié)點(diǎn)的次序?yàn)榫又?，左子?shù)的結(jié)點(diǎn)居前,右子樹(shù)的結(jié)點(diǎn)居后,因此,在中序序列中,以根結(jié)點(diǎn)(A)為分界線,前面的子序列(I、C、N、K)一定在左子樹(shù)中,后面的子序列(L、M、H）一定在右子樹(shù)中。同樣的道理,對(duì)于已經(jīng)劃分出的每一個(gè)子序列的所有結(jié)點(diǎn)中,位于前序序列最前面的一個(gè)結(jié)點(diǎn)為子樹(shù)的根結(jié)點(diǎn),而在中序序列中位于該根結(jié)點(diǎn)前面的結(jié)點(diǎn)構(gòu)成左子樹(shù)的結(jié)點(diǎn)子序列,位于該根結(jié)點(diǎn)后面的結(jié)點(diǎn)構(gòu)成右子樹(shù)的結(jié)點(diǎn)子序列。按此規(guī)則不斷循環(huán)下去,直到所有的子序列為單個(gè)結(jié)點(diǎn)為止,其求解過(guò)程如圖5.12所示圖5.12由前序和中序序列求解二叉樹(shù)的過(guò)程可以證明:根據(jù)二叉樹(shù)中的前序遍歷和中序遍歷序列、中序遍歷和后序遍歷序列,都能唯一地確定一棵二叉樹(shù)。但根據(jù)前序遍歷和后序遍歷序列或者依靠3種遍歷序列中的任何一種遍歷序列,都不能唯一地確定一棵二叉樹(shù)。二叉樹(shù)的這種性質(zhì)可以用于信息傳遞中的加密。例:試?yán)枚鏄?shù)的樹(shù)狀作為密鑰完成信息傳遞的加密。在密碼學(xué)中,通常將要傳遞的信息稱為明文,為了保護(hù)明文,可以將其通過(guò)某種方式變換成無(wú)法識(shí)別的密文,這個(gè)變換過(guò)程稱為加密;另一方面,密文可以通過(guò)相應(yīng)的逆變換過(guò)程再還原為明文,這個(gè)過(guò)程稱為解密。這里以M(Message)代表明文,C(Ciphertext)代表密文,E(Enciphering)代表加密變換,D(Deciphering)代表解密變換,用于加密的算法稱為密鑰K(key)(本例中用二叉樹(shù)的樹(shù)狀作為密鑰),則整個(gè)加密解密的過(guò)程描述如圖5.13所示。(1)生成密鑰:由信息的發(fā)送和接收雙方各提供一種二叉樹(shù)的遍歷序列,如前序遍歷和中序遍歷序列,分別為1、2、4、7、3、5、8、6、9和4、7、2、1、5、8、3、9、6,構(gòu)成如圖5.14所示的二叉樹(shù)。對(duì)其中的任何一個(gè)結(jié)點(diǎn),若其有左孩子,則將其指向左孩子的分支編碼為0；若有右孩子,則將其指向右孩子的分支編碼為1,一直進(jìn)行下去,直到編碼結(jié)束,由此二叉樹(shù)構(gòu)成密鑰。（2)信息加密:對(duì)明文用二叉樹(shù)進(jìn)行編碼,從根結(jié)點(diǎn)開(kāi)始,取明文的第1位(1,對(duì)應(yīng)根結(jié)點(diǎn)的右分支)右轉(zhuǎn),到結(jié)點(diǎn)3;取明文的第2位(0,對(duì)應(yīng)3這個(gè)結(jié)點(diǎn)的左分支）左轉(zhuǎn),到結(jié)點(diǎn)5;取明文的第3位（0）由于結(jié)點(diǎn)5無(wú)左分支,故明文的前兩位(10)的最終編碼的二叉樹(shù)為5。接著從根結(jié)點(diǎn)開(kāi)始,取明文的第3位（0,對(duì)應(yīng)根結(jié)點(diǎn)的左分支)左轉(zhuǎn),到結(jié)點(diǎn)2;取明文的第4位(1),由于結(jié)點(diǎn)2無(wú)右分支,故明文的第3位的最終編碼為2。依此類推,一直到編碼結(jié)束,得到最終編碼為52875,將其轉(zhuǎn)換為二進(jìn)制序列為(01010010100001110101),這就是密文。3)信息解密:接收方收到二進(jìn)制序列01010010100001110101),按每四位一組轉(zhuǎn)換為十進(jìn)制串52875)。根據(jù)二叉樹(shù)對(duì)該十進(jìn)制數(shù)串進(jìn)行編碼,在給定的圖5.14的二叉樹(shù)中,5的編碼為(10)、2的編碼為(0)、8的編碼為(101)、7的編碼為(001)、5的編碼為(10),組合起來(lái)的編碼為10010100110,至此,解密結(jié)束。5.4線索二叉樹(shù)對(duì)任何一種數(shù)據(jù)結(jié)構(gòu),經(jīng)常涉及到取前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的運(yùn)算,對(duì)線性結(jié)構(gòu)而言,由于其邏輯關(guān)系是順序的,故其運(yùn)算很容易,但對(duì)非線性結(jié)構(gòu)并非易事。從上一節(jié)二叉樹(shù)的遍歷過(guò)程可知,二叉樹(shù)的遍歷實(shí)際上就是把非線性結(jié)構(gòu)變?yōu)榫€性結(jié)構(gòu)的過(guò)程,但這些信息只能在動(dòng)態(tài)遍歷時(shí)體現(xiàn),如何保留結(jié)點(diǎn)在某種遍歷中的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的信息呢?一種簡(jiǎn)單的方法是另外增加一個(gè)線性表,存儲(chǔ)遍歷后的序列,但這需要額外地存儲(chǔ)開(kāi)銷。實(shí)際上,具有n個(gè)結(jié)點(diǎn)的二叉樹(shù),其二叉鏈表中共有2n個(gè)指針域。由于除根結(jié)點(diǎn)外,對(duì)于每個(gè)結(jié)點(diǎn)都有一個(gè)指針指向該結(jié)點(diǎn),因此實(shí)際只有n-1個(gè)指針域被使用,而另外n+1個(gè)指針域是空的,可以利用這n+1個(gè)空指針存放某種遍歷方式下指向前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針,這種附加的指針?lè)Q為"線索",加上了線索的二叉樹(shù)稱為線索二叉樹(shù),把加上線索的過(guò)程稱為二叉樹(shù)的線索化。根據(jù)二叉樹(shù)的不同遍歷方法,可以分為前序線索二叉樹(shù)、中序線索二叉樹(shù)和后序線索二叉樹(shù)3種。5.4.1線索二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)為了區(qū)分線索二叉樹(shù)的指針與線索,需要在每個(gè)結(jié)點(diǎn)中增加兩個(gè)標(biāo)志位Lflag和Rflag,令:0Lflag是指針,指向結(jié)點(diǎn)的左孩子結(jié)點(diǎn)Lflag=1Lflag是線索,指向結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)0Rflag是指針,指向結(jié)點(diǎn)的右孩子結(jié)點(diǎn)Rflag=1Rflag是線索,指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)增加了標(biāo)志域的二叉樹(shù)結(jié)構(gòu)如圖5.15所示。這時(shí),線索二叉樹(shù)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)調(diào)整為:struetbtnode{ETData;int

Lflag,Rflagz;structbtnode*Lchild;

struct

btnode*Rchild;};對(duì)于同一棵二叉樹(shù),遍歷的方法不同,得到的線索二叉樹(shù)也不同。如圖5.16所示為一棵二叉樹(shù)相應(yīng)的前序、中序和后序線索樹(shù)。5.4.2二叉樹(shù)的線索化由圖5.13可知,為了將一棵二叉樹(shù)線索化,只需在按某種遍歷方法(這里以中序?yàn)槔?線索化時(shí),將訪問(wèn)子樹(shù)的根結(jié)點(diǎn)用以下操作來(lái)代替：(1)若上次訪問(wèn)到的結(jié)點(diǎn)的右指針為空,則將其指向當(dāng)前結(jié)點(diǎn),并置右標(biāo)志域?yàn)?;(2)若當(dāng)前訪問(wèn)到的結(jié)點(diǎn)的左指針為空,則將其指向上次訪問(wèn)到的結(jié)點(diǎn),并置左標(biāo)志域?yàn)?。5.4.3線索二叉樹(shù)的遍歷對(duì)二叉樹(shù)進(jìn)行線索化后,如果需要再次遍歷,只要根據(jù)遍歷序列的線索進(jìn)行即可,這里仍以中序線索二叉樹(shù)為例進(jìn)行說(shuō)明:首先,從二叉樹(shù)的根結(jié)點(diǎn)開(kāi)始,沿左子樹(shù)找下去,一直找到左標(biāo)志域?yàn)?的結(jié)點(diǎn)(即葉子結(jié)點(diǎn),也是線索化的第一個(gè)結(jié)點(diǎn))。接著從該結(jié)點(diǎn)開(kāi)始,依次查找中序序列的后繼結(jié)點(diǎn),其規(guī)則如下:(1)若當(dāng)前結(jié)點(diǎn)的右標(biāo)志域?yàn)?,說(shuō)明指針是線索,則順序訪問(wèn)線索所指向的下一個(gè)結(jié)點(diǎn);(2)若當(dāng)前結(jié)點(diǎn)的右標(biāo)志域?yàn)?,說(shuō)明指針是分支,則沿右子樹(shù)的左指針進(jìn)行搜索,一直找到左標(biāo)志域?yàn)?且左指針值不為空為止,該結(jié)點(diǎn)即為當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)。線索二叉樹(shù)的遍歷是一種非遞歸算法,它不涉及堆棧的進(jìn)棧與出棧操作,因而比遞歸算法節(jié)省內(nèi)存空間,同時(shí)其時(shí)間復(fù)雜度與樹(shù)的深度相關(guān)。對(duì)含n個(gè)結(jié)點(diǎn)的二叉樹(shù),在最壞情況下,時(shí)間復(fù)雜度為0(n)。

5.5樹(shù)和森林主要討論樹(shù)的存儲(chǔ)結(jié)構(gòu)以及樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換關(guān)系5.5.1樹(shù)的存儲(chǔ)結(jié)構(gòu)在實(shí)際應(yīng)用中,人們?cè)褂煤芏喾N存儲(chǔ)結(jié)構(gòu)來(lái)表達(dá)一棵樹(shù),這里介紹幾種常用的存儲(chǔ)方法。1.雙親表示法在樹(shù)中,每個(gè)結(jié)點(diǎn)的雙親是唯一的。利用這一性質(zhì),在存儲(chǔ)每一結(jié)點(diǎn)信息的同時(shí)存儲(chǔ)其雙親結(jié)點(diǎn)的信息,這可以用指針等動(dòng)態(tài)鏈表的方式實(shí)現(xiàn),但用順序表來(lái)存儲(chǔ)更方便,通常的做法是:開(kāi)辟一塊連續(xù)的存儲(chǔ)空間（例如數(shù)組）存儲(chǔ)結(jié)點(diǎn)信息,其中每個(gè)存儲(chǔ)單元的結(jié)構(gòu)形式如圖5.17所示。這種結(jié)構(gòu)中,雙親域用來(lái)存儲(chǔ)雙親結(jié)點(diǎn)在數(shù)組中的位的存儲(chǔ)結(jié)構(gòu)置。這樣結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)用C語(yǔ)言描述如下：#defineMAX100//樹(shù)中結(jié)點(diǎn)的最大值TypedefstruetTnode{ETdata；

intparent；}Tnode;這樣,一棵樹(shù)可以定義為:typedefstruet{

TNode

tree[MAX];

int

TreeNodeNUIEber;//結(jié)點(diǎn)數(shù)}ParentTree;根據(jù)定義,一棵樹(shù)用MAX個(gè)上述結(jié)點(diǎn)的一維數(shù)組來(lái)表示,如圖5.18所示。由于這種方法利用了樹(shù)中每個(gè)結(jié)點(diǎn)(根結(jié)點(diǎn)除外)只有一個(gè)雙親結(jié)點(diǎn)的性質(zhì),因此查找某個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)非常容易。依照此方法,也較容易找到樹(shù)根,但是要訪問(wèn)某個(gè)葉子結(jié)點(diǎn)則要遍歷整個(gè)向量數(shù)組。2.孩子表示法由于樹(shù)中的每個(gè)結(jié)點(diǎn)具有多個(gè)孩子結(jié)點(diǎn),因此可以利用多重鏈表的存儲(chǔ)方式,使每個(gè)結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)域和多個(gè)指向孩子結(jié)點(diǎn)的指針域,通常把這種方法稱為多重鏈表法。這時(shí)鏈表中的結(jié)點(diǎn)可以有如圖5.19所示兩種結(jié)點(diǎn)格式。在第1種格式中,多重鏈表的結(jié)點(diǎn)是同構(gòu)的,即每個(gè)結(jié)點(diǎn)的指針域的個(gè)數(shù)等于該樹(shù)的度d,利用這種存儲(chǔ)方法有利于對(duì)樹(shù)完成各種操作,但會(huì)造成許多空鏈域,形成空間的浪費(fèi),不難計(jì)算,如果樹(shù)的度為d,結(jié)點(diǎn)的個(gè)數(shù)為n,則空鏈域的個(gè)數(shù)為nd-n+l=n(d-1)+1。而且也不利于樹(shù)的擴(kuò)展(如無(wú)法在該樹(shù)中某結(jié)點(diǎn)處插入一個(gè)度大于d的子樹(shù))。第2種格式中的結(jié)點(diǎn)是不同構(gòu)的,每個(gè)結(jié)點(diǎn)的度degree等于每個(gè)結(jié)點(diǎn)指針域的個(gè)數(shù),這種方法雖然能節(jié)省存儲(chǔ)空間,但對(duì)樹(shù)的操作很不方便,故很少采用這種格式。使用第1種格式時(shí),樹(shù)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)用C語(yǔ)言描述如下:typedefstructnode{ETdata;struetnode*Son[M];//M為樹(shù)的度}JD;其中,圖5.18中的樹(shù)用多重鏈表法表示如圖5.20所示:另外一種方法是將樹(shù)中每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)用單鏈表連接起來(lái),形成孩子鏈表。這樣n個(gè)結(jié)點(diǎn)就有n個(gè)孩子鏈表,而n個(gè)結(jié)點(diǎn)的數(shù)據(jù)和n個(gè)孩子鏈表的頭指針又組成一個(gè)順序表,該順序表可用一維數(shù)組表示,數(shù)組中的每個(gè)元素包含數(shù)據(jù)域data和指向孩子結(jié)點(diǎn)的指針。其數(shù)據(jù)結(jié)構(gòu)用C語(yǔ)言描述如下:typedefstructCTnode{//此結(jié)構(gòu)用于定義孩子結(jié)點(diǎn)

intchild；//孩子結(jié)點(diǎn)在順序表中的序號(hào)

structnode*next;//指向下一個(gè)孩子結(jié)點(diǎn)的指針}ChildPoint;typedefstruet{//此結(jié)構(gòu)用于定義順序表的每個(gè)元素ETdata;//樹(shù)結(jié)點(diǎn)中的數(shù)據(jù)域

childpoint

*FirstChilds//孩子鏈表的頭指針}HeadNode;

typedefstruet{Headnodenodes[MAXCOUNT];

intNodeCounts;//樹(shù)中的結(jié)點(diǎn)數(shù)

intRoot;//各子樹(shù)根結(jié)點(diǎn)在順序表中的序號(hào)}CTree;圖5.18中的樹(shù)用孩子表示法表示如圖5.21所示圖5.12數(shù)的孩子表示法孩子表示法比較適合有關(guān)孩子結(jié)點(diǎn)的操作,卻不適用于訪問(wèn)其雙親結(jié)點(diǎn)。為此,可以在順序表的每個(gè)元素中增加一個(gè)數(shù)據(jù)域,用于存放雙親結(jié)點(diǎn)的位置,其相應(yīng)的數(shù)據(jù)結(jié)構(gòu)調(diào)整為:typedefstruet{//此結(jié)構(gòu)用于定義順序表的每個(gè)元素ETdata;//樹(shù)結(jié)點(diǎn)中的數(shù)據(jù)域

intParent;//雙親結(jié)點(diǎn)在順序表中的序號(hào)ChildPoint*FirstChild;//孩子鏈表的頭指針}HeadNode;這種表示法稱為雙親孩子表示法,這時(shí)圖5.18用雙親孩子表示法表示如圖5.22所示。3.孩子兄弟表示法表達(dá)樹(shù)的結(jié)點(diǎn)時(shí),除表示其數(shù)據(jù)域外,另外還可以增加兩個(gè)指針域:一個(gè)指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn),另一個(gè)指向該結(jié)點(diǎn)的下一個(gè)兄弟結(jié)點(diǎn),把樹(shù)的這種存儲(chǔ)方法稱為孩子兄弟表示法。由于這種存儲(chǔ)方法實(shí)質(zhì)上是用一棵二叉樹(shù)來(lái)存儲(chǔ)樹(shù)的結(jié)構(gòu),因此又稱為二叉樹(shù)表示法或二叉鏈表表示法。這時(shí)每個(gè)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)用C語(yǔ)言表示如下:typedefstructCSnode{ET

data;structCSNode*firstchild,*nextsibling;}其中,指針firstchild和nextsibling分別指向第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。這種表示法適合對(duì)樹(shù)進(jìn)行各種操作,如遍歷整棵樹(shù)查找某個(gè)結(jié)點(diǎn)的第n個(gè)孩子、查找兄弟結(jié)點(diǎn)等,但它也同時(shí)破壞了原來(lái)樹(shù)的層次。例如對(duì)圖5.18,其孩子兄弟表示法如圖5.23所示5.52樹(shù)、森林和二叉樹(shù)的相互轉(zhuǎn)換通過(guò)前面樹(shù)的孩子兄弟表示法知,樹(shù)和二叉樹(shù)之間是可以相互轉(zhuǎn)換的。即給定一棵樹(shù),可以找到唯一的一棵二叉樹(shù)與之對(duì)應(yīng),從物理結(jié)構(gòu)來(lái)看,它們都用二叉鏈表來(lái)表示,只是邏輯含義不同而已。本節(jié)主要討論樹(shù)、森林和二叉樹(shù)三者之間的相互轉(zhuǎn)換方法1.樹(shù)轉(zhuǎn)換為二叉樹(shù)對(duì)于一棵二叉樹(shù),其左右孩子是有區(qū)別的。而對(duì)于一棵無(wú)序樹(shù),樹(shù)中結(jié)點(diǎn)的各孩子是無(wú)序的,為便于二者之間轉(zhuǎn)換,特作如下約定：樹(shù)中每一個(gè)結(jié)點(diǎn)的孩子按從左到右的次序順序編號(hào),這樣一棵無(wú)序樹(shù)便成為有序樹(shù)。將一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)的方法為:(1)加線將樹(shù)中所有相鄰兄弟之間加一條連線。(2)刪線對(duì)樹(shù)中的每個(gè)結(jié)點(diǎn),只保留其與第一個(gè)孩子結(jié)點(diǎn)之間的連線,刪除其與其他孩子結(jié)點(diǎn)之間的連線。(3)旋轉(zhuǎn)以樹(shù)的根結(jié)點(diǎn)為軸,將整棵樹(shù)順時(shí)針旋轉(zhuǎn)一定的角度,使之層次分明。其轉(zhuǎn)換過(guò)程如圖5.24所示由上述轉(zhuǎn)換過(guò)程知:樹(shù)中某結(jié)點(diǎn)的第一個(gè)孩子轉(zhuǎn)換為相應(yīng)二叉樹(shù)中該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)。而樹(shù)中原來(lái)的兄弟結(jié)點(diǎn),在二叉樹(shù)中后一個(gè)孩子結(jié)點(diǎn)成為前一個(gè)孩子結(jié)點(diǎn)的右孩子結(jié)點(diǎn),而且轉(zhuǎn)換后的二叉樹(shù)的根結(jié)點(diǎn)沒(méi)有右子樹(shù)。反之,一棵根結(jié)點(diǎn)沒(méi)有右子樹(shù)的二叉樹(shù)在邏輯上也很容易轉(zhuǎn)換為一棵樹(shù)。2.森林轉(zhuǎn)換為二叉樹(shù)由前面森林的定義知,森林是樹(shù)的集合。一棵樹(shù)可以用孩子兄弟法轉(zhuǎn)換為一棵二叉樹(shù),這種二叉樹(shù)的根結(jié)點(diǎn)是沒(méi)有右孩子的,如果把森林中第二棵樹(shù)的根結(jié)點(diǎn)看成是第一棵樹(shù)的根結(jié)點(diǎn)的兄弟,則可以完成從森林到二叉樹(shù)的轉(zhuǎn)換,其具體步驟為:(1)轉(zhuǎn)換將森林中的每棵樹(shù)轉(zhuǎn)換為相應(yīng)的二叉樹(shù)。(2)連接第一棵二叉樹(shù)不動(dòng),從第二棵二叉樹(shù)開(kāi)始,依次把后一棵二叉樹(shù)的根結(jié)點(diǎn)作為前一棵二叉樹(shù)的根結(jié)點(diǎn)的右孩子,直到所有的二叉樹(shù)連接在一起,即完成森林向二叉樹(shù)的轉(zhuǎn)換。(3)旋轉(zhuǎn)以根結(jié)點(diǎn)為軸,將整棵樹(shù)按順時(shí)針旋轉(zhuǎn)一定的角度,得到一棵層次分明的二叉樹(shù)。圖5.25以示例的形式給出了整個(gè)轉(zhuǎn)換過(guò)程。圖5.25將森林轉(zhuǎn)換為二叉樹(shù)3.二叉樹(shù)還原為樹(shù)或森林由前面內(nèi)容知,樹(shù)和森林都可轉(zhuǎn)換為二叉樹(shù),所不同的是:由樹(shù)轉(zhuǎn)換的二叉樹(shù)根結(jié)點(diǎn)無(wú)右孩子,而由森林轉(zhuǎn)換的二叉樹(shù)有右孩子。作為其逆過(guò)程,也可由一棵二叉樹(shù)還原為樹(shù)或森林,具體方法如下:(1)連線若某結(jié)點(diǎn)是其雙親的左孩子,則把該結(jié)點(diǎn)的右孩子、右孩子的右孩子……都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線連接起來(lái)。(2)刪線刪除原二叉樹(shù)中所有雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線。(3)調(diào)整調(diào)整由上兩步得到的樹(shù)或森林,使之層次分明圖5.26給出了將一棵二叉樹(shù)還原為森林的示例。圖5.26二叉樹(shù)轉(zhuǎn)換為森林例設(shè)森林F中有5棵樹(shù),每棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為n1、n2、n3、n4、n5當(dāng)把森林F