吉林大學內(nèi)部絕密資料 第四章 樹課件

第四章樹樹的基本概念二叉樹(BinaryTree)線索化二叉樹(ThreadedBinaryTree)樹與森林(Tree&Forest)壓縮與哈夫曼樹(HuffmanTree)

樹結(jié)構(gòu)在客觀世界中是大量存在的，例如家譜、行政組織機構(gòu)都可用樹形象地表示。樹在計算機領(lǐng)域中也有著廣泛的應(yīng)用，例如在編譯程序中，用樹來表示源程序的語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)中，可用樹來組織信息；在分析算法的行為時，可用樹來描述其執(zhí)行過程。例1[Joe的后代] 下圖給出了Joe的后代，并按層次方式組織，其中Joe在最頂層。Joe的孩子（Ann，Mary和John）列在下一層，在父母和孩子間有一條邊。在層次表示中，非常容易地找到Ann的兄弟姐妹，Joe的后代，Chris的祖先等。例2[軟件工程] 下面考察另一種層次數(shù)據(jù)——軟件工程中的模塊化技術(shù)。通過模塊化，可以把大的復(fù)雜的任務(wù)分成一組小的不太復(fù)雜的任務(wù)。模塊化的目標是把軟件系統(tǒng)分成許多功能不相關(guān)的部分或模塊以便于進行相對獨立的開發(fā)。由于解決幾個小問題比解決大問題更容易一些，因此模塊化方法可以縮短整個軟件的開發(fā)時間。另外，不同的程序員可以同時開發(fā)不同的模塊。如果有必要，每個模塊可以再細分，下圖給出了某文字處理器的一種可行的模塊分解圖。文字處理器的模塊層次結(jié)構(gòu)定義4.1.1一個樹（或樹形）就是一個有限非空的結(jié)點集合T，其中：有一個特別標出的被稱為該樹（或樹形）之根root(T)的結(jié)點；其余結(jié)點（根除外）被分成m0個不相交的集合T1，T2，…，Tm，且T1，T2，…，Tm又都是樹（或樹形）。樹（或樹形）T1，T2，…，Tm被稱作root(T)的子樹（或子樹形）。有序樹：樹中結(jié)點的各個子樹

從左至右有序。無序樹：樹中結(jié)點的各個子樹

從左至右無序。定義4.1.2樹是包含n(n≥1)個結(jié)點且滿足如下條件的有限集合(非遞歸定義)：存在一個唯一的結(jié)點v0，它沒有前驅(qū)結(jié)點，稱為樹的根（或根結(jié)點）；任何非根結(jié)點都有且僅有一個前驅(qū)結(jié)點，稱為該結(jié)點的父結(jié)點；任何結(jié)點都可能有多個（

n1）后繼結(jié)點，稱之為該結(jié)點的子結(jié)點；若某結(jié)點沒有后繼結(jié)點，則稱之為葉結(jié)點。任一非根結(jié)點vk都有且僅有一條從v0到該結(jié)點的結(jié)點序列（或曰路徑）v0

v1

…

vk，其中vi是vi1（1

i

k）基本術(shù)語結(jié)點:數(shù)據(jù)元素+若干指向子樹的分支結(jié)點的度:一個結(jié)點的子結(jié)點的數(shù)目(分支的個數(shù))樹的度:樹中所有結(jié)點的度的最大值葉子結(jié)點:度為零的結(jié)點分支結(jié)點:度大于零的結(jié)點結(jié)點的層次:假設(shè)根結(jié)點的層次為0,第l層的結(jié)點的子樹根結(jié)點的層次為l+1A的層數(shù)為0B、C、D的層數(shù)為1E、G、H、I的層數(shù)為2F的層數(shù)為3從A到F的路徑為A-B-E-F，路徑長度為3。樹的高度為3AECDBIHGF層次0層次1層次2層次3圖6.1樹

樹的表示

1.集合嵌套表示法2.凹入表示法3.廣義表表示法4.樹形表示法ACBDE1ABCDE2ABCDE4A(B,C(D,E))3二叉樹

(BinaryTree)二叉樹的主要性質(zhì)和定義●定義：二叉樹是結(jié)點的有限集合，它必須滿足 下面的一個條件： （1）它是空集。 （2）它由一個根結(jié)點,根結(jié)點的左右子樹構(gòu) 成，且其左右子樹滿足二叉樹定義。

●

二叉樹的特征

①二叉樹每個結(jié)點的最多有2個子結(jié)點；

②二叉樹的子樹有左右之分。二叉樹的五種不同形態(tài)二度樹是否是二叉樹？嚴格說來，二度樹和二叉樹是不同的。

當二度樹中某結(jié)點含有一個子結(jié)點時，無左右之分。二叉樹可以是空二叉樹，但通常規(guī)定樹不能為空。二叉樹的性質(zhì)引理4.2.1二叉樹中層數(shù)為i的結(jié)點至多有2i個，i≧0。證明：用數(shù)學歸納法。當i=0

時，僅有一個根結(jié)點，其層數(shù)為0，因此i=0時引理成立。假定當i=j(j≥0)時，引理成立，即第j層上至多有2j個結(jié)點。對于二叉樹的任意結(jié)點，其子結(jié)點個數(shù)最大為2，故第j+1層上至多有2*2j=2j+1

個結(jié)點，因此當i=j+1時，引理成立。由數(shù)學歸納法可知，對于所有的i≥0，均有“第i層上至多有2i個結(jié)點”。證畢。引理4.2.3

設(shè)T是由n個結(jié)點構(gòu)成的二叉樹，其中,葉子結(jié)點個數(shù)為n0，度為2的結(jié)點個數(shù)為n2，則有：n0＝n2＋1證明：若設(shè)度為1的結(jié)點有n1個，總結(jié)點個數(shù)為n，總邊數(shù)為e，則n=n0+n1+n2

e=n–1

(子結(jié)點與父結(jié)點的連接)e=2n2+n1

(所有發(fā)出分支的結(jié)點)因此，有2n2+n1=n0+n1

+n2-1

n2=n0-1n0=n2+1

滿二叉樹的定義：一棵高度為k的滿二叉樹，是具有

2k+1－1個結(jié)點且高度為k

