第1頁4.1樹的基本概念4.2二叉樹(BinaryTree)4.3線索二叉樹(ThreadedBinaryTree)4.4樹與森林(Tree&Forest)4.5壓縮與哈夫曼樹(HuffmanTree)4.6應用第四章樹第2頁在現實世界中，樹（或曰樹結構）大量存在，例如用樹可形象地表示家譜、行政組織機構、著作目錄等。樹在計算機領域中也有著廣泛的應用，例如在編譯程序中，用樹來表示源程序的語法結構；在數據庫系統中，可用樹來組織信息；在分析算法的行為時，可用樹來描述其執行過程。緒論第3頁例1.大學層次結構吉林大學人文學部哲學社會學院文學院外國語學院藝術學院體育學院社會科學部文學院外國語學院藝術學院體育學院理學部數學學院物理學院化學學院生命科學學院第4頁下圖給出了Joe(喬)的后代的層次結構,其中Joe在頂層,Joe的孩子Ann(安),Mary(瑪麗)和John(約翰)列在下一層,在父母和孩子間有一條邊.在層次表示中,很容易找到Ann的兄弟姐妹,Joe的后代,Chris(克里斯)的祖先等.例2.Joe的后代JoeAnnMaryJohnMarkSueChris第5頁總裁銷售副總裁市場副總裁財務副總裁開發副總裁例3.

某公司組織管理機構某公司中地位最高的人為總裁，在最高處；副總裁的地位次之，位于總裁之下.副總裁為總裁的下屬，總裁是其上級。每個副總裁都有自己的下屬，而其下屬又可能有自己的下屬。圖中,每個員工若有直接下屬或直接上級，則兩者間有一條邊互連。第6頁聯邦政府國防部教育部稅務部陸軍海軍空軍海軍陸戰隊下圖是聯邦政府層次結構圖.頂層元素(亦稱機構)是聯邦政府，下一級是其主要的隸屬單位，如不同的部.每個部可進一步劃分，其分支在下一層示出.例如國防部包括陸軍,海軍,空軍和海軍陸戰隊.每個機構，若有分支機構，則兩者間有一條邊。下圖展現了諸元素間的整體-部分關系.例4.政府機構第7頁文字處理器文件字體導入光標OpenNewSavePrintQuit例5.某文字處理軟件結構下圖給出了某文字處理器的一種模塊分解圖.文字處理器是最頂層模塊,在其下層被劃分成4個模塊.文件模塊完成與文本文件有關的操作,如Open,New,Save,Print和Quit等.字體模塊包括與字體處理有關的所有功能模塊,且它們在字體模塊的下一層.導入模塊用于處理圖形、表格及其他格式的文本文件.光標模塊處理屏幕上光標的移動.在接口設計好之后,程序員可以相對獨立的方式分析、設計和開發每個模塊.

第8頁軟件的模塊化技術.一方面，模塊化的目標是將大而復雜的軟件系統，分解成許多功能獨立，較簡單、較小的模塊，使多人同時并行開發不同的模塊，可大大縮短整個軟件的開發時間.另一方面，分開測試一些小而獨立的模塊比測試一個大而復雜的模塊要容易得多，有利于保障開發的正確性。第9頁4.1樹的基本概念4.2二叉樹4.3線索二叉樹4.4樹和森林4.5壓縮與哈夫曼樹4.6

應用第10頁樹的遞歸定義定義4.1.1：一個樹(或曰樹形)就是一個有限非空的結點集合T，其中：有一個特別標出的被稱為該樹之根root(T)的結點；除根之外的其余結點被分成m0個不相交的集合T1,T2,…,Tm，且T1,T2,…,Tm又都是樹.樹T1,T2,…,Tm被稱作root(T)的子樹(或曰子樹形).4.1.1

樹的定義第11頁定義4.1.2

樹是包含n1個結點且滿足如下條件的有限集合:存在唯一的結點v0,它無前驅結點,稱為樹的根(或曰根結點)；任何非根結點都有且僅有一個前驅結點，稱為該結點的父結點；若某結點無后繼結點,則稱之為葉結點;任何非葉結點P都有1個后繼結點,稱其為P的子結點;任一非根結點vk都有且僅有一條從v0到vk的結點序列(或曰路徑)v0

v1

…

vk,其中vi是vi1(1

i

k)

的子結點。樹的非遞歸定義線性結構樹結構首結點(無前驅)根結點(無前驅)最后1個元素(無后繼)葉子結點可能多個(無后繼)其它數據元素(一個前驅,一個后繼)樹中其它結點(一個前驅,多個后繼)樹與線性結構的比較第12頁1、結點的度與樹的度一個結點的子結點的數目,被稱為該結點的度或曰次數.一棵樹的度為maxi

1nD(i),其中n為樹中結點總數,i指樹中的第i個結點,D(i)表結點i的度.2、葉結點與分支結點度為零的結點被稱為葉結點；度大于零的結點被稱為分支結點.4.1.2樹的相關術語第13頁3．結點的層數樹形T中結點的層數遞歸定義如下：⑴root(T)層數為零；⑵其余結點的層數為其前驅結點的層數加1.第14頁在圖4.1所示的樹T中：B有一個子結點E，度為1；A有三個子結點B,C和D(換言之,A是B,C和D的父結點)度為3；因為在T中,結點A的子結點數最多,故這棵樹的度為3.T

