數(shù)據(jù)結(jié)構(gòu)課件：第4章 樹1

1、4.1樹的基本概念4.2二叉樹4.3線索二叉樹4.4樹和森林4.5壓縮與哈夫曼樹4.6 應(yīng)用第四章 樹樹結(jié)構(gòu)在客觀世界中大量存在，如家譜、行政組織機(jī)構(gòu)等都可用樹形象地表示。JoeJohnMaryAnnChrisSueMaryMary企業(yè)管理機(jī)構(gòu) 在層次中地位最高的人(此處為總裁)在圖中位置最高。在層次中地位次之的(即副總裁)在圖中位于總裁之下等等。副總裁為總裁的下屬，總裁是他們的上級(jí)。每個(gè)副總裁都有自己的下屬，而其下屬又有自己的下屬。企業(yè)管理結(jié)構(gòu)總裁財(cái)務(wù)副總裁市場(chǎng)副總裁開發(fā)副總裁銷售副總裁. 遞歸定義定義4.1： 一個(gè)樹（或樹形）就是一個(gè)有限非空的結(jié)點(diǎn)集合T，其中：有一個(gè)特別標(biāo)出的被稱為該樹（

2、或樹形）之根root(T)的結(jié)點(diǎn)；其余結(jié)點(diǎn)（根除外）被分成m 0 個(gè)不相交的集合T1，T2，Tm，且T1，T2，Tm又都是樹（或樹形）。樹（或樹形）T1，T2，Tm被稱作root(T)的子樹（或子樹形）。一、樹的定義圖4.1為一棵由根結(jié)點(diǎn)A出發(fā)的樹，其中，A有三個(gè)子結(jié)點(diǎn)B、C和D；B有一個(gè)子結(jié)點(diǎn)E；E有一個(gè)子結(jié)點(diǎn)F；C有兩個(gè)子結(jié)點(diǎn)G和H；D有一個(gè)子結(jié)點(diǎn)I； F，G，H，I是葉結(jié)點(diǎn)，因?yàn)樗鼈儧]有子結(jié)點(diǎn)。從A到F的路徑為A-B-E-F。AECDBIHGF圖4.1 樹EBF（A）G（B）CHG（C）圖4.2 子樹 若斷掉一個(gè)結(jié)點(diǎn)與其父結(jié)點(diǎn)的連接，把該結(jié)點(diǎn)和它的子孫們單獨(dú)拿出，就是一棵以該結(jié)點(diǎn)為根結(jié)點(diǎn)

3、的樹，我們稱之為“子樹”。圖4.1.2中的（A）、（B）、（C）均是圖4.1所示樹的子樹。樹的相關(guān)術(shù)語(yǔ)1度一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)的數(shù)目，稱為該結(jié)點(diǎn)的度或次數(shù)。一棵樹的度為maxi=1, n D (i)，其中n為樹中結(jié)點(diǎn)總數(shù)，i指樹中的第i個(gè)結(jié)點(diǎn)，D(i)表結(jié)點(diǎn)i的度。2葉結(jié)點(diǎn)、分支結(jié)點(diǎn)度為0的結(jié)點(diǎn)被稱為葉結(jié)點(diǎn)；度0的結(jié)點(diǎn)被稱為分支結(jié)點(diǎn)。在圖4.1中：B有一個(gè)子結(jié)點(diǎn)E，度為1；A有三個(gè)子結(jié)點(diǎn)B、C和D（換言之，A是B、C和D的父結(jié)點(diǎn)），度為3，故這棵樹的度也為3 .3結(jié)點(diǎn)的層數(shù)樹形T中結(jié)點(diǎn)的層數(shù)遞歸定義如下： root(T)層數(shù)為零； 其余結(jié)點(diǎn)的層數(shù)為其前驅(qū)結(jié)點(diǎn)的層數(shù)加1 .AECDBIHGF層次0層