的二叉樹(最多節(jié)點數(shù)目)?？砂磳哟雾樞颍窗磸牡?層到第k層，每層由左向右的次序）將一棵滿二叉樹的所有結(jié)點用自然數(shù)從1開始編號。564372981013111214151

完全二叉樹的定義：

是一棵具有n個結(jié)點，高度為k的二叉樹，且樹中所有結(jié)點對應(yīng)高度為k的滿二叉樹中編號由1至n的那些結(jié)點。56437298101性質(zhì)6如果將一棵有n個結(jié)點的完全二叉樹自頂向下，同一層自左向右連續(xù)給結(jié)點編號0,1,2,…,n-1，然后按此結(jié)點編號將樹中各結(jié)點順序地存放于一個一維數(shù)組中,并簡稱編號為i的結(jié)點為結(jié)點i(0

i

n-1。則有以下關(guān)系：

若i==0,則i無雙親若i>0,則i的雙親為(i-1)/2

若2*i+1<n,則i的左子節(jié)點為2*i+1

若2*i+2<n,則i的右子節(jié)點為2*i+2

若i為偶數(shù),且i!=0,則其左兄弟為i-1

若i為奇數(shù),且i!=n-1,則其右兄弟為i+1

i所在層次為log2(i+1)

用歸納法證明

若i=1，如果n≥2，則左孩子的編號顯然為2.假定對所有滿足(1≤j≤i,2i≤n)的j，j的左孩子編號為2j.那么對于結(jié)點i+1，我們證明其左孩子編號為

2（i+1）.如果2（i+1）≤n，則由層次次序得知，i+1的左孩子之前的兩個結(jié)點就是i的左孩子和右孩子，因為i的左孩子編號為2i（歸納假設(shè)），故i的右孩子編號為2i+1，從而i+1的左孩子編號為2i+2=2(i+1).證畢。引理4.2.5n個結(jié)點的完全二叉樹的高度是

log2n

.證明：設(shè)二叉樹高度為k，由定義4.2.3知，完全二叉樹的結(jié)點個數(shù)介于高度為k-1和高度為k的滿二叉樹的結(jié)點數(shù)之間，即有：

2k-1<n≤2k+1-1從而有2k≤n<2k+1，即k≤log2n<k+1，因為k為整數(shù)，故有k=

log2n

.證畢。請注意:

當根結(jié)點的層數(shù)從1計時，樹的高度為

log2n」+1

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

A[0]A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]A[9]94176612523627049313123126694175706249

●

一般二叉樹的順序存儲CBA2465731a[0]a[1]a[2]a[3]a[4]A

B

Ca[5]a[6]二叉樹順序存儲演示2可能會浪費很多存儲空間，單支樹就是一個極端情況。

2·

鏈式存儲結(jié)構(gòu)二叉樹諸結(jié)點被隨機存放在內(nèi)存空間中，結(jié)點之間的關(guān)系用指針說明。

二叉樹的結(jié)點結(jié)構(gòu)

二叉樹結(jié)點應(yīng)包含三個域：數(shù)據(jù)域data、指針域left（稱為左指針）和指針域right（稱為右指針），其中左、右指針分別指向該結(jié)點的左、右子樹的根結(jié)點.leftright

data

二叉樹鏈式存儲結(jié)構(gòu)ADCBEFG∧∧∧∧∧∧∧∧ACBEFDG問題：如何找到父親節(jié)點？

(1)搜索二叉樹中符合數(shù)據(jù)域條件的結(jié)點算法Find(t,item.q)/*在二叉樹T中搜索Data域之值為item的結(jié)點，指針t指向T之根，指針q指向欲搜索的結(jié)點*/Find1.[t

?]IF

t

THEN(q

.

RETURN.).IF

Data(t)

item

THEN(q

t

.

RETURN.

).Find2.[遞歸]Find(Left(t),item

.

p).IF

p

THEN(q

p.

RETURN.).Find(Right(t),item

.q).RETURN.?

(2)從二叉樹中刪除給定結(jié)點及其左右子樹算法DST(t)/*root指向一棵二叉樹T之根，本算法從T中刪除給定結(jié)點t

(是簡稱，其含義是：t是指向該結(jié)點的指針)及其左右子樹；DST是DelSubTree之縮寫*/DST1.[t

?]IF

t

THEN

RETURN.DST2.[t

root?]IF

t

root

THEN(Del(t).

root

.RETURN.

)DST3.[找t的父結(jié)點q]p

t

.Father(root,p.q).DST4.[修改q的指針域]IF

Left(q)

p

THEN

Left(q)

.IF

Right(q)

p

THEN

Right(q)

.DST5.[刪除p及其子樹]Del(p).?算法Del(p)/*刪除結(jié)點p及其左右子樹*/Del1.[p

?]IF

p

THENRETURN.Del2.[遞歸刪除]Del(Left(p)).

Del(Right(p)).

AVAIL

p

.?

(3)

搜索父結(jié)點算法Father(t,p.q)/*指針t指向二叉樹T之根，在T中搜索給定結(jié)點p之父結(jié)點；q指向p之父結(jié)點；本算法使用了遞歸*/Father1.[t

?]IF

t

THEN(q

.RETURN.)Father2.[t為所求?]IF

Left(t)

p

OR

Right(t)

p

THEN(q

t.

RETURN.)Father3.[遞歸]Father(Left(t),p.qL).IF

qL

THEN(q

qL

.RETURN.)ELSE(Father(Right(t),p

.

qR).q

qR

.RETURN.)?問題：如何提高執(zhí)行效率？三叉鏈表表示法

Leftdataparentright

4.2.4二叉樹的遍歷

●二叉樹的遍歷：按照一定次序訪問樹中所有結(jié)點，并且每個結(jié)點的值僅被訪問一次的過程。先根（中根、后根）序遍歷次序是樹中結(jié)點的一個有序序列，稱為二叉樹的先根（中根、后根）序列。遍歷方式先根序列：DLR中根序列：LDR后根序列：LRDLDR先根序遍歷中根序遍歷后根序遍歷步驟一訪問根遍歷左子樹遍歷左子樹步驟二遍歷左子樹訪問根遍歷右子樹步驟三遍歷右子樹遍歷右子樹訪問根中根遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則中根遍歷左子樹(L)；訪問根結(jié)點(V)；中根遍歷右子樹(R)。遍歷結(jié)果