中F,G,H,I

為葉結點,其余結點為分支結點.T中,結點A

為樹T

之根,其層數為零;結點F的層數為3.第15頁圖4.1樹TACB層數0層數1DEGHIF層數2層數3T中,結點A的子結點數最多,故T的度為3第16頁4．邊，路徑，路徑長度樹形中結點間的連線被稱為邊。若樹T中存在結點序列vm

vm1…

vmk，1

k

T的最大層數，滿足vi1是vi（m

i

mk1）的子結點，則稱此結點序列為vm到vmk的路徑，該路徑所經歷的邊數k被稱為路徑長度.5.子孫結點、祖先結點一棵樹中若存在結點vm到vn的路徑，則稱vn為vm的子孫結點，vm為vn的祖先結點.第17頁一個結點到它的某個子孫結點有且僅有一條路徑.樹中結點間的父子關系具有如下特征：樹中任一結點都可有零個或多個直接后繼(即子結點),但至多只能有一個直接前驅(即父結點).樹中只有根結點無前驅,它是始結點;葉結點無后繼,它們是終結點.樹中某些結點之間具有父子關系或者祖先、子孫關系，祖先、子孫關系是父子關系的擴展,一些結點間,如兄弟結點(同一父親的諸子結點被稱為兄弟結點)之間就沒有這種關系。第18頁6．樹的高度樹的高度為maxi

1nNL(i),其中n為樹中結點總數,i指樹中第i個結點,NL(i)之值為結點i的層數.換言之,樹的高度指樹中結點的最大層數.第19頁A(B,C(D,E))3樹的表示:

1.集合嵌套表示法2.凹入表示法3.廣義表表示法4.樹形表示法BDE1ACABDE2CABCDE4第20頁樹的基本操作1、判樹空：TREEEMPTY(T)2、求根：ROOT(T)3、求樹的深度：TREEDEPTH(T)4、求結點的brothers:同一雙親的孩子互稱5、求結點的雙親：PARENT(T,e)6、求結點的孩子：CHILD(T,e,i)7、建樹:CREATE_TREE(T,T1,T2,…,Tm)8、遍歷樹：TRAVERSAL(T)第21頁4.2二叉樹(BinaryTree)4.2.1二叉樹的定義和主要性質定義4.2.1二叉樹(形)是結點的有限集合，它或者是空集，或者由一個根及兩個不相交的稱為這個根的左、右子樹形的二叉樹組成。第22頁二叉樹的五種不同形態LRRL(a)(b)(c)(d)(e)第23頁樹與二叉樹的主要區別：⑴二叉樹每個結點最多有2個子結點，樹則無此限制；⑵二叉樹中結點的子樹分成左子樹和右子樹，即使某結點只有一棵子樹，也要指明該子樹是左子樹，還是右子樹，就是說二叉樹是有序的；⑶樹決不能為空(即樹不能為空集),它至少有一個結點,而一棵二叉樹可以是空的(即可以為空集).第24頁A(a)(b)(c)(d)(e)ACBACBCBACBACB圖4.2.2含3個結點的所有二叉樹第25頁引理4.1二叉樹中層數為

i的結點至多有

2i個,i0.證明：用數學歸納法。當i0時,至多有一個根結點,其層數為0,因此當

i0時引理成立.假定當ik(k0)時引理成立，即第k層上至多有2k

個結點。對二叉樹的任意結點，其子結點個數最多為2,故第k1層上至多有22k2k+1

個結點，因此當ik1時，引理成立。證畢?二叉樹的性質第26頁高度為k(k1)的二叉樹中至少有k1個結點.有k1個結點的二叉樹高度至多為k1.圖4.2.3

是高度為3,結點最少(4個)的二叉樹之一.ABCD圖4.2.3有4個結點的二叉樹高度為3第27頁引理4.2

高度為k0的二叉樹至多有2k+11個結點.根據引理4.2.1第0層上至多有20個結點，第1層上至多有21個結點,……,第k層上至多有2k個結點,因此，高度為k的二叉樹中至多有20＋21＋……+2k

2k+1－1個結點。證畢?第28頁證明：設T中,度為1的結點為n1個,總邊數為e,則nn0+n1+n2

⑴非根結點有1條邊與父結點相連,有en–1⑵顯然又有，e2n2+n1⑶由上諸式有2n2+n1=n0+n1+n21

n2=n01n0=n2+1證畢?引理4.3任一有n個結點的二叉樹,其中葉結點數為n0,度為2的結點數為n2,則有n0n21第29頁滿二叉樹定義4.4一棵非空高為k（k

0）,具有2k+11個結點的二叉樹，被稱為滿二叉樹。第30頁712345689101112131415非空高為k二叉樹至多有2k+11個結點.滿二叉樹的特點是：葉結點都在第k層上；每個分支結點都有兩個子結點；葉結點的個數等于非葉結點個數加1(對滿二叉樹而言，除葉結點外，其它結點的度均為2.見引理4.3).第31頁層次順序:按從上至下,即從第0至第k層，每層由左到右的次序.定義4.5