4、次1層次2層次3樹的層數(shù)4路徑樹形中結(jié)點(diǎn)間的連線被稱為邊。若樹形T中存在結(jié)點(diǎn)序列vm vm+1 vmk，1 k T的最大層數(shù)，滿足vi+1是vi（m i mk1）的子結(jié)點(diǎn)，則稱此結(jié)點(diǎn)序列為vm到vmk的路徑，該路徑所經(jīng)歷的邊數(shù)nm被稱為路徑長(zhǎng)度。5. 子孫結(jié)點(diǎn)、祖先結(jié)點(diǎn)一棵樹中若存在結(jié)點(diǎn)vm到vn的路徑，則稱vn為vm的子孫結(jié)點(diǎn)，vm為vn的祖先結(jié)點(diǎn)。 不難看出，一個(gè)結(jié)點(diǎn)到它的某個(gè)子孫結(jié)點(diǎn)有且僅有一條路徑。樹中結(jié)點(diǎn)之間的父子關(guān)系具有如下特征：（1）樹中任一結(jié)點(diǎn)都可以有零個(gè)或多個(gè)直接后繼(即子結(jié)點(diǎn))，但至多只能有一個(gè)直接前驅(qū)(即父結(jié)點(diǎn))。（2）樹中只有根結(jié)點(diǎn)無(wú)前驅(qū)，它是始結(jié)點(diǎn)；葉結(jié)點(diǎn)無(wú)后繼，它們