a+b*c-d-e/f中根遍歷(InorderTraversal，中序遍歷)表達式語法樹二叉樹遞歸的中根遍歷算法

算法Inorder（t）IN1[遞歸遍歷]IFt≠NULLTHEN（ Inorder（left（t））. PRINT（data（t））. Inorder（right（t））.）

▌

二叉樹的中根遍歷演示先根遍歷(PreorderTraversal，前/先序遍歷)先根遍歷二叉樹算法的框架是若二叉樹為空，則空操作；否則訪問根結(jié)點(V)；先根遍歷左子樹(L)；先根遍歷右子樹(R)。遍歷結(jié)果-+a*b

-

cd/ef二叉樹遞歸的先根遍歷算法

算法Preorder（t）Preorder1[遞歸遍歷]IFt≠NULLTHEN（PRINT（data（t））.

Preorder（left（t））.

Preorder（right（t））.）

▌

二叉樹的先根遍歷演示后根遍歷(PostorderTraversal，后序遍歷)后根遍歷二叉樹算法的框架是若二叉樹為空，則空操作；否則后根遍歷左子樹(L)；后根遍歷右子樹(R)；訪問根結(jié)點(V)。遍歷結(jié)果abcd

-*+ef/-二叉樹遞歸的后根遍歷算法

算法Postorder（t）Postorder1[遞歸遍歷]IFt≠NULLTHEN（

Postorder

（left（t））.

Postorder

（right（t））.

PRINT（data（t））.）

▌

先根序得到的結(jié)點序列：中根序得到的結(jié)點序列：后根序得到的結(jié)點序列：ABCDEFA+BCDE+FAB+CDEF+分別對應(yīng)表達式的前綴、中綴和后綴表示法（其中，中綴表示還需要括號和優(yōu)先級，稍有差別）。非遞歸中根遍歷算法算法NIO(t)/*設(shè)t是指向與圖4.2.7(b)中之表示相同的一棵二叉樹T

的根的指針，本算法利用一個輔助堆棧S以中根序訪問T

的所有結(jié)點；NIO是NorecInOrder之縮寫*/NIO1.[初始化] CREATE(S).

p

t

. /*操作CREATE(S)系指創(chuàng)建一個空堆棧S*/NIO2.[入棧] WHILE

p

DO (S

p

.

p

Left(p).)NIO3.[棧為空?] IF

S為空THENRETURN. ELSE

p

S

.NIO4.[訪問p，更新p] PRINT(Data(p)).

p

Right(p)./*這里用PRINT代替訪問*/NIO5.[返回] GOTO

NIO2

.?非遞歸中根遍歷算法算法NIO(t)/*設(shè)t是指向與圖4.2.7(b)中之表示相同的一棵二叉樹T

的根的指針，本算法利用一個輔助堆棧S以中根序訪問T

的所有結(jié)點；NIO是NorecInOrder之縮寫*/NIO1.[初始化] CREATE(S).

p

t

. /*操作CREATE(S)系指創(chuàng)建一個空堆棧S*/NIO2.[入棧] WHILE

p

DO (S

p

.

p

Left(p).)NIO3.[棧為空?] IF

S為空THENRETURN. ELSE

p

S

.NIO4.[訪問p，更新p] PRINT(Data(p)).

p

Right(p)./*這里用PRINT代替訪問*/NIO5.[返回] GOTO

NIO2

.?非遞歸的后根遍歷算法為記憶走過的結(jié)點，設(shè)置一個工作棧：i=0,1或2，表示結(jié)點所處的三種狀態(tài)：沒有訪問結(jié)點遍歷完左子樹遍歷完右子樹。結(jié)點退棧次數(shù)

i

后序遍歷時，每遇到一個結(jié)點，先把它推入棧中，讓

i=0。在遍歷其左子樹前，改結(jié)點的i=1，將其左子結(jié)點壓入棧中。在遍歷完左子樹后，還不能訪問該結(jié)點，必須繼續(xù)遍歷右子樹，此時該結(jié)點的i=2，并把其右子女推入棧中。在遍歷完右子樹后，結(jié)點才退棧訪問。