一棵有n個結點、高為k的二叉樹T,一棵高為k的滿二叉樹T*,用正整數按層次順序分別編號T和T*的所有結點,如果T之所有結點恰好對應于T*的前n個結點，則稱T為完全二叉樹.完全二叉樹顯然,滿二叉樹一定是完全二叉樹.第32頁第33頁71234568910111213141512345678910完全二叉樹滿二叉樹包含n個結點、高為k的完全二叉樹的特點：樹中只有最下面兩層結點的度可小于2；樹中最下面一層的結點都集中在該層最左邊

的若干位置上；樹中葉結點只能出現在層數最大、次大的兩層上，即存在一個整數m0使得樹中每個葉結點在第m或第m1層上；對樹中所有結點,按層次順序,用正整數從1開始編號,僅僅編號最大的非葉結點可無右孩子,其余非葉結點都有兩個孩子結點；在層次順序意義下,樹中所有結點對應于高為k的滿二叉樹中編號由1至n的那些結點。第34頁引理4.4將一棵有n

個結點的完全二叉樹,按層次順序用自然數從1開始編號，則有：若1i

n,則編號為i之結點的父結點編號

為

i/

2

.若2i

n,且編號為i

的結點有左孩子,則其

左孩子的編號為2i．若2i1

n,且編號為

i

的結點有右孩子,則其右孩子的編號為2i+1．僅編號最大的非葉結點可無右孩子,但必須有

左孩子,其余非葉結點都有兩個孩子結點.第35頁用歸納法證明引理4.4:若i

1，n2，則其左孩子的編號顯然為2.假定對所有

j(1

ji,2i

n),其左孩子編號為2j.如果

2(i1)n

,那么對結點

ji1,往證其左孩子的編號為2(i1).由層次順序知,i1的左孩子之前的兩個結點就是i的左孩子和右孩子,由歸納假設知i

的左孩子編號為2i,故i

的右孩子編號為2i1,從而i1的左孩子編號為2i22(i1).其它條款可仿證.證畢?第36頁引理4.5具有n

個結點的完全二叉樹的高度是log2n.證明：設二叉樹高度為k

,

由定義4.5知,

完全二叉樹的結點個數介于高度為k1和k

的滿二叉樹的結點數之間，即有：

2k

1

n

2k+1

1從而有2k

n

2k+1，即k

log2n

k+1，因為

k

為整數，故有k

log2n

.證畢?第37頁二叉樹的存儲結構要存儲一棵二叉樹，需存儲其所有結點的數據信息，以及其左、右孩子的地址。通常有兩種存儲方式：順序存儲鏈接存儲第38頁4.2.2二叉樹的順序存儲二叉樹的順序存儲(或曰順序存儲方式，順序存儲方法)：

系指將二叉樹的所有結點按層次順序存放在一塊地址連續的存儲空間中，同時要反映出二叉樹中結點間的邏輯關系。第39頁對于任一完全二叉樹T,結點的層次順序反映了

其結構,可按層次順序給出其結點編號:這就是

T的順序存儲方式,結點編號恰好反映了

T

結

點間的邏輯關系。若對完全二叉樹T之結點按層次順序編號,則

可用一維數組A對其進行存儲,A[i]存儲T中

編號為i的結點，其中A[1]存儲T的根結點；

若結點A[i]有左孩子，則其存放在A[2i]處；若結點A[i]有右孩子,則其存放在A[2i1]處.第40頁圖4.2.5完全二叉樹的順序存儲結構(b)圖(a)的順序存儲結構順序存儲結構ABECDA[1]A[2]A[3]A[4]A[5]1(a)5個結點的完全二叉樹EBACD2345第41頁結點值3123126694175706249結點編號12345678910106649311294175706212345672389哪個是編號最大的非葉結點？第42頁若將上述方法用于非完全二叉樹,卻有很多缺點.如果采用上述順序存儲方式，按層次順序，對非完全二叉樹之結點進行編號，則編號不能表達結點間的邏輯關系.為此先通過添加虛結點將其轉換成一棵“完全二叉樹”,然后再對原來的結點和虛結點統一編號,最后完成順序存儲。但這無疑增加了用于存儲虛結點的空間。第43頁(a)

非完全二叉樹ABCDA[1]A[3]A[7]A[15](c)非完全二叉樹的順序存儲結構轉換(b)完全二叉樹ABCDABCD第44頁二叉樹鏈接存儲系指二叉樹的諸結點被隨機存放在內存空間中,用指針指明結點間的邏輯關系.二叉樹的結點結構

在二叉樹的鏈接存儲中，結點包含三個域，數據域data、左指針域left和右指針域right，其中左、右指針分別指向該結點的左、右子樹的根結點；結點結構圖示如下：4.2.3二叉樹鏈接存儲第45頁leftdataright常用data字段值表示結點的名字.如在右圖第2層最左邊的結點C中,left域中的表示C的左子樹為空,right域的表示C的右子樹為空.ABCDEFG第46頁CABDEFG二叉樹鏈接存儲結構Leftdataparentright另一種結點結構：結點包括三個指針域,parent域中指針指向其父結點第47頁算法Father(t,p.q)/*指針t指向二叉樹T之根;Father使用遞歸在T

中搜索給定結點p之父結點;q指向p之父結點*/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).IFqL