5、是終結(jié)點(diǎn)。（3）樹中某些結(jié)點(diǎn)之間具有父子關(guān)系或者祖先、子孫關(guān)系，祖先、子孫關(guān)系是對(duì)父子關(guān)系的擴(kuò)展，一些結(jié)點(diǎn)之間，如兄弟結(jié)點(diǎn)（同一個(gè)父親的諸子結(jié)點(diǎn)被稱為兄弟結(jié)點(diǎn)）之間就沒有這種關(guān)系。6樹的高度 樹的高度為maxi=1, n NL (i)，其中n為樹中結(jié)點(diǎn)總數(shù)，i指樹中第i個(gè)結(jié)點(diǎn)，NL(i)之值為結(jié)點(diǎn)i的層數(shù)。 樹的高度是指樹中結(jié)點(diǎn)的最大層數(shù)。7 有序樹和無(wú)序樹 樹中結(jié)點(diǎn)的各棵子樹T1,T2,是有次序的，即為有序樹，否則為無(wú)序樹。8 森林 森林是m (m0）棵互不相交的樹的集合。樹的表示 1.集合嵌套表示法2.凹入表示法3.廣義表表示法4.樹形表示法ACBDEABCDEA(B,C(D,E)ABCD

6、E1243與線性結(jié)構(gòu)的比較 線性結(jié)構(gòu) 樹結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素 根結(jié)點(diǎn) (無(wú)前驅(qū)) (無(wú)前驅(qū))最后一個(gè)數(shù)據(jù)元素 多個(gè)葉子結(jié)點(diǎn) (無(wú)后繼) (無(wú)后繼)其它數(shù)據(jù)元素 樹中其它結(jié)點(diǎn)(一個(gè)前驅(qū)、一個(gè)后繼) (一個(gè)前驅(qū)、多個(gè)后繼)樹的特點(diǎn)： 有一個(gè)總根。 沒有分枝相交。 樹有層次。樹的基本操作1、創(chuàng)建樹：CREATE_TREE(T)2、判樹空：TREEEMPTY(T)3、求根：ROOT(T) 4、求樹的高度：TREEDEPTH(T)5、 求某結(jié)點(diǎn)的兄弟: BROTHERS(T)6、求結(jié)點(diǎn)的雙親：PARENT(T)7、求結(jié)點(diǎn)的孩子：CHILD(T,e,i)8、遍歷樹：TRAVERSAL(T) 9、在樹T中搜索

7、數(shù)據(jù)域?yàn)閕tem的結(jié)點(diǎn)：SEARCH(T,item,i)4.1樹的基本概念4.2二叉樹4.3線索二叉樹4.4樹和森林4.5壓縮與哈夫曼樹4.6 應(yīng)用第四章 樹4.2二叉樹 4.2.1 二叉樹的定義和主要性質(zhì) 4.2.2 二叉樹的順序存儲(chǔ) 4.2.3 二叉樹的鏈接存儲(chǔ) 4.2.4 二叉樹的遍歷 4.2.5 二叉樹遍歷的應(yīng)用4.2.1 二叉樹的定義和主要性質(zhì)二叉樹的定義：二叉樹是結(jié)點(diǎn)的有限集合，它或者是空集，或者由一個(gè)根及兩個(gè)不相交的稱為這個(gè)根的左、右子樹的二叉樹構(gòu)成。 二叉樹的特征 （1） 二叉樹每個(gè)結(jié)點(diǎn)最多有2個(gè)子結(jié)點(diǎn)； （2） 二叉樹的子樹有左右之分。二叉樹的五種不同形態(tài) （a） （b） （

8、c） （d） （e）樹與二叉樹的主要區(qū)別：（1）二叉樹每個(gè)結(jié)點(diǎn)最多有 2 個(gè)子結(jié)點(diǎn)，樹則無(wú)此限制；（2） 二叉樹中結(jié)點(diǎn)的子樹分成左子樹和右子樹，即使某結(jié)點(diǎn)只有一棵子樹，也要指明該子樹是左子樹，還是右子樹，就是說(shuō)二叉樹是有序的；（3） 樹不能為空，即它至少有一個(gè)結(jié)點(diǎn)，而一棵二叉樹可以是空的（或者說(shuō)二叉樹可以為空集）。 含有3個(gè)結(jié)點(diǎn)的不同二叉樹 （a） （b） （c） （d） （e）二叉樹的性質(zhì)引理4.1 二叉樹中層數(shù)為i的結(jié)點(diǎn)至多有2i個(gè)，i 0。(當(dāng)根結(jié)點(diǎn)為1層時(shí)，有2i-1個(gè)結(jié)點(diǎn)。）證明：用數(shù)學(xué)歸納法。當(dāng)i=0時(shí)，僅有一個(gè)根結(jié)點(diǎn)，其層數(shù)為0，因此i=0時(shí)引理成立。假定當(dāng)i=k(k0)時(shí)引理成

9、立，即第j層至多有2k個(gè)結(jié)點(diǎn)。對(duì)于二叉樹的任意結(jié)點(diǎn)，其子結(jié)點(diǎn)個(gè)數(shù)最大為2，故第k+1層至多有 2*2k= 2k+1 個(gè)結(jié)點(diǎn)，因此當(dāng) i=k+1時(shí)，引理成立。由數(shù)學(xué)歸納法可知，對(duì)于所有的i0，均有“第 i 層上至多有 2i 個(gè)結(jié)點(diǎn)”。證畢。引理4.2 高度為k的二叉樹中至多有2k+1-1 (k 0)個(gè)結(jié)點(diǎn)。 (當(dāng)根結(jié)點(diǎn)為1層時(shí)，有2k -1個(gè)結(jié)點(diǎn)。）證明：根據(jù)引理4.1 第0層上至多有20個(gè)結(jié)點(diǎn)，第1層上至多有21個(gè)結(jié)點(diǎn), ，第k層上至多有2k個(gè)結(jié)點(diǎn),因此，高度為k的二叉樹中至多有20 21+ 2k= 2k+1-1 個(gè)結(jié)點(diǎn)。證畢。高度為k (k 1)的二叉樹中至少有k1個(gè)結(jié)點(diǎn)。含有k (k 1)

10、個(gè)結(jié)點(diǎn)的二叉樹高度至多為k1 . 有4個(gè)結(jié)點(diǎn)、高度為3的二叉樹CABD引理4.3 設(shè)T是由n個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹，其中葉子結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則有：n0n21證明：設(shè)度為1的結(jié)點(diǎn)有n1個(gè)，總結(jié)點(diǎn)個(gè)數(shù)為n，總邊數(shù)為e，則： n=n0+n1+n2 (1) e=n-1 (2) e=2n2+n1 (3) 因此，有n0+n1+n2-1=2n2+n1 n0=n2+1證畢。定義4.4 一棵非空高度為k( k 0)的滿二叉樹，是有2k+11個(gè)結(jié)點(diǎn)的二叉樹。654372981013111214151高度為k（非空）二叉樹至多有2k+11個(gè)結(jié)點(diǎn)。滿二叉樹的特點(diǎn)是： 葉結(jié)點(diǎn)都在第k層上； 每個(gè)分支

11、結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)； 葉結(jié)點(diǎn)的個(gè)數(shù)等于非葉結(jié)點(diǎn)個(gè)數(shù)加1 定義4.5 一棵包含n個(gè)結(jié)點(diǎn)高為k的二叉樹T，當(dāng)按層次順序編號(hào)T的所有結(jié)點(diǎn)，對(duì)應(yīng)于一棵高為k的滿二叉樹中編號(hào)由1至n的那些結(jié)點(diǎn)時(shí)，T被稱為完全二叉樹。65437298101具有n個(gè)結(jié)點(diǎn)高為k的完全二叉樹的特點(diǎn)是： 樹中只有最下面兩層結(jié)點(diǎn)的度可以小于2； 樹中最下面一層的結(jié)點(diǎn)都集中在該層最左邊的若干位置上（滿二叉樹意義上）； 樹中葉結(jié)點(diǎn)只能在層數(shù)最大的兩層上出現(xiàn)，即存在一個(gè)非負(fù)整數(shù)k使得樹中每個(gè)葉結(jié)點(diǎn)在第k層或第k 1層； 對(duì)樹中所有結(jié)點(diǎn)，按層次順序，用自然數(shù)從1開始編號(hào)，僅僅編號(hào)最大的非葉結(jié)點(diǎn)可以沒有右孩子，其余非葉結(jié)點(diǎn)都有兩個(gè)孩子結(jié)點(diǎn)。

12、 樹中所有結(jié)點(diǎn)對(duì)應(yīng)于高度為k的滿二叉樹中編號(hào)由1至n的那些結(jié)點(diǎn)。引理4.4 若將一顆具有n個(gè)結(jié)點(diǎn)的完全二叉樹按層次次序從1開始編號(hào)，則對(duì)編號(hào)為i (1i n)的結(jié)點(diǎn)有： 若i1，則編號(hào)為i的結(jié)點(diǎn)的父結(jié)點(diǎn)的編號(hào)為 i/2 。若2in，則編號(hào)為i的結(jié)點(diǎn)的左孩子的編號(hào)為 2i，否則 i 無(wú)左孩子。若2i+1n，則i結(jié)點(diǎn)的右孩子結(jié)點(diǎn)編號(hào)為2i+1，否則 i 無(wú)右孩子。用歸納法證明 若i=1，如果n2，則左孩子的編號(hào)顯然為2. 假定對(duì)所有滿足ji的j，已知j的左孩子編號(hào)為2j. 那么對(duì)結(jié)點(diǎn)i+1，我們證明其左孩子編號(hào)為2(i+1). 如果2(i+1)n，則由層次次序得知，i+1的左孩子之前的兩個(gè)結(jié)點(diǎn)是i

13、的左孩子和右孩子，因?yàn)閕的左孩子編號(hào)為2i(歸納假設(shè))，故i的右孩子編號(hào)為2i+1，從而i+1的左孩子編號(hào)為2i+2= 2(i+1).證畢引理4.5 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的高度是 log2n .證明： 設(shè)二叉樹高度為k，由定義知，完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)介于高度為k-1和高度為k的滿二叉樹的結(jié)點(diǎn)數(shù)之間，即有： 2k-1 n2k+1-1 從而有2kn 2k+1，即klog2n k+1，因?yàn)閗為整數(shù)，故有k= log2n .證畢請(qǐng)注意: 當(dāng)根結(jié)點(diǎn)的層數(shù)為1時(shí)，樹的高度為 log2n +1 。4.2二叉樹 4.2.1 二叉樹的定義和主要性質(zhì) 4.2.2 二叉樹的順序存儲(chǔ) 4.2.3 二叉樹的鏈接存儲(chǔ)