算法postorder(t)CREATS(S).S(t,0).WHILENOT(StackEmpty(S))DO((P,i)S.IFP≠NULLTHEN(IFi=0TEHN(S(P,1).S(left(P),0).).IFi=1THEN(S(P,2).S(right(P),0).IFi=2THENPRINT(data(P))))▌層次遍歷按層數(shù)由小到大，同層由左向右的次序訪問結(jié)點。遍歷結(jié)果:

ABECFDABDFCE若訪問第i層上的所有結(jié)點，必須知道該層上所有結(jié)點的地址，地址是保存在其父結(jié)點的left和right指針中的。 用一個隊列來實現(xiàn)。實現(xiàn)：

通過觀察發(fā)現(xiàn)，在第i層上若結(jié)點x在結(jié)點y的左邊，則x一定在y之前被訪問。同理，在第i+1層上，x的子結(jié)點一定在y的子結(jié)點之前被訪問。二叉樹層次遍歷算法需要一個輔助隊列，具體方法如下：根結(jié)點入隊.重復(fù)本步驟直至隊為空:

若隊非空，取隊頭結(jié)點并訪問；若其左指針不空，將其左孩子入隊，若其右指針不空，將其右孩子入隊.算法Lorder(t)CREATQ(Q).Qt.WHILENOT(QueueEmpty(Q))DO(PQ.IFP≠NULLTHEN(PRINT(data(P)).Qleft(P).Qright(P)))▌

ABDFCE先根遍歷序列：ABCDEF中根遍歷序列：BDCAFE后根遍歷序列：DCBFEA層次遍歷序列：ABECFD寫出遍歷順序：先根中根后根層次

由后根序列和中根序列可以唯一地確定一棵二叉樹。[例]后根序列CEFDBHGA

中根序列CBEDFAGH 后根序列CEFDBHGA

中根序列CBEDFAGHAC

B

E

DFGHABCDEFGHABCGDEHF

由先根序列和中根序列可以唯一地確定一棵二叉樹。[例]先根序列ABCKDEHF

中根序列BKCAHEDF4.2.5創(chuàng)建二叉樹唯一確定二叉樹先根序列不能唯一確定二叉樹之結(jié)構(gòu)在先根序列中加入特殊符號以示空指針位置ABD##E##C##

ACBED算法CBT(tostop.t)/*構(gòu)造以結(jié)點t為根的二叉樹；tostop

‘#’*/CBT1.[讀數(shù)據(jù)]READ(ch)./*讀入序列中的一個符號*/CBT2.[ch

tostop?]IF

ch

tostop

THEN(t

.RETURN

t

.)ELSE(t

AVAIL

.

Data(t)

ch

.)CBT3.[構(gòu)造左子樹]CBT(tostop

.

Left(t)).

CBT4.[構(gòu)造右子樹]CBT(tostop

.

Right(t)).

?

遍歷二叉樹的應(yīng)用——

4.2.6復(fù)制二叉樹

可以按先根遍歷、中根遍歷或后根遍歷的方式復(fù)制二叉樹。以后根遍歷為例進行復(fù)制。

復(fù)制過程：先復(fù)制子結(jié)點，再復(fù)制父結(jié)點，將 父結(jié)點與子結(jié)點連接起來。

算法CopyTree(t.p)/*t指向一棵二叉樹T的根，p指向T的復(fù)制品之根*/CopyTree1.[遞歸出口]

IF

t

THENRETURN

.CopyTree2.[復(fù)制左子樹]IFLeft(t)

THEN

CopyTree(Left(t).

newlptr)

ELSE

newlptr

.CopyTree3.[復(fù)制右子樹]IF

Right(t)

THEN

CopyTree(Right(t).newrptr)ELSE

newrptr

.CopyTree4.[生成結(jié)點]p

AVAIL.

Data(p)

Data(t).

Left(p)

newlptr.

Right(p)

newrptr.RETURN

p.?4.3

線索二叉樹以Left/Right鏈接表示的二叉樹結(jié)構(gòu)，可看作是有很多從根結(jié)點一直到葉結(jié)點的單鏈表組成的，一個結(jié)點的前驅(qū)結(jié)點是其父結(jié)點，一個結(jié)點的后繼結(jié)點是它的兒子結(jié)點這種結(jié)構(gòu)有兩方面不足：其一是從一個結(jié)點只能訪問它的兒子結(jié)點，而不能訪問它的父結(jié)點；其二是這種結(jié)構(gòu)通常包含很多未被有效使用的指針字段（或域），譬如包含i個結(jié)點的二叉樹，在其2i個指針域中僅有i-1個被使用.問題的提出：

通過遍歷二叉樹可得到結(jié)點的一個線性序列，在線性序列中，除第一個結(jié)點外，每個結(jié)點有且僅有一個前趨，除最后一個結(jié)點外，每個結(jié)點有且僅有一個后繼但是在二叉樹上只能找到結(jié)點的左孩子、右孩子，結(jié)點在線性序列中的前趨和后繼只有在遍歷過程中才能得到。

為了同結(jié)點在二叉樹中所具有的前驅(qū)（即父結(jié)點）和后繼（即子結(jié)點）區(qū)別開來，通常把序列中的結(jié)點的前驅(qū)或后繼冠以某種遍歷的名稱，如把中序序列中結(jié)點的前驅(qū)稱作中序前驅(qū)，結(jié)點的后繼稱作中序后繼。定義：在一棵有n個結(jié)點的二叉樹的中根序列T0T1…Ti-1TiTi＋1…Tn-2Tn-1中，Ti-1稱為Ti的中根前趨結(jié)點，Ti+1稱為Ti的中根后繼結(jié)點。其中，中根序列中的第一個結(jié)點T0的中根前趨為NULL，最后一個結(jié)點Tn-1的中根后繼為NULL。線索二叉樹的結(jié)點結(jié)構(gòu)：其中指示在某種遍歷次序下的前驅(qū)和后繼的

指針稱為線索；

加上線索的二叉樹稱為線索二叉樹；

對二叉樹以某種次序進行遍歷使其變?yōu)榫€索二叉樹的過程稱為線索化。

按中序遍歷得到的線索二叉樹稱為中序線索二叉樹；按先序遍歷得到的線索二叉樹稱為先序線索二叉樹；按后序遍歷得到的線索二叉樹稱為后序線索二叉樹；leftright

datapredsucc線索二叉樹演示ADBCErootrootADΛΛBΛΛΛCΛΛEΛpredpredpredpredsuccsuccsuccsuccsucc給出后序線索二叉樹ADBCErootrootADΛΛBΛΛΛCΛΛEΛpredpredpredpredsuccsuccsuccsuccsucc仍有很多空指針⑴將原指針域Pred和Succ分別改成存儲一個二進制位的域LThread和RThread.⑵若結(jié)點t有左孩子，則Left指向t的左孩子，且LThread的值為0；若t沒有左孩子，則

Left指向t的前驅(qū)結(jié)點，且LThread的值為1（此時稱Left為線索）.⑶若結(jié)點t有右孩子，則Right指向t的右孩子，且RThread的值為0；若t沒有右孩子，

則Right指向t的后繼結(jié)點，且RThread的值為1（此時稱Right為線索）.leftright

dataleftThreadrightThread改進leftright

dataleftThreadrightThreadleftThread=0,left域指示結(jié)點t的左孩子1,left域指示結(jié)點t的中根前驅(qū)rightThread=0,right域指示結(jié)點t的右孩子1,right域指示結(jié)點t的中根后繼A00B10C11D01E11∧∧中序線索二叉樹的存儲結(jié)構(gòu)ACBED[例]中序線索二叉樹。中根遍歷序列：

BCAEDA00B10C11D01E11∧∧中序線索二叉樹的存儲結(jié)構(gòu)ACBED[例]中序線索二叉樹。中根遍歷序列：

BCAED有兩個空指針CD改進

線索二叉樹的目的：在中序線索二叉樹中不需要對二叉樹進行遍歷可以方便的找到給定結(jié)點的中序前趨和中序后繼結(jié)點，并且不需要太多額外的空間。如何判斷葉結(jié)點？線索二叉樹中，一個結(jié)點是葉結(jié)點的充要條件為：左、右標志(LeftThread、RightThread)均是1。