THEN(q

qL

.RETURN.).Father(Right

(

t

),p

.qR).q

qR

.?①在二叉樹中搜索給定結點的父結點第48頁問題：為什么需要淺綠色語句?②搜索二叉樹中符合數據域條件的結點算法Find(t,item

.q

)/*指針t指向二叉樹T之根,Find在T中搜索Data

域之值為item的結點,指針q指向該結點*/Find1.[t

?]IFt

THEN(q

.RETURN.

).IFData(

t

)

itemTHEN(q

t

.RETURN.

).Find2.[遞歸]Find

(

Left(t),item

.p

).IFp

THEN

(q

p

.RETURN.

).Find

(Right(t),item

.q

).?第49頁③從二叉樹中刪除給定結點及其左右子樹算法DST(t)/*root指向二叉樹T之根，DST從T中

刪除給定結點t及其左右子樹*/DST1.[t

?]IFt

THENRETURN.DST2.[t

root?]IFt

rootTHEN(Del(t).root

.RETURN.)DST3.[找t的父親q]p

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

pTHENLeft(q)

.IFRight(q)

pTHENRight(q)

.DST5.[刪除p及其子樹]Del(p).?第50頁算法Del(p)//刪除結點p及其左右子樹Del1.[p

?]IFp

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

p.?假定，當前p指向結點C第51頁AGBCDEF二叉樹的遍歷：按照一定次序訪問樹中所有結點，且使每個結點恰好被訪問一次。以先根(中根、后根)次序遍歷二叉樹T,得到T之

結點的一個序列,稱為T的先根(中根、后根)序列.遍歷方式先根遍歷：

DLR中根遍歷：

LDR后根遍歷：

LRD4.2.4二叉樹的遍歷D二叉樹RL第52頁當二叉樹為空則什么都不做,否則遍歷分三步進行：二叉樹之先根,中根和后根遍歷定義先根序中根序后根序步驟一訪問根以中根序遍歷左子樹以后根序遍歷左子樹步驟二以先根序遍歷左子樹訪問根以后根序遍歷右子樹步驟三以先根遍歷右子樹以中根序遍歷右子樹訪問根第53頁+ABEFDC圖4.11

表達式(A+B)((CD)E+F)對應的二叉樹第54頁例：先根序遍歷得到的結點序列：ABCDEF中根序遍歷得到的結點序列：A+BCDE+F后根序遍歷得到的結點序列：AB+CDEF+中根遍歷二叉樹算法框架:若二叉樹為空,則空操作;否則：中根遍歷左子樹;訪問根結點;中根遍歷右子樹.表達式語法樹的中根遍歷

結果：abcde/f中根遍歷(InorderTraversal,中序遍歷)表達式語法樹afbcde第55頁二叉樹結點在水平線上的投影即中序遍歷結果GKHAFEDCBCBDFE

AH

G

K第56頁這三種結點序列都非常重要，它們分別與表達式的前綴、中綴和后綴表示相對應(其中,中綴表示還需要括號和優先級,稍有差別).

第57頁二叉樹遞歸的中根遍歷算法算法Inorder（t）/*;步驟中簡記Inorder為INO

*/INO1.[遞歸出口]

//若二叉樹為空,則終止算法IFtNULLTHENRETURN.INO2.[遞歸遍歷]Inorder(left(t)).PRINT(data(t)).Inorder(right(t)).?第58頁二叉樹遞歸的先根遍歷算法算法Preorder（t）/*;步驟中簡記Preorder

為PRO*/PRO1.[遞歸出口]//若二叉樹為空,終止算法IFtNULLTHENRETURN.PRO2.[遞歸遍歷]PRINT(data(t)).Preorder(left(t)).Preorder(right(t)).)?

第59頁二叉樹遞歸的后根遍歷算法算法Postorder（t）/*;步驟中簡記Postorder

為POO*/POO1.[樹為空?]IFtNULLTHENRETURN.POO2.[后根遍歷子樹]Postorder(left(t)). Postorder(right(t)).POO4.[訪問根]PRINT(data(t)).?

第60頁算法NIO(t)/*設t是指向一棵鏈接表示的二叉樹T

之根的指針,NIO利用一個輔助堆棧S以中根序訪問

T

的所有結點*/NIO1.[初始化]CREATE

(

S

).p

t

.

//創建空棧S

NIO2.[入棧]

WHILE

p

DO(S

p.p

Left(p).

)//*一直往左下方NIO3.[棧為空?]

IF

S為空THEN

RETURN

ELSE

p

S.NIO4.

[訪問p,更新p]PRINT(Data(

p

)).p

Right(

p

).NIO5.[返回]GOTONIO2.?非遞歸中根遍歷算法第61頁圖4.12非遞歸中根遍歷二叉樹(b)中根遍歷(a)中二叉樹,堆棧內容變化過程圖(b)中略去了進棧過程的描述NIO2.[入棧]WHILEp