14、 4.2.4 二叉樹的遍歷 4.2.5 二叉樹遍歷的應(yīng)用要存儲(chǔ)一棵二叉樹，必須存儲(chǔ)其所有結(jié)點(diǎn)的數(shù)據(jù)信息、左孩子和右孩子地址，既可用順序結(jié)構(gòu)存儲(chǔ)，也可用鏈接結(jié)構(gòu)存儲(chǔ)。二叉樹的順序存儲(chǔ)是指將二叉樹中所有結(jié)點(diǎn)按層次順序存放在一塊地址連續(xù)的存儲(chǔ)空間中，同時(shí)反映出二叉樹中結(jié)點(diǎn)間的邏輯關(guān)系。4.2.2 二叉樹的順序存儲(chǔ) 對(duì)于完全二叉樹，結(jié)點(diǎn)的層次順序反映了其結(jié)構(gòu)，可按層次順序給出一棵完全二叉樹之結(jié)點(diǎn)的編號(hào)，結(jié)點(diǎn)編號(hào)恰好反映了結(jié)點(diǎn)間的邏輯關(guān)系，事實(shí)上，這就是完全二叉樹的順序存儲(chǔ)方法。 只要對(duì)二叉樹之結(jié)點(diǎn)按照層次順序進(jìn)行編號(hào)，就可利用一維數(shù)組A來(lái)存儲(chǔ)一棵含有n個(gè)結(jié)點(diǎn)的完全二叉樹，其中A1存儲(chǔ)二叉樹的根結(jié)點(diǎn)，A