查找中根序列的第一個和最后一個結(jié)點：從二叉樹根結(jié)點出發(fā)，沿左指針鏈往下查找，直至找到一個沒有左孩子的結(jié)點為止，它是中根遍歷順序下二叉樹中第一個被訪問的結(jié)點；從二叉樹根結(jié)點出發(fā)，沿右指針鏈往下查找，直至找到一個沒有右孩子的結(jié)點為止，它是中根遍歷順序下二叉樹中最后被訪問的結(jié)點查找中根序列的第一個結(jié)點：算法FIO(t

.

q

)/*t指向中序線索二叉樹T*之根，本算法返回T*的中根序列的首結(jié)點，并用q指向它*/FIO1.[初始化]

q

t.

FIO2.

[找中根遍歷順序下二叉樹中第一個被訪問的結(jié)點]WHILE

LThread(q)0DO

q

Left(q).RETURN

q.?WHILE

LThread(q)0DO

q

Left(q).A00B10C11D01E11∧∧中序線索二叉樹的存儲結(jié)構(gòu)WHILE

LThread(q)0DO

q

Left(q).A10D01E11∧∧查找中根序列的最后一個結(jié)點：算法LIO(

t.

q

)/*給定中序線索二叉樹T*，t指向T*之根，本算法返回T*的中根序列末結(jié)點，并用q指向它*/LIO1.[初始化]q

t

.LIO2.

[找中根遍歷順序下二叉樹中最后被訪問的結(jié)點]WHILE

RThread(q)0DO

q

Right(q).RETURN

q

.?WHILE

RThread(q)0DO

q

Right(q).A00B10C11D01E11∧∧(3)在線索二叉樹中搜索current的中根前趨結(jié)點算法思想:

對于結(jié)點current：若其leftThread=1（

current沒有左子結(jié)點），則left指向該結(jié)點的前趨結(jié)點；若current是樹的中根序列的第一個結(jié)點，則current沒有中根前趨；若leftThread=0，則left指向current的左孩子，此時，應(yīng)從current的左孩子開始，沿其右指針向下，直到找到?jīng)]有右孩子的結(jié)點s，即在左子樹中查找中根序列的最后一個結(jié)點（算法LIO(t.q)）其leftThread=1（

current沒有左子結(jié)點），則left指向該結(jié)點的前趨結(jié)點；若current是樹的中根序列的第一個結(jié)點，則current沒有中根前趨；ABDECFHIKGJL其leftThread=1（

current沒有左子結(jié)點），則left指向該結(jié)點的前趨結(jié)點；ABDECFHIKGJL若leftThread=0，則left指向current的左孩子，此時，應(yīng)從current的左孩子開始，沿其右指針向下，直到找到?jīng)]有右孩子的結(jié)點s，即在左子樹中查找中根序列的最后一個結(jié)點（算法LIO(t.q)）ABDECFHIKGJL算法PIO(t,

p

.

q

)/*給定中序線索二叉樹T*，t指向T*之根，本算法搜索T*之結(jié)點p的中根前驅(qū)結(jié)點，令q指向該前驅(qū)*/PIO1.[求T*之中根序列首結(jié)點]FIO(t

.

first).PIO2.[p

first？]IF

p

first

THEN(q

.

RETURN

q

.)/*若p為T*之中根序列的首結(jié)點，則p無前驅(qū)，置q

*/PIO3.[取p之左指針]lp

Left(p).PIO4.[LThread(p)1?]IF

LThread(p)1THEN(q

lp

.

RETURN

q

.)/*此時LThread(p)1，lp指向p的前驅(qū)結(jié)點*/

ELSE(LIO(lp.

q).RETURN

q

.)/*此時LThread(p)0，p的前驅(qū)是根為lp之二叉樹的中根序列的末結(jié)點*/?(3’)在線索二叉樹中搜索current的中根后繼算法思想:若current是樹的中根序列的最后一個結(jié)點，則current沒有中根后繼；若其rightThread=1（

current沒有右子結(jié)點）

，則right指向該結(jié)點的后繼；若rightThread=0，則right指向該結(jié)點的右孩子，此時，應(yīng)從current的右孩子開始，沿左指針向下，直到找到?jīng)]有左孩子的結(jié)點s（leftThread=1）,則s就是current的后繼，即后繼是中序遍歷current的右子樹時，訪問的第一個結(jié)點；ABDECFHIKGJL若current是樹的中根序列的最后一個結(jié)點，則current沒有中根后繼；ABDECFHIKGJL若current是樹的中根序列的最后一個結(jié)點，則current沒有中根后繼；ABDECFHIKGJL若rightThread=0，則right指向該結(jié)點的右孩子，此時，應(yīng)從current的右孩子開始，沿左指針向下，直到找到?jīng)]有左孩子的結(jié)點s（leftThread=1）,則s就是current的后繼，即后繼是中序遍歷current的右子樹時，訪問的第一個結(jié)點；ABDECFHIKGJL

算法NIO*

(t,

p.

q)/*給定中序線索二叉樹T*，t指向T*之根，本算法在T*中搜索其結(jié)點p的中序后繼，并令q指向該后繼*/NIO*1.[求中根序列末結(jié)點]LIO(t

.

last).NIO*2.[p

last?]IF

p

last

THEN(q

.

RETURN

q

.)NIO*3.[取p之右指針]rp

Right(p).NIO*4.[RThread(p)1?]IF

RThread(p)1

THEN(qrp.

RETURN

q

.)/*rp是右線索，它指向p之后繼*/

ELSE(FIO(rp

.

q).

RETURN

q

.)/*p之后繼是以rp為根的二叉樹的中根序列首結(jié)點*/?在后序線索二叉樹中，查找前驅(qū)結(jié)點若結(jié)點p是后序序列首結(jié)點，則p無后序前驅(qū)；/*情況1*/若結(jié)點p非后序序列首結(jié)點：

若LThread(p)1，則Left(p)指向p的后序前驅(qū)結(jié)點；/*情況2，Left(p)為左線索*/若LThread(p)0，則：/*此時p有左子樹.∵后序遍歷，p之后序前驅(qū)必是兩子樹中最后被遍歷的結(jié)點，情況3*/若p有右子樹，則p之右孩子是其后序前驅(qū)；若p無右子樹，則p之后序前驅(qū)是其左孩子.算法PPO(t,

p

.

q

)/*給定后序線索二叉樹T*，t指向T*之根，本算法搜索T*中結(jié)點p的后序前驅(qū)，并令q指向該前驅(qū)*/PPO1.[求后序序列首結(jié)點]FPO(t

.

first).