DO

(S

p.p

Left

(p).)NIO3.[棧為空?]若S為空,則RETURN.否則

p

S.NIO4.[訪問,更新p]打印

Data(p).

pRight(p).

返回NIO2.第62頁

(a)二叉樹ABCEFD

AB

A

AD

C

CE

A

F訪問D訪問A訪問C訪問F

A

ABA進棧B進棧訪問B

ADD進棧

CC進棧E進棧

CE訪問EF進棧

F

定理4.1設算法NIO從步驟NIO2開始，p指向一棵有n個結點之二叉樹T*的根，此時棧S中有S[1],S[2],┅,S[m],m0.則步驟NIO2至NIO5將以中根序遍歷T*，并最后達到步驟NIO3，同時棧S也恢復到原來值S[1],S[2],┅,S[m].算法NIO正確性證明作業：讀書上之證明第63頁②非遞歸后根遍歷算法非遞歸后根遍歷算法需要一個輔助堆棧來記憶訪問路徑，算法中棧元素結構如下：樹中任一結點p都要進棧三次，出棧三次.

第一次出棧是為遍歷p的左子樹；第二次出棧是為遍歷p的右子樹；第三次出棧是為訪問p.其中i在集合{0,1,2}中取值,用來標識p

的

出棧次數.具體說明如下：

結點

退棧次數

i第64頁初始化時,將(根結點,0)進棧.

出棧,判斷出棧元素(p,i)中的標號i：若i0,則(p,1)

進棧;若p的左指針非空,則

(Left(p),

0)

進棧,準備遍歷

p

的左子樹./*

若p有左子樹,則其左子樹所有結點的二元組皆在p的二元組之上

*/

若i1,則(p,2)進棧;若

p

的右指針非空,則(Right(p),0)

進棧,準備遍歷

p

的右子樹./*

此時

p

的左子樹已被遍歷;若p有右子樹,則其右子樹所有結點的二元組皆在p的二元組之上*/

若i

2,訪問結點p.

//此時p

的左、右子樹都已被遍歷,自然應訪問根結點第65頁算法NPO(t)/*設二叉樹T以鏈接方式存儲,指針t

指向T之根,算法NOP利用堆棧S以后根序遍歷T*/NPO1.[初始化]IFt

THENRETURN.CREATS(S).S

(t,0).NPO2.[后根遍歷]WHILE棧S非空DO((p,i)S.IFi0THEN(

S

(p

,

1).若left(p)則

S(left(p),0).).IFi1THEN//此時p

的左子樹已被遍歷(

S

(

p

,

2).若

right(

p)

則

S

(

right(

p),

0).).IFi2THEN//此時p

的右子樹已被遍歷PRINT(data(p)).).?WHILE的每次迭代中3個IF語句僅執行一個第66頁

C,1A,2E,1

C,1A,2E,2訪E訪F訪C訪A

C,1A,2

C,2A,2F,0

C,2A,2F,1

C,2A,2F,2

C,2A,2

A,2

對左圖之二叉樹進行后序遍歷,棧S之變化

A,0

B,0A,1

B,1A,1

B,2A,1D,0

B,2A,1D,1

B,2A,1D,2

B,2A,1

A,1

C,0A,2

C,1A,2E,0訪D訪BWHILE棧S非空DO//分別簡記left、right為Lt和Rt(

(p,i)S.IFi0THEN

[S(p,1).

若

Lt

(p),則

S

(Lt(p),0).].IFi1THEN

[S(p,2).

若

Rt

(p),則

S

(Rt(p),0).].IFi2THEN

PRINT(data(p)).)?ABCDEF第67頁先根序列和中根序列可唯一確定一棵二叉樹ABDCEFKH[例]上圖二叉樹T的先序、中序遍歷結果:①先根序列A00BALCBRKCLDAREDLHELFDR②中根序列BALKCLCBRA00HELEDLDARFDR由①、②兩個序列可確定二叉樹的結構。

由①知T之根為A,由②知A之左子樹包括B,K,C三個結點

其右子樹包含H,E,D,F四個結點,再由①知A之左子樹的根為B，知A之右子樹的根為D，照此可確定出整個T之結構.譬如，FDR系指F是D的右孩子。A00系指T之根。第68頁后根序列和中根序列可唯一確定一棵二叉樹[例]

后根序列CEFDBHGA

中根序列CBEDFAGH第69頁后根序列CBLEDLFDRDBRBALHGRGARA00

中根序列CBLBALEDLDBRFDR

A00GARHGRAC

B

E

DFGHDEFABCGHABCGDEHF第70頁第71頁練習：已知某二叉樹的先序遍歷序列是ABDGCEFH，中序遍歷序列是DGBAECHF，它的后序遍歷序列是什么？給定一棵二叉樹T的先根序列和后根序列，那么能否由此確定出T之結構？第72頁層次遍歷:按層數由小到大,即從第0層開始逐層向下,同層中由左到右的次序訪問二叉樹的所有結點.遍歷結果:

ABECFDABECFD第73頁在第

i

層上若結點x

在結點y