15、i存儲(chǔ)二叉樹中編號(hào)為i的結(jié)點(diǎn)，并且結(jié)點(diǎn)Ai的左孩子（若存在）存放在A2i處，而Ai的右孩子（若存在）存放在A2i1處。完全二叉樹的順序存儲(chǔ) A1A2A3A4A5A6 A7 A8 A9A10941766125236270493131 23 12 66 94 17 5 70 62 49 這種順序存儲(chǔ)方式是完全二叉樹最簡(jiǎn)單、最節(jié)省空間的存儲(chǔ)方式。它實(shí)際上只存儲(chǔ)了結(jié)點(diǎn)信息域之值，而未存儲(chǔ)其左孩子和右孩子地址，通過(guò)計(jì)算可找到它的左孩子、右孩子和父結(jié)點(diǎn)，尋找子孫結(jié)點(diǎn)和祖先結(jié)點(diǎn)也非常方便。但這種方法應(yīng)用到非完全二叉樹時(shí)，卻有很多缺點(diǎn)。如果采用上述的順序存儲(chǔ)方式，按照層次順序，對(duì)非完全二叉樹之結(jié)點(diǎn)進(jìn)行編號(hào)，則

16、這時(shí)的編號(hào)不能與結(jié)點(diǎn)一一對(duì)應(yīng)。為此，先加入若干虛結(jié)點(diǎn)將其轉(zhuǎn)換成一棵“完全二叉樹”，然后再對(duì)原來(lái)的結(jié)點(diǎn)和虛結(jié)點(diǎn)統(tǒng)一編號(hào)，最后完成順序存儲(chǔ)。但這增加了用于存儲(chǔ)虛結(jié)點(diǎn)的空間。 一般二叉樹必須仿照完全二叉樹那樣存儲(chǔ)。但可能會(huì)浪費(fèi)很多存儲(chǔ)空間。一棵n個(gè)結(jié)點(diǎn)的二叉樹，最壞情況下需要2n-1個(gè)數(shù)組單元。4CB A 25731a1a2a3a4a5A B C a6a74.2二叉樹 4.2.1 二叉樹的定義和主要性質(zhì) 4.2.2 二叉樹的順序存儲(chǔ) 4.2.3 二叉樹的鏈接存儲(chǔ) 4.2.4 二叉樹的遍歷 4.2.5 二叉樹遍歷的應(yīng)用1、 二叉樹的鏈接存儲(chǔ)二叉樹諸結(jié)點(diǎn)被隨機(jī)存放在內(nèi)存空間中，結(jié)點(diǎn)之間的關(guān)系用指針說(shuō)明。

17、 二叉樹的結(jié)點(diǎn)結(jié)構(gòu) 二叉樹結(jié)點(diǎn)包含三個(gè)域：數(shù)據(jù)域data、指針域left和指針域right，其中左、右指針分別指向該結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn).leftright data 二叉樹的鏈接存儲(chǔ)結(jié)構(gòu)ADCBEFGACBEFDG三叉鏈表表示法 Left data parent right 二叉樹結(jié)點(diǎn)類的定義 TemplateClass BinTreeNode friend class BinTree ; private:BinTreeNode *left;BinTreeNode *right; public: T data; 2、鏈接存儲(chǔ)的二叉樹的實(shí)現(xiàn) BinTreeNode (const T&item,

18、 BinTreeNode *lptr=NULL, BinTreeNode *rptr=NULL): data(item),left(lptr),right(rptr) / 構(gòu)造函數(shù) BinTreeNode*GetLeft(void)const return Left; /返回左孩子 BinTreeNode*GetRight(void)const return right; /返回右孩子 void SetLeft(BinTreeNode * L) left = L; / 將左孩子更新為結(jié)點(diǎn) L void SetRight(BinTreeNode * R) right=R; /將右孩子更新為結(jié)點(diǎn)