/*算法FPO求后序線索二叉樹之后序序列首結(jié)點，請讀者自行給出*/PPO2.[pfirst?]IF

pfirst

THEN(q

.RETURNq

.)/*p是后序序列的首結(jié)點，故p無前驅(qū)*/PPO3.[取Left(p)]lpLeft(p).PPO4.[LThread(p)1?]IF

LThread(p)1THEN(qlp

.

RETURN

q

.)/*lp是左線索，lp指向p之前驅(qū)*/PPO5.[取Right(p)]rpRight(p).PPO6.[rp?]IF

rp

THEN(qrp

.

RETURN

q

.)/*rp是p的后序前驅(qū)*/ELSE(qlp.

RETURN

q

.)?后序線索二叉樹中，找結(jié)點的后繼算法思想:

對任意結(jié)點p，若p為二叉樹的根，則無后繼;

若p是其父結(jié)點的右孩子、或是獨生左孩子，則后繼為其父結(jié)點；若p是有兄弟的左孩子，則后繼為其父結(jié)點的右子樹上按后序遍歷時，訪問的第一個結(jié)點；A00B10C11D01E11∧先序線索二叉樹的存儲結(jié)構(gòu)ABCDE找結(jié)點的后繼算法找結(jié)點的前趨算法A00B10C11D01E11∧后序線索二叉樹的存儲結(jié)構(gòu)CBEDA找結(jié)點的前趨算法找結(jié)點的后繼算法A00B10C11D01E11∧∧中序線索二叉樹的存儲結(jié)構(gòu)遍歷線索二叉樹欲對X序（先序、中序或后序）線索二叉樹進行X序遍歷只需從X序遍歷序列之首結(jié)點p出發(fā)，找p的X序后繼q，再找q的X序后繼r，如此下去直至找到X序之末結(jié)點為止。算法InOrder(t)/*t指向中序線索二叉樹T*之根，本算法中根遍歷T*/InOrder1.[求中根序列首結(jié)點]FIO(t

.

q).InOrder2.[用NIO*求q之中序后繼]WHILE

q

DO(PRINT(Data(q)).

NIO*(t,q

.

q).

)?插入結(jié)點在線索二叉樹T*中插入結(jié)點p，作為T*中某結(jié)點s的左子結(jié)點或右子結(jié)點。⑴若s無右子樹，則令p作為s的右子結(jié)點，并修改s和p的相應(yīng)指針①

Right(p)Right(s).

/*s的后繼指針成為p的后繼指針*/②

RThread(p)

RThread(s).

/*結(jié)點p的RThread域值為1*/③

Left(p)

s

.LThread(p)1.

/*p的前驅(qū)為s*/④Right(s)

p

.

RThread(s)0.

/*p成為s的右子結(jié)點*/succsprootpsuccpredsroot插入結(jié)點⑵若s有右子樹，則將

變成p的右子樹，p變成s的右子結(jié)點，并修改s和p的相應(yīng)指針以及

的中序序列首結(jié)點的Left和LThread域之值①

Right(p)

Right(s).

RThread(p)

RThread(s).

/*s的右子樹變成p的右子樹*/②Left(p)s.

LThread(p)1.

/*p的前驅(qū)結(jié)點為s*/③Right(s)

p

.

/*p成為s的右子結(jié)點*/ ④q

Right(p).

FIO(q.

q).

Left(q)

p.

/*q為p之右子樹的中序序列首結(jié)點，q的前驅(qū)指針指向p*/succrootpredsppresuccpresproot刪除結(jié)點刪除一個結(jié)點的右孩子（結(jié)點s的右子結(jié)點p存在）.

（1）若p為葉結(jié)點

只須修改s的Right和RThread域之值Right(s)Right(p).RThread(s)1./*p的后繼結(jié)點成為s的后繼結(jié)點*/srootpredsuccpsuccroots刪除結(jié)點（2）若p有右子樹，無左子樹，則把p的右子樹變成s的右子樹，并修改temp的前驅(qū)指針(右子樹之中根序列的第一個結(jié)點)Right(s)Right(p).Left(temp)s./*p的右子樹成為s的右子樹,

temp的前驅(qū)結(jié)點變成s*/sprerootsucctempsppreroottempsuccpre刪除結(jié)點

（3）若p無右子樹，有左子樹則把p的左子樹變成s的右子樹，并修改temp的后繼指針(左子樹之中根序列的最后一個結(jié)點)Right(s)Left(p).

Right(temp)Right(p).

/*p的左子樹成為s的右子樹，

temp的后繼結(jié)點變成s*/rootstempsuccpresuccprootssuccpretemp刪除結(jié)點（4）若p既有左子樹，又有右子樹(保證不改變原二叉樹的中根序列)將p之左子樹變成s的右子樹，p的右子樹變成temp的右子樹(指向p之左子樹的中根序列的最后一個結(jié)點)令temp1指向p之右子樹的中根序列的第一個結(jié)點Right(temp)Right(p)

RThread(temp)0

/*p的右子樹鏈接為temp的右子樹*/Left(temp1)temp

/*temp1的前驅(qū)結(jié)點變成temp*/Right(s)Left(p)

/*p的左子樹鏈接為s的右子樹*/presuccsuccptemp1pretemprootstemp1rootstemppresuccpre4.4樹和森林樹和森林的概念樹的定義

一個樹（或樹形）就是一個有限非空的結(jié)點集合T，其中：有一個特別標出的被稱為該樹（或樹形）之根root(T)的結(jié)點；其余結(jié)點（根除外）被分成m0個不相交的集合T1，T2，…，Tm，且T1，T2，…，Tm又都是樹（或樹形）。樹（或樹形）T1，T2，…，Tm被稱作root(T)的子樹（或子樹形）。樹與二叉樹的轉(zhuǎn)換

1.

樹轉(zhuǎn)換成二叉樹

樹與二叉樹的轉(zhuǎn)換