的左邊，則x

一定在y

之前被訪問.同理,在第i1層上，x的孩子結點一定在y

的孩子結點之前被訪問.若訪問i

層上的所有結點，必須知道i

層上所有結點的地址，地址保存在其父結點的left或right指針中。由①，算法可用先進先出的隊列來實現；由②，除待遍歷二叉樹T的根結點之外，其余結點的地址均是其父結點的left或right.層次遍歷問題的分析第74頁使用一個先進先出結構的隊列Q，具體如下：將根結點插入Q.重復執行本步驟直至Q為空:若Q非空,取Q的頭結點n

并訪問;若n的左指針不空,將其左孩子插入Q;若n的右指針不空,將其右孩子插入Q.二叉樹層次遍歷算法的主要思想第75頁/*

算法LevelOrder按層次順序對鏈接存儲的二叉樹T進行遍歷，t

指向T

之根，Q

為隊列

*/LO1.[建空隊]CREATE(Q).LO2.[入隊]p

t.IF

p

THEN

Q

p.//T

之根入隊LO3.[層次遍歷]

WHILE

Q

非空DO(p

Q.PRINT(Data(p)).//取對頭并訪問

IF

Left(p)

THEN

Q

Left(p).

IF

Right(p)

THEN

Q

Right(p).)?算法LevelOrder(t)第76頁由二叉樹的遍歷算法，很容易想到用遍歷方法去創建二叉樹。如，從先根遍歷思想出發構造二叉樹。但先根序列不能唯一確定二叉樹的結構，兩棵不同的二叉樹卻可能有相同的先根序列。

原因是：二叉樹中，可能有其左指針和/或右指針為空的結點，先根序列不包含這方面的信息。

由此：需在先根序列中加入特殊符號以示空指針位置，這里不妨用“#”號表示空指針位置。4.2.5創建二叉樹第77頁遞歸算法CreateBinTree（簡記為CBT）以根指針t為輸入參數，以包含空指針信息的先根序列為輸入序列.當讀入"#"字符時，將其初始化為一個空指針；否則生成一個新結點并初始化其父結點之左、右指針.由于序列中用"#"表示空指針，故在算法中設置tostop"#"，以便判斷序列中的"#"號.當輸入序列為ABD#E###C##時,可創建下頁所示的二叉樹.第78頁算法CBT(tostop.t)//構造以結點t為根的二叉樹；tostop

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

tostop?]IFch

tostopTHEN(t

.RETURN.)ELSE(t

AVAIL.Data(t)

ch.)CBT3.[構造左子樹]CBT(tostop.Left(t)).CBT4.[構造右子樹]CBT(tostop.Right(t)).?

ABD#E###C##CBT(.t)

Data(t)A

CBT(.L(t))

Data(L(t))B

CBT(.L(L(t)))

Data(L(L(t)))D

CBT(.L(L(L(t)))).L(L(L(t))).

CBT(.R(L(L(t))))

Data(R(L(L(t))))E

CBT(L(R(L(L(t))))).L(R(L(L(t)))).

CBT(R(R(L(L(t))))).R(R(L(L(t)))).

CBT(.R(L(t))).

R(L(t)).

CBT(.R(t))

Data(R(t))C

CBT(.L(R(t))).

L(R(t)).

CBT(.R(R(t))).R(R(t)).?第79頁DBE####CA##ABD#E###C##簡記Left,Right為L和R;省略參數tostop,以及t

AVAIL等操作t第80頁設指針t指向一棵鏈接表示的二叉樹T，欲得到T的一個“備份”，則容易想到用先根、中根或后根遍歷二叉樹的解決方案。考慮到在創建二叉樹的算法中使用了先根遍歷的思想，這里最好嘗試其它遍歷方式，譬如說“后根遍歷”。若采用后根遍歷方式，則復制過程如下：

①復制左子樹；

②復制右子樹；

③生成父結點，連接父結點和左右子樹之根結點.4.2.6二叉樹遍歷的應用：復制二叉樹第81頁

算法

CT(t.p)

/*t指向鏈接表示的二叉樹T之根，二叉樹T為T的復制品，

p指向T之根;在CT中，復制采用后根遍歷方式*/

CT1.[遞歸出口]IFt

THENRETURN.CT2.[復制左子樹]IFLeft(t)

THENCT(Left(t).lptr)ELSElptr

.CT3.[復制右子樹]IFRight(t)

THENCT(Right(t).rptr)ELSErptr

.CT4.[生成根結點]p

AVAIL.Data(p)

Data(t).Left(p)lptr.Right(p)rptr.RETURNp.?CT(t.p)//t

指向結點A

CT(L(t).lptr)

//步CTP2.L(t)B

具體見85頁

CT(R(t).rptr)

//步CTP3.R(t)D具體見86頁

pAVAIL.Data(p)

Data(t).

L(p)lptr.//此時L(p)指向結點B，見85頁R(p)rptr.

//此時R(p)指向結點D，見86頁

RETURNp.?//此時p指向結點ABACDE簡記Left、Right為:L(t)和R(t)第82頁CT(L(t).lptr)

//L(t)B

lptr

//步CT2，L(L(t))