19、R ; 二叉樹類BinTree的定義templateclass BinTree private: BinTreeNode * root; /指向根結(jié)點(diǎn) public: BinTree(BinTreeNode * t= NULL ): root(t) /構(gòu)造函數(shù) BinTree( ) Del (root)； /析構(gòu)函數(shù)刪除整棵二叉樹 BinTreeNode *Father (BinTreeNode * t, BinTreeNode* p); /在以t為根的子樹中搜索結(jié)點(diǎn)p的父結(jié)點(diǎn)int Find (BinTreeNode * & t，const T & item) const; /在以t為根的子

20、樹中查找data域?yàn)閕tem的結(jié)點(diǎn)void DelSubtree (BinTreeNode* t); / 刪除以t為根的子樹void PreOrder (BinTreeNode *t ) const ; /先根遍歷以結(jié)點(diǎn)t為根的子樹void InOrder (BinTreeNode *t) const ; /中根遍歷以t為根的子樹void PostOrder (BinTreeNode *t) const ; /后根遍歷以結(jié)點(diǎn)t為根的子樹. 二叉樹類BinTree的部分實(shí)現(xiàn) (1) 搜索父結(jié)點(diǎn)算法Father ( t, p . q )/在以t為根的二叉樹中搜索p的父結(jié)點(diǎn) F1 判斷t是否存在及p

21、是否為根結(jié)點(diǎn) IF (t=NULL OR p=t)THEN ( qNULL . RETURN ) . F2 若t為所求 IF left(t)=p OR right(t)=p THEN ( qt . RETURN). F3 遞歸調(diào)用 Father( left(t), p . qL). IF qLNULL THEN qqL . RETURN.） ELSE ( Father(right(t), p . qR). qqR) . ABDCL1L2 二叉樹類BinTree的實(shí)現(xiàn) (1) 搜索父結(jié)點(diǎn) / 私有函數(shù) father :返回父結(jié)點(diǎn)。 template BinTreeNode * BinNode :