方法：① 在所有兄弟結(jié)點之間加一條連線；② 對每個結(jié)點，除保留與其大孩子和其大兄弟結(jié)點的連線之外，去掉該結(jié)點與其他孩子結(jié)點的連線。③ 調(diào)整部分連線方向、長短使之成為規(guī)范圖形。樹轉(zhuǎn)換成二叉樹ACBFDEACBFDE由樹轉(zhuǎn)換的二叉樹① 在所有兄弟結(jié)點之間加一條連線；② 對每個結(jié)點，除保留與其大孩子和其大兄弟結(jié)點的連線之外，去掉該結(jié)點與其他孩子結(jié)點的連線。③ 調(diào)整部分連線方向、長短使之成為規(guī)范圖形二叉樹轉(zhuǎn)換成樹

左子右兄ACBFDE由二叉樹轉(zhuǎn)換的樹ACBFDE二叉樹4.4.1樹的順序存儲結(jié)構(gòu)父結(jié)點法子結(jié)點示法先根序列及結(jié)點次數(shù)表示法后根序列及結(jié)點次數(shù)表示法層次序列表示法父結(jié)點表示法RADEFCBGKHR-1A0B0C0D1E1F3G6H6K60123456789數(shù)組下標:*便于涉及雙親的操作；*求結(jié)點的孩子時需要遍歷整棵樹。孩子表示法RADEFCBGKH0123456789數(shù)組下標:*便于涉及孩子的操作；求雙親不方便；*采用同構(gòu)的結(jié)點，空間浪費。R1A4B-1C6D-1E-1F7G-1H-1K-1235-1

-1

-1

-1

-1

-1

-1

-1

-1

89

-1

-1

-1

-1

-1

-1

樹的先根序列及結(jié)點次數(shù)表示法樹的先根遍歷的定義（1）訪問根結(jié)點（2）從左到右依次先根次序遍歷樹的諸子樹RADEFCBGKH先根序列RADEBCFGHK定理4.1

如果已知一個樹的先根序列和每個結(jié)點相應(yīng)的次數(shù)，則能唯一確定該樹的結(jié)構(gòu)。證明：用數(shù)學歸納法

1.若樹中只有一個結(jié)點，定理顯然成立。

2.假設(shè)樹中結(jié)點個數(shù)小于n(n≥2)時定理成立。

3.當樹有n個結(jié)點時，由樹的先根序列的定義知，序列中的第一個結(jié)點為根結(jié)點（設(shè)為A）。

設(shè)該結(jié)點的次數(shù)為k，k≥1（因n≥2），因此A有k個子樹，且第一個子樹排在最前面，而第k個子樹排在最后面，并且每個子樹的結(jié)點個數(shù)小于n，故由歸納假設(shè)知，每個子樹都能唯一確定，從而以A為根的樹亦能唯一確定，證畢?第一個子樹排在最前面，第k個子樹排在最后面，并且每個子樹的結(jié)點個數(shù)小于n，由歸納假設(shè)可知，每個子樹可以唯一確定，從而整棵樹的樹形可以確定。

先根序列ABCDEFGHIJKL度序列403000022000后根次序和結(jié)點次數(shù)表示法例后根序列EFBCHIJGDA結(jié)點的次數(shù)0020000313層次次序和結(jié)點次數(shù)表示法已知一個樹的層次序列和每個結(jié)點相應(yīng)的次數(shù)，則能唯一確定該樹的結(jié)構(gòu)。

4.4.2樹的鏈接存儲結(jié)構(gòu)

(1)Father鏈接結(jié)構(gòu):不易實現(xiàn)遍歷

ACBFDEACBDFE∧孩子鏈表表示RADEFCBGKH0123456789數(shù)組下標:*便于涉及孩子的操作；*求結(jié)點的雙親時不方便。R

A

B/C

D/E/F

G/H/K/1

2

3/4

5/6/7

8

9/3孩子兄弟表示法（二叉樹表示法）結(jié)點結(jié)構(gòu)firstchildnextbrotherdataRADEFCBGKHR∧A∧DE∧∧C∧H∧F∧G∧B∧K∧∧孩子兄弟表示法示例：①

搜索父結(jié)點算法FindFather(t,p.

result)/*在以t為根指針的樹中，搜索指針p所指結(jié)點的父結(jié)點。若找到，則令指針result指向其父結(jié)點；否則，令指針result為空*/FF1[找到t所指結(jié)點的第一棵子樹]qFistChild(t).FF2[從t的第一棵子樹開始搜索，若搜索到，則返回；否則，搜索t的下一棵子樹]WHILE

q

AND

q

pDO( FindFather(q,p.result)

IF

result

THEN

q

NextBrother(q) ELSE

RETURN

result.)FF3[遞歸出口：若p是t的一個子結(jié)點，令指針result

指向t]IF

q

p

THEN

RETURN

resultt.ELSE

RETURNresult

.?②搜索指定數(shù)據(jù)域的結(jié)點算法FindTarget(t,target.result)/*在以t為根指針的樹中，搜索數(shù)據(jù)成員等于target的結(jié)點。若找到，則令指針result指向該結(jié)點；否則，令指針result為空*/FT1[若找到，則指針result指向該結(jié)點] IF

Data(t)

target

THEN (RETURN

result

t.)FT2[從t的第一棵子樹開始搜索]p

FistChild(t).FindTarget(p,target.result).WHILE

p

AND

result

DO(p

NextBrother(p).FindTarget(p,target.result).)FT3[在以t為根的樹中，沒有搜索到數(shù)據(jù)成員等于target的結(jié)點]RETURN

result

.?③搜索大兒子結(jié)點算法GFC(p.q)/*算法GFC搜索指針p所指結(jié)點的大兒子結(jié)點，若找到，則令指針q指向它；否則，令指針q為空；GFC是GetFirstChild之縮寫*/GFC1.[指針p所指結(jié)點存在，并且存在大兒子結(jié)點]IF

p

AND

FistChild(p)

THEN (RETURN

q

FistChild(p).)GFC2.[大兒子結(jié)點不存在]RETURN

q

.?

④刪除子樹算法DS(t,

p)/*算法DS在以t為根的樹中刪除根為p的子樹；DS是DelSubtree之縮寫*/DS1.[指針t所指結(jié)點和指針p所指結(jié)點中有一個不存在，則返回]IF

t

OR

p

THEN

RETURN.DS2.[確定p所指結(jié)點的父結(jié)點是否存在]FindFather(t,p.result).