CT(R(L(t)).rptr)

lptr

//L(R(L(t)))

rptr

//R(R(L(t)))

pAVAIL.Data(p)Data(R(L(t))).//Data(p)C

L(p)lptr.R(p)rptr.

RETURNp.

//rptr

p

pAVAIL.Data(p)

Data(L(t)).//Data(p)B

L(L(t))

lptr.//L(L(t))

R(L(t))

rptr.

//R(L(t))指向結點C

RETURNp.//lptr

p，即

lptr

指向結點B第83頁簡記Left、Right為:L(t)和R(t)BADECCT(R(t).rptr)

CT(L(R(t)).lptr)//L(R(t))E

lptr

.

//CT2.L(L(R(t))))

rptr

.

//CT3.R(L(R(t))))

pAVAIL.Data(p)Data(L(R(t))).//Data(p)E

L(p)

lptr.//lptr

R(p)

rptr.//rptr

RETURNp.

//lptrp，此時lptr指向結點ECT(R(R(t)).rptr)RETURN.//rptr

pAVAIL.Data(p)

Data(R(t)).//Data(p)D

L(p)

lptr.//此時L(p)

指向結點E

R(p)

rptr.

//R(p)RETURNp.//rptr

p，此時rptr指向結點D

BADCE第84頁第85頁用后序遍歷計算二叉樹結點個數算法Count(t.n)/**/IFtNULLTHEN(n0.RETURN.)Count(left(t).nl).Count(right(t).nr).n

nlnr1.▌編寫計算二叉樹高度的算法[解題思路]二叉樹之深度可由如下公式求得：由此可見，該題可用遞歸算法求解。第86頁算法depth(t.d)/**/IFtTHEN(d1.RETURN.)ELSE(depth(left(t).d1).depth(right(t).d2).IF(d1>d2)THEN(dd11.RETURN.) ELSE(dd2+1.RETURN.)

)?

第87頁以Left/Right鏈接表示的二叉樹結構，可看作是由許多從根結點到葉結點的單鏈表組成的，一個結點的前驅結點是它的父結點，一個結點的后繼結點是它的孩子結點。這種結構的不足有二：

其一是，從一個結點出發只能訪問它的孩子結點，而不能訪問它的父結點；

其二是，這種結構通常包含很多未被有效利用的指針字段，譬如包含i個結點的二叉樹，在其2i個指針字段中僅有i1個被使用.4.3線索二叉樹第88頁為使二叉樹之訪問更方便,其空間利用率更高.1960年,珀利斯(A.J.Perlis)和桑頓(C.Thornton)提出了巧妙的線索二叉樹表示，并給出了以各種順序遍歷線索二叉樹的重要思想.但是珀利斯和桑頓提出的只是單向的線索二叉樹.1963年，霍特(A.W.Holt)又提出了雙向線索二叉樹。第89頁第90頁象雙向鏈表一樣,二叉樹也可采用雙向鏈接.如下圖所示,針對某種遍歷順序,可為二叉樹的每個結點增加兩個指針域，分別存放指向其前驅和后繼結點的指針Pred和Succ，并稱Pred和Succ為"線索".在這樣的二叉樹中,搜索一結點在某遍歷順序下的前驅或后繼將變得更加容易，但將增加一些存儲空間的開銷.LeftRight

DataPredSucc線索二叉樹定義4.6設T*是一棵二叉樹，其結點增加了針對某種遍歷順序的線索域，在T*中可直接查找任一結點在該遍歷順序下的前驅和后繼結點，稱T*為線索二叉樹

(Threaded

BinaryTree).第91頁在一棵線索二叉樹中，若指針Pred和Succ分別指向結點的先根（中根、后根）前驅和先根（中根、后根）后繼，則稱其為先序（中序、后序）線索二叉樹.書上：圖4.21(a)所示二叉樹T之中根遍歷序列為BCAED，它的中序線索二叉樹的鏈接表示如圖4.21(b)所示；T的后根序列為CBEDA，它的后序線索二叉樹的鏈接表示如圖4.21(c)所示.

第92頁(a)

二叉樹ABDCEPredSuccPredrootSuccPred(b)中序線索二叉樹的鏈接表示中序序列：BCAEDDEACBSuccPredSucc圖4.21線索二叉樹的鏈接表示圖中虛線箭頭表示線索第93頁后序線索二叉樹的鏈接表示后序序列：

CBEDASuccPredSuccSuccPredSuccrootADBCEPredPred第94頁線索二叉樹的問題與分析問題：由圖4.21可見，線索二叉樹的結點中仍有很多空指針，就是說存儲空間的浪費問題還未得到有效解決。分析：指針域需占用較多的存儲空間，如一個空間容量為4GB的內存儲器需要32個二進制位來表示地址，若將指針域中的Pred和Succ換成1個二進制位則會節省許多空間。

第95頁10月22日講到這里線索二叉樹的改進方案：將原指針域Pred和Succ分別改成存儲一個二進制位的域LThread和RThread.若結點t有左孩子，則Left指向t的左孩子，且LThread值為0;若t沒有左孩子,