22、 father(BinTreeNode *begin, BinTreeNode * current） 搜索父結(jié)點(diǎn)father(BinTreeNode *begin, BinTreeNode * current） BinTreeNode * temp; if( begin = = NULL) return NULL if( begin-left=current| begin-right=current) return begin; if（(temp=father(begin-left, current)!= NULL） return temp ； else return father(begin

23、-right,current); L1L2ABDFCE(2)搜索二叉樹中符合數(shù)據(jù)域條件的結(jié)點(diǎn)算法Find( t, item . q )Find1. 判斷t是否為空或?yàn)樗?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.(3)刪除結(jié)點(diǎn)t及其左右子樹算法DST ( t )DST1. t? IF t THEN RETURN

24、 .DST2. troot? IF troot THEN (Del(t) . root . RETURN. )DST3. 找t的父結(jié)點(diǎn)q pt . 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é)點(diǎn)p及其左右子樹 */Del1. p ? IF p THEN RETURN.Del2. 遞歸刪除 Del(Left (p). Del(Right (p). AVAIL p .ABECD4.2二叉樹 4

25、.2.1 二叉樹的定義和主要性質(zhì) 4.2.2 二叉樹的順序存儲(chǔ) 4.2.3 二叉樹的鏈接存儲(chǔ) 4.2.4 二叉樹的遍歷 4.2.5 二叉樹遍歷的應(yīng)用 4.2.4 二叉樹的遍歷 二叉樹的遍歷：按照一定次序訪問(wèn)二叉樹中所有結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次的過(guò)程。 二叉樹的某種（先根、中根、后根或?qū)哟危┍闅v次序是二叉樹中結(jié)點(diǎn)的一個(gè)有序序列，稱為二叉樹的先根（中根、后根或?qū)哟危┬蛄小?1. 二叉樹的遞歸遍歷算法遍歷方式先根遍歷： DLR中根遍歷： LDR后根遍歷： LRDLDR二叉樹 ABDFCE先根遍歷序列：A B C D E F中根遍歷序列： B D C A F E后根遍歷序列： D C B F E

26、 A若二叉樹為空，則空操作；否則中根遍歷左子樹；訪問(wèn)根結(jié)點(diǎn)；中根遍歷右子樹。遍歷結(jié)果 A / B *C * D +E1）中根遍歷(中序遍歷)表達(dá)式語(yǔ)法樹At例*D/E*+CB二叉樹中根遍歷算法(遞歸)算法InOrder(t)InOrder1 遞歸遍歷 IF tNULL THEN (InOrder(left(t). PRINT(data(t). InOrder(right(t).) /中序遍歷以t為根的子樹,C+實(shí)現(xiàn)void BinTree:InOrder ( BinTreeNode * t ) if ( t != NULL ) InOrder( tleft ); cout tdata; InO

27、rder ( tright ); 中序遍歷結(jié)果： A / B *C * D +EAt例*D/E*+CB出棧的條件： t0 ，子程序結(jié)束且棧不空出棧。整個(gè)程序結(jié)束的條件： 子程序結(jié)束并且棧為空。2)先根遍歷 (前/先序遍歷)若二叉樹為空，則空操作；否則訪問(wèn)根結(jié)點(diǎn)；先根遍歷左子樹；先根遍歷右子樹。表達(dá)式語(yǔ)法樹At例*D/E*+CB二叉樹先根遍歷算法(遞歸)算法PreOrder(t)PreOrder1 遞歸遍歷 IF tNULL THEN ( PRINT(data(t). PreOrder(left(t). PreOrder(right(t) ).) /先序遍歷以t為根的子樹,C+實(shí)現(xiàn)void Bi

28、nTree:PreOrder ( BinTreeNode * t ) if ( t != NULL ) cout tdata; PreOrder ( tleft ); PreOrder ( tright ); 3）后根遍歷 (后序遍歷)若二叉樹為空，則空操作；否則后根遍歷左子樹；后根遍歷右子樹；訪問(wèn)根結(jié)點(diǎn)。二叉樹后根遍歷算法(遞歸)算法PostOrder(t)PostOrder1 遞歸遍歷 IF tNULL THEN (PostOrder(left(t). PostOrder(right(t). PRINT(data(t). ) 2. 二叉樹的非遞歸遍歷算法 非遞歸的中根遍歷遞歸算法InOrd

29、er(t)InOrder1 遞歸遍歷 IF tNULL THEN (InOrder(left(t). PRINT(data(t). InOrder(right(t). ) ABECD非遞歸的中根遍歷算法算法NIO( t )NIO1. 初始化 CREATE ( S ). p t . /* CREATE(S) 創(chuàng)建一個(gè)空堆棧 */NIO2. 入棧 WHILE p DO ( S p . p Left ( p) . )NIO3. 棧為空? IF S為空 THEN RETURN. ELSE p S .NIO4. 訪問(wèn)p，更新p PRINT (Data ( p ) ). p Right ( p ). NI

30、O5. 返回 GOTO NIO2 .第 72 頁(yè)圖4.12 非遞歸中根遍歷二叉樹 (a) 二叉樹(b) 中根遍歷(a)中二叉樹, 堆棧內(nèi)容變化過(guò)程圖(b)中略去了進(jìn)棧過(guò)程的描述ABCDEFABAADCCEAF訪問(wèn)D訪問(wèn)A訪問(wèn)C訪問(wèn)FAABA進(jìn)棧B進(jìn)棧訪問(wèn)BADD進(jìn)棧CC進(jìn)棧E進(jìn)棧CE訪問(wèn)EF進(jìn)棧FNIO2. 入棧 WHILE p DO ( S p. p Left ( p).)NIO3. 棧為空? 若S為空，則 RETURN. 否則 p S .NIO4. 訪問(wèn),更新p 打印 Data(p). pRight(p). 返回NIO2第 72 頁(yè)非遞歸的先根遍歷算法，與非遞歸的中根遍歷算法類似，區(qū)別在于

31、輸出語(yǔ)句的位置不同。先根和中根遍歷的非遞歸算法，一個(gè)結(jié)點(diǎn)僅進(jìn)棧出棧一次，我們能夠判斷其輸出語(yǔ)句的位置，分別為結(jié)點(diǎn)進(jìn)棧前及出棧后。而后根遍歷輸出結(jié)點(diǎn)的位置應(yīng)為處理完右子樹之后，如果每個(gè)結(jié)點(diǎn)還是進(jìn)棧、出棧一次，則無(wú)法確定何時(shí)輸出結(jié)點(diǎn)，即其左右子樹是否已處理完。非遞歸的后根遍歷算法 設(shè)置一個(gè)工作棧： 結(jié)點(diǎn)所處狀態(tài)i = 0, 1或2： 0：結(jié)點(diǎn)及左右子樹均未被訪問(wèn)； 1：遍歷左子樹； 2：遍歷右子樹。樹中任一結(jié)點(diǎn)q都需進(jìn)棧三次，出棧三次。第一次出棧是為遍歷結(jié)點(diǎn)q的左子樹，第二次出棧是為遍歷結(jié)點(diǎn)q的右子樹，第三次出棧是為訪問(wèn)結(jié)點(diǎn)q . 結(jié)點(diǎn) 結(jié)點(diǎn)狀態(tài) i1) 將(根結(jié)點(diǎn),0)壓入堆棧。2) 彈棧，對(duì)出

32、棧元素(p, i )中標(biāo)號(hào)i進(jìn)行判斷， 若 i0，則將(p,1)壓入堆棧；若結(jié)點(diǎn)p的左指針不為空，則將(Left(p), 0) 壓入堆棧，準(zhǔn)備遍歷其左子樹.若 i1，此時(shí)已遍歷完結(jié)點(diǎn)p的左子樹，則將(p,2)壓入堆棧；若右指針不為空，則將(Right(p), 0)壓入堆棧，準(zhǔn)備遍歷其右子樹.若 i2，此時(shí)已遍歷完結(jié)點(diǎn)p的右子樹，訪問(wèn)結(jié)點(diǎn)p. 算法NPostOrder(t)NPO1建立堆棧 CREATS(S).NPO2堆棧初始化 S (t,0).NPO3利用棧實(shí)現(xiàn)遞歸 WHILE NOT(StackEmpty(S) DO ( (P,i) S. IF i=0 THEN ( S (P,1). IF

33、left(P) null THEN S (left(P),0) . ) IF i=1 THEN ( S (P,2). IF right (P) null THEN S (right(P),0). ) IF i=2 THEN PRINT(data(P) . ) 非遞歸的后根遍歷算法對(duì)左圖之二叉樹進(jìn)行后序遍歷, 棧S 之變化 訪D訪BFCABDEWHILE 棧 S 非空 DO /分別簡(jiǎn)記left、right為 Lt 和 Rt ( ( p , i ) S. IF i 0 THEN S( p , 1). 若 Lt ( p) , 則 S (Lt ( p), 0). IF i 1 THEN S( p ,

34、2). 若 Rt ( p) , 則 S (Rt ( p), 0). IF i 2 THEN PRINT (data( p). ) 第 77 頁(yè)第 77 頁(yè)由先根序列和中根序列可以唯一 確定一棵二叉樹。例 先根序列 A B C K D E H F 中根序列B K C A H E D F先根序列 A B C K D E H F 中根序列 B K C A H E D FAB CKDEHFABEDCKFHABDCKEHF由后根序列和中根序列可以唯一地確定一棵二叉樹。例 后根序列 C E F D B H G A 中根序列 C B E D F A G H后根序列 C E F D B H G A 中根序列C

35、 B E D F A G HACBEDFGHABCDEFGHABCGDEHF3、二叉樹的層次遍歷按層數(shù)由小到大，同層由左向右的次序訪問(wèn)結(jié)點(diǎn)。遍歷結(jié)果: A B E C F DABDFCE通過(guò)觀察發(fā)現(xiàn)，第i層上，若結(jié)點(diǎn)x在結(jié)點(diǎn)y的左邊，則x一定在y之前被訪問(wèn)。同理，第i+1層上，x的子結(jié)點(diǎn)一定在y的子結(jié)點(diǎn)前被訪問(wèn)。若訪問(wèn)第i層上的所有結(jié)點(diǎn)，必須知道該層上所有結(jié)點(diǎn)的地址，地址保存在其父結(jié)點(diǎn)的left和right指針中。用一個(gè)隊(duì)列來(lái)實(shí)現(xiàn)。二叉樹層次遍歷算法需要一個(gè)輔助隊(duì)列具體方法如下：根結(jié)點(diǎn)入隊(duì).重復(fù)本步驟直至隊(duì)為空:若隊(duì)非空，取隊(duì)頭結(jié)點(diǎn)并訪問(wèn)； 若其左指針不空，將其左孩子入隊(duì)； 若其右指針不空，將其右孩子入隊(duì). ABFEDC算法LevelOrder ( t )LevelOrder1. 建空隊(duì) CREATE ( Q ). LevelOrder 2. 入隊(duì) p t . IF p THEN Q p .LevelOrder 3. 層次遍歷 WHILE Q 非空 D