IF

result

THEN

RETURN.DS3.[若p所指結(jié)點的父結(jié)點存在，并且p是其父結(jié)點的大兒子結(jié)點]

IF

FistChild(result)

p

THEN(

FistChild(result)

NextBrother(p).Del(p).

RETURN.)DS4.[若p所指結(jié)點的父結(jié)點存在，并且p不是其父結(jié)點的大兒子結(jié)點，則搜索p的前一個兄弟結(jié)點q]q

FistChild(result).

WHILE

NextBrother(q)

p

DO

q

NextBrother(q).

NextBrother(q)

NextBrother(p).Del(p).

RETURN.?三種情況：1、刪除以A為根的子樹2、刪除以B為根的子樹3、刪除以C為根的子樹RADEFCBGKHRBAKCFDEGH三種情況：1、刪除以A為根的子樹2、刪除以B為根的子樹3、刪除以C為根的子樹RADEFCBGKHRBAKCFDEGH三種情況：1、刪除以A為根的子樹2、刪除以B為根的子樹3、刪除以C為根的子樹RADEFCBGKHRBAKCFDEGH④刪除子樹算法DS(t,

p)/*算法DS在以t為根的樹中刪除根為p的子樹；DS是DelSubtree之縮寫*/DS1.[指針t所指結(jié)點和指針p所指結(jié)點中有一個不存在，則返回] IF

t

OR

p

THEN

RETURN.DS2.[確定p所指結(jié)點的父結(jié)點是否存在]FindFather(t,p.result).

IF

result

THEN

RETURN.DS3.[若p所指結(jié)點的父結(jié)點存在，并且p是其父結(jié)點的大兒子結(jié)點]

IF

FistChild(result)

p

THEN(

FistChild(result)

NextBrother(p).Del(p).

RETURN.)DS4.[若p所指結(jié)點的父結(jié)點存在，并且p不是其父結(jié)點的大兒子結(jié)點，則搜索p的前一個兄弟結(jié)點q]q

FistChild(result).

WHILE

NextBrother(q)

p

DO

q

NextBrother(q).

NextBrother(q)

NextBrother(p). Del(p).RETURN.?森林與二叉樹的轉(zhuǎn)換森林：是m(m≧0）棵互不相交的樹的集合。1

森林轉(zhuǎn)成二叉樹原則：

①把森林中第一棵樹T1的根作為整個森林的根；

②把森林中其它樹的根依次作為T1的兄弟結(jié)點。

森林轉(zhuǎn)成二叉樹

ACBDFEGJHI[例]

森林轉(zhuǎn)成二叉樹

[例]ACBDFEGJHIR

森林轉(zhuǎn)成的二叉樹1

森林轉(zhuǎn)成樹2二叉樹GJHIFEACBDACBDFEGJHIR森林與二叉樹之間的自然對應(yīng):任何一個森林都對應(yīng)一棵二叉樹。同理，如果逆轉(zhuǎn)這個過程，任何一個二叉樹就對應(yīng)一個唯一的森林。定義

設(shè)F=(T1,T2,…,Tn)表示由樹T1,T2,…,Tn組成的森林。自然對應(yīng)下森林F的二叉樹B(F)遞歸定義如下：（1）n=0

，則B(F)為空；（2）若n>0，則B(F)的根是ROOT(T1)，B(F)的右子樹是B((T2,…,Tn))，左子樹是B((T11,T12,…,T1m))，其中T11,T12,…,T1m是ROOT(T1)的諸子樹。森林和自然對應(yīng)的二叉樹

GJHIFEACBD[例]××ACBDFEGJHI二叉樹轉(zhuǎn)成森林樹和森林的遍歷1樹的遍歷先根遍歷：先訪問樹的根結(jié)點，然后依次先根遍歷每棵子樹。先根遍歷序列：ABCEFDACBFDE后根遍歷：先依次后根遍歷每棵子樹，然后訪問樹的根結(jié)點。

后根遍歷序列：BEFCDAACBFDE

2森林的遍歷先根遍歷森林：

①訪問森林中第一棵樹的根結(jié)點；

②先序遍歷第一棵樹中根結(jié)點的子樹森林；

③先序遍歷其余的樹構(gòu)成的森林。ACBDFEGJHI森林的先根遍歷序列：

ABCDEFGHIJ二叉樹GJHIFEACBD二叉樹的先根序列：

ABCDEFGHIJ

后根遍歷森林：

①后序遍歷第一棵樹的子樹森林；

②訪問森林中第一棵樹的根結(jié)點；

③后序遍歷其余的樹構(gòu)成的森林。ACBDFEGJHI森林的后根遍歷序列：

BCDAFEHJIG二叉樹GJHIFEACBD二叉樹的中根序列：

BCDAFEHJIG①遞歸算法——先根遍歷以當前結(jié)點current為根的樹算法PreOrder(t)/*遞歸先根遍歷以t為根指針的樹。*/PreOrder1.[若t為空返回]

IFt=

THENRETURN.PreOrder2.[訪問t所指結(jié)點]PRINT(Data(t)).PreOrder3.[將指針t

定位到它所指結(jié)點的第一個子結(jié)點]

GetFistChild(t.child); PreOrder4.[先根遍歷t所指結(jié)點的諸子樹]WHILE

child

DO( PreOrder(child). GetNextBrother(child.child).)?迭代算法（非遞歸）首先，將當前結(jié)點設(shè)為根結(jié)點。（1）訪問當前結(jié)點，若當前結(jié)點的firstChild不為NULL(當前結(jié)點有子結(jié)點)，將當前結(jié)點壓入棧，并將其子結(jié)點設(shè)為當前結(jié)點；反復(fù)執(zhí)行（1），直至當前結(jié)點為空。（2）從棧中彈出一個結(jié)點，將其設(shè)為結(jié)點p，若它有大兄弟結(jié)點，則將其大兄弟結(jié)點壓入棧，且將該兄弟結(jié)點設(shè)為結(jié)點p；否則，反復(fù)執(zhí)行（2），直至彈出的結(jié)點有大兄弟結(jié)點或?？找灾翢o結(jié)點可彈出。（3）反復(fù)執(zhí)行（1）（2），直至棧為空。②迭代算法——先根遍歷以當前結(jié)點current為根的樹算法