則Left指向t的前驅結點,且LThread值為1，此時稱Left為線索.若結點t有右孩子，則Right指向t的右孩子，且RThread值為0；若t沒有右孩子，則Right指向t的后繼結點，且RThread值為1，此時稱Right為線索.第96頁圖4.22改進后的線索二叉樹(b)改進的中序線索二叉樹A00B10C11D01E11ABDCE(a)

二叉樹結點中為何出現?SuccPredPredSucc第97頁PredSuccroot

(c)改進后的后序線索二叉樹0A0D10B10E11C11SuccSuccPredABDCE(a)二叉樹為何Left域中放?第98頁在中序線索二叉樹中,不需要對二叉樹進行遍歷就可方便地找到給定結點的中序前趨和中序后繼結點，且不需要太多的額外空間。在改進的線索二叉樹中，一個結點是葉結點的充要條件是，其左、右標志（LThread、RThread）均為1.第99頁[1]-1在以t

為根的中序線索二叉樹中，搜索中根順序的第一個結點算法思想：若t

有左子樹，則中根遍歷順序的第一個結點就是左子樹中最左邊的結點；若t

無左子樹，中根遍歷順序的第一個結點就是t.

4.3.3線索二叉樹基本算法第100頁算法FIO(t.q)/*t指向改進的中序線索二叉樹T*之根，本算法返回T*的中根序列的首結點，并用q指向它*/FIO1.[初始化]q

t.FIO2.

[找中根序首結點]WHILELThread(q)0DOq

Left(q).RETURNq.?

第101頁WhileLThread(q)=0DOq

Left(q);A00B10C11D01E11t第102頁[1]-2搜索線索二叉樹T*之中根順序的最后一個結點,設t

指向T*之根.算法思想：若t

有右子樹，則中根序末結點就是右子樹中最右邊的結點；若t無右子樹，中根序的末結點就是t.

第103頁算法LIO(t.q)/*給定改進的中序線索二叉樹T*，t指向T*之根，LIO返回T*之中根序之末結點，并用q指向它*/LIO1.[初始化]q

t.LIO2.[找中根序末結點]WHILERThread(q)0DOq

Right(q).RETURNq.?第104頁解決該問題的主要思路：若p是中根序首結點，則p無中序前驅結點；

//情況1若p非中根序首結點：若LThread(p)1，則Left(p)為左線索，直接指向p的中序前驅結點；//情況2若LThread(p)0，p的中序前驅結點是p之左子樹的中根序末結點.//情況3[2]-1T是一棵改進的中序線索二叉樹，如何找出

T中結點p的中序前驅結點？第105頁算法PIO(t,p.q)/*給定改進的中序線索二叉樹（這里亦簡稱二叉樹）T*，t指向T*之根，算法PIO搜索T*中結點p的中序前驅結點，PIO運行結束時q指向它*/PIO1.[求中序首結點]FIO(t.first).IFp

firstTHEN(q

.RETURNq.)//p無前驅PIO2.[取p之左指針]lp

Left(p).IFLThread(p)1THEN(qlp.RETURNq.)

//情況2，lp指向p的中序前驅結點PIO3.[求中序末結點]LIO(lp.q).//求以lp

為根之二叉樹的中序末結點RETURNq.?第106頁主要思想：若p是中序末結點，則其無后繼結點；

//情況1若p非中序末結點：

//由中序定義知：p之后繼在p

的右子樹中若RThread(p)1，則Right(p)指向p之中序后繼//情況2，Right(p)為右線索若RThread(p)0，則p的中序后繼為p之右子樹的中序首結點。//情況3[2]-2T是一棵改進的中序線索二叉樹，如何找出T中

結點p之中序后繼結點？第107頁算法NIO*(t,p.q)/*給定改進的中序線索二叉樹（這里亦簡稱二叉樹）T*，t指向T*之根，NIO*搜索T*中結點p的中序后繼，當NIO*運行結束q指向它*/NIO*1.[求中序末結點]

LIO(t.last).IFp

lastTHEN(q

.RETURNq.)//情況1NIO*2.[取p之右指針]rp

Right(p).IFRThread(p)1THEN(qrp.RETURNq.)

//情況2，Right(p)為指向p之中序后繼的右線索NIO*3.[RThread(p)0]

FIO(rp.q).RETURNq.?

/*情況3，

rp為p之右子樹的根，q指向以rp為根之

二叉樹的中序首結點*/第108頁主要思想：若結點p是改進的后序線索二叉樹T*之后序首結點，則p無后序前驅；//情況1若結點p非T*之后序首結點：若LThread(p)1，則Left(p)指向p的后序前驅；

//情況2，Left(p)為左線索若LThread(p)0，則：

//情況3，此時p有左子樹若p無右子樹，則p之左孩子是其后序前驅；若p有右子樹，則p之右孩子是其后序前驅.[3]-1改進的后序線索二叉樹中結點p之后序前驅第109頁算法PPO(t,p.q)/*給定后序線索二叉樹T*，t指向T*之根，PPO搜索T*之結點p的后序前驅，并令q指向它*/PPO1.[求T*之后序首結點]FPO(t.first).//FPO求T*之后序首結點IFpfirst