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

1、4.1樹的基本概念4.2二叉樹4.3線索二叉樹4.4樹和森林4.5壓縮與哈夫曼樹4.6 應(yīng)用第四章 樹樹結(jié)構(gòu)在客觀世界中大量存在，如家譜、行政組織機(jī)構(gòu)等都可用樹形象地表示。企業(yè)管理機(jī)構(gòu) 在層次中地位最高的人(此處為總裁)在圖中位置最高。在層次中地位次之的(即副總裁)在圖中位于總裁之下等等。副總裁為總裁的下屬，總裁是他們的上級。每個副總裁都有自己的下屬，而其下屬又有自己的下屬。企業(yè)管理結(jié)構(gòu) 樹在計算機(jī)領(lǐng)域也有廣泛的應(yīng)用，如:在編譯中，用樹來表示源程序的語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)中，可用樹來組織信息；在分析算法時，可用樹來描述其執(zhí)行過程；操作系統(tǒng)中，文件及文件夾的存儲，軟件工程中，軟件的菜單等都是樹。

2、 遞歸定義定義4.1： 一個樹（或樹形）就是一個有限非空的結(jié)點(diǎn)集合T，其中：有一個特別標(biāo)出的被稱為該樹（或樹形）之根root(T)的結(jié)點(diǎn)；其余結(jié)點(diǎn)（根除外）被分成m 0 個不相交的集合T1，T2，Tm，且T1，T2，Tm又都是樹（或樹形）。樹（或樹形）T1，T2，Tm被稱作root(T)的子樹（或子樹形）。一、樹的定義定義4.2 樹是包含n ( n 1 )個結(jié)點(diǎn)且滿足如下條件的有限集合：存在一個唯一的結(jié)點(diǎn)v0，它沒有前驅(qū)結(jié)點(diǎn)，稱為樹的根（或根結(jié)點(diǎn)）；任何非根結(jié)點(diǎn)都有且僅有一個前驅(qū)結(jié)點(diǎn)，稱為該結(jié)點(diǎn)的父結(jié)點(diǎn)；任何結(jié)點(diǎn)都可能有多個（ n1）后繼結(jié)點(diǎn)，稱之為該結(jié)點(diǎn)的子結(jié)點(diǎn)；若某結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)，則稱之

3、為葉結(jié)點(diǎn)。任一非根結(jié)點(diǎn)vk都有且僅有一條從v0到該結(jié)點(diǎn)的結(jié)點(diǎn)序列（或曰路徑）v0 v1 vk，其中vi是vi1（1 i k）的子結(jié)點(diǎn)。 非遞歸定義圖4.1.1為一棵由根結(jié)點(diǎn)A出發(fā)的樹，其中，A有三個子結(jié)點(diǎn)B、C和D；B有一個子結(jié)點(diǎn)E；E有一個子結(jié)點(diǎn)F；C有兩個子結(jié)點(diǎn)G和H；D有一個子結(jié)點(diǎn)I； F，G，H，I是葉結(jié)點(diǎn)，因為它們沒有子結(jié)點(diǎn)。從A到F的路徑為A-B-E-F。AECDBIHGF圖4.1.1 樹EBF（A）G（B）CHG（C）圖4.1.2 子樹 若斷掉一個結(jié)點(diǎn)與其父結(jié)點(diǎn)的連接，把該結(jié)點(diǎn)和它的子孫們單獨(dú)拿出，就是一棵以該結(jié)點(diǎn)為根結(jié)點(diǎn)的樹，我們稱之為“子樹”。圖4.1.2中的（A）、（B）、

4、（C）均是圖4.1.1所示樹的子樹。樹的相關(guān)術(shù)語1度一個結(jié)點(diǎn)的子結(jié)點(diǎn)的數(shù)目，稱為該結(jié)點(diǎn)的度或次數(shù)。一棵樹的度為maxi=1, n D (i)，其中n為樹中結(jié)點(diǎn)總數(shù)，i指樹中的第i個結(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.1中：B有一個子結(jié)點(diǎn)E，度為1；A有三個子結(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樹的層數(shù)層次3層次1層次24路徑樹形中結(jié)點(diǎn)間的連線被

5、稱為邊。若樹形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ù)k被稱為路徑長度。5. 子孫結(jié)點(diǎn)、祖先結(jié)點(diǎn)一棵樹中若存在結(jié)點(diǎn)vm到vn的路徑，則稱vn為vm的子孫結(jié)點(diǎn)，vm為vn的祖先結(jié)點(diǎn)。 不難看出，一個結(jié)點(diǎn)到它的某個子孫結(jié)點(diǎn)有且僅有一條路徑。樹中結(jié)點(diǎn)之間的父子關(guān)系具有如下特征：（1）樹中任一結(jié)點(diǎn)都可以有零個或多個直接后繼(即子結(jié)點(diǎn))，但至多只能有一個直接前驅(qū)(即父結(jié)點(diǎn))。（2）樹中只有根結(jié)點(diǎn)無前驅(qū)，它是始結(jié)點(diǎn)；葉結(jié)點(diǎn)無后繼，它們是終結(jié)點(diǎn)。（3）樹中某些結(jié)點(diǎn)之間具有父子關(guān)系或者祖先

6、、子孫關(guān)系，祖先、子孫關(guān)系是對父子關(guān)系的擴(kuò)展，一些結(jié)點(diǎn)之間，如兄弟結(jié)點(diǎn)（同一個父親的諸子結(jié)點(diǎn)被稱為兄弟結(jié)點(diǎn)）之間就沒有這種關(guān)系。6樹的高度 樹的高度為maxi=1, n NL (i)，其中n為樹中結(jié)點(diǎn)總數(shù)，i指樹中第i個結(jié)點(diǎn)，NL(i)之值為結(jié)點(diǎn)i的層數(shù)。 樹的高度是指樹中結(jié)點(diǎn)的最大層數(shù)。與線性結(jié)構(gòu)的比較 線性結(jié)構(gòu) 樹結(jié)構(gòu)第一個數(shù)據(jù)元素 根結(jié)點(diǎn) (無前驅(qū)) (無前驅(qū))最后一個數(shù)據(jù)元素 多個葉子結(jié)點(diǎn) (無后繼) (無后繼)其它數(shù)據(jù)元素 樹中其它結(jié)點(diǎn)(一個前驅(qū)、一個后繼) (一個前驅(qū)、多個后繼)樹的特點(diǎn)： 有一個總根。 沒有分枝相交。 樹有層次。樹的基本操作1、創(chuàng)建樹：CREATE_TREE(T)

7、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、插入結(jié)點(diǎn)：INSERT()10、刪除結(jié)點(diǎn)：DELETE()11、在樹T中搜索數(shù)據(jù)域為item的結(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 二叉樹的順序存儲 4.2.3 二叉樹

8、的鏈接存儲 4.2.4 二叉樹的遍歷 4.2.5 二叉樹遍歷的應(yīng)用4.2.1 二叉樹的主要性質(zhì)和定義二叉樹的定義：二叉樹是結(jié)點(diǎn)的有限集合，它或者是空集，或者由一個根及兩個不相交的稱為這個根的左、右子樹的二叉樹構(gòu)成。 二叉樹的特征 （1） 二叉樹每個結(jié)點(diǎn)最多有2個子結(jié)點(diǎn)； （2） 二叉樹的子樹有左右之分。二叉樹的五種不同形態(tài)樹與二叉樹的主要區(qū)別： 二叉樹中結(jié)點(diǎn)的子樹分成左子樹和右子樹，即使某結(jié)點(diǎn)只有一棵子樹，也要指明該子樹是左子樹，還是右子樹，就是說二叉樹是有序的；A (a) (b) (c) (d) (e)ACBACBCBACBACB 含有3個結(jié)點(diǎn)的不同二叉樹二叉樹的性質(zhì)引理4.1 二叉樹中層數(shù)

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

10、= 2k+1-1 個結(jié)點(diǎn)。證畢。高度為k (k 1)的二叉樹中至少有k1個結(jié)點(diǎn)。含有k (k 1)個結(jié)點(diǎn)的二叉樹高度至多為k1 . 有4個結(jié)點(diǎn)、高度為3的二叉樹CABD引理4.3 設(shè)T是由n個結(jié)點(diǎn)構(gòu)成的二叉樹，其中葉子結(jié)點(diǎn)個數(shù)為n0，度為2的結(jié)點(diǎn)個數(shù)為n2，則有：n0n21證明：設(shè)度為1的結(jié)點(diǎn)有n1個，總結(jié)點(diǎn)個數(shù)為n，總邊數(shù)為e，則： n=n0+n1+n2 e=n-1 (子結(jié)點(diǎn)與父結(jié)點(diǎn)的連接) e = 2n2 + n1 (所有發(fā)出分支的結(jié)點(diǎn))因此，有n0+n1+n2-1=2n2+n1 n0=n2+1證畢。定義4.4 一棵非空高度為k( k 0)的滿二叉樹，是有2k+11個結(jié)點(diǎn)的二叉樹。5643

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

12、k 1層； 對樹中所有結(jié)點(diǎn)，按層次順序，用自然數(shù)從1開始編號，僅僅編號最大的非葉結(jié)點(diǎn)可以沒有右孩子，其余非葉結(jié)點(diǎn)都有兩個孩子結(jié)點(diǎn)。 樹中所有結(jié)點(diǎn)對應(yīng)于高度為k的滿二叉樹中編號由1至n的那些結(jié)點(diǎn)。引理4.4 若將一顆具有n個結(jié)點(diǎn)的完全二叉樹按層次次序從1開始編號，則對編號為i (1i n)的結(jié)點(diǎn)有： 若i1，則編號為i的結(jié)點(diǎn)的父結(jié)點(diǎn)的編號為 i/2 。若2in，則編號為i的結(jié)點(diǎn)的左孩子的編號為 2i，否則 i 無左孩子。若2i+1n，則i結(jié)點(diǎn)的右孩子結(jié)點(diǎn)編號為2i+1，否則 i 無右孩子。用歸納法證明 若i=1，如果n2，則左孩子的編號顯然為2. 假定對所有滿足ji的j，知j的左孩子編號為2j.

13、 那么對結(jié)點(diǎn)i+1，我們證明其左孩子編號為2(i+1). 如果2(i+1)n，則由層次次序得知，i+1的左孩子之前的兩個結(jié)點(diǎn)是i的左孩子和右孩子，因為i的左孩子編號為2i(歸納假設(shè))，故i的右孩子編號為2i+1，從而i+1的左孩子編號為2i+2= 2(i+1).證畢引理4.5 具有n個結(jié)點(diǎn)的完全二叉樹的高度是 log2n .證明： 設(shè)二叉樹高度為k，由定義知，完全二叉樹的結(jié)點(diǎn)個數(shù)介于高度為k-1和高度為k的滿二叉樹的結(jié)點(diǎn)數(shù)之間，即有： 2k-1 n2k+1-1 從而有2kn 2k+1，即klog2n k+1，因為k為整數(shù)，故有k= log2n .證畢請注意: 當(dāng)根結(jié)點(diǎn)的層數(shù)從1計時，樹的高度為

14、 log2n +1 。4.2二叉樹 4.2.1 二叉樹的定義和主要性質(zhì) 4.2.2 二叉樹的順序存儲 4.2.3 二叉樹的鏈接存儲 4.2.4 二叉樹的遍歷 4.2.5 二叉樹遍歷的應(yīng)用要存儲一棵二叉樹，必須存儲其所有結(jié)點(diǎn)的數(shù)據(jù)信息、左孩子和右孩子地址，既可用順序結(jié)構(gòu)存儲，也可用鏈接結(jié)構(gòu)存儲。二叉樹的順序存儲是指將二叉樹中所有結(jié)點(diǎn)按層次順序存放在一塊地址連續(xù)的存儲空間中，同時反映出二叉樹中結(jié)點(diǎn)間的邏輯關(guān)系。4.2.2 二叉樹的順序存儲 對于完全二叉樹，結(jié)點(diǎn)的層次順序反映了其結(jié)構(gòu)，可按層次順序給出一棵完全二叉樹之結(jié)點(diǎn)的編號，結(jié)點(diǎn)編號恰好反映了結(jié)點(diǎn)間的邏輯關(guān)系，事實上，這就是完全二叉樹的順序存儲方

15、法。 只要對二叉樹之結(jié)點(diǎn)按照層次順序進(jìn)行編號，就可利用一維數(shù)組A來存儲一棵含有n個結(jié)點(diǎn)的完全二叉樹，其中A1存儲二叉樹的根結(jié)點(diǎn)，Ai存儲二叉樹中編號為i的結(jié)點(diǎn)，并且結(jié)點(diǎn)Ai的左孩子（若存在）存放在A2i處，而Ai的右孩子（若存在）存放在A2i1處。4.2.2 二叉樹的順序存儲圖4.2.5 完全二叉樹與順序存儲結(jié)構(gòu)AECDB(b) 圖(a)的順序存儲結(jié)構(gòu)A1A3A21(a) 5個結(jié)點(diǎn)的完全二叉樹EBACD2345A4A5順序存儲結(jié)構(gòu)完全二叉樹的順序存儲 A1A2A3A4A5A6 A7 A8 A9A1031 23 12 66 94 17 5 70 62 49 1712523627049316694

16、這種順序存儲方式是完全二叉樹最簡單、最節(jié)省空間的存儲方式。它實際上只存儲了結(jié)點(diǎn)信息域之值，而未存儲其左孩子和右孩子地址，通過計算可找到它的左孩子、右孩子和父結(jié)點(diǎn)，尋找子孫結(jié)點(diǎn)和祖先結(jié)點(diǎn)也非常方便。但這種方法應(yīng)用到非完全二叉樹時，卻有很多缺點(diǎn)。如果采用上述的順序存儲方式，按照層次順序，對非完全二叉樹之結(jié)點(diǎn)進(jìn)行編號，則這時的編號不能與結(jié)點(diǎn)一一對應(yīng)。為此，先加入若干虛結(jié)點(diǎn)將其轉(zhuǎn)換成一棵“完全二叉樹”，然后再對原來的結(jié)點(diǎn)和虛結(jié)點(diǎn)統(tǒng)一編號，最后完成順序存儲。但這增加了用于存儲虛結(jié)點(diǎn)的空間。由于一般二叉樹必須仿照完全二叉樹那樣存儲，可能會浪費(fèi)很多存儲空間，單支樹就是一個極端情況。4CB A 25731a1

17、a2a3a4a5A B C a6a74.2二叉樹 4.2.1 二叉樹的定義和主要性質(zhì) 4.2.2 二叉樹的順序存儲 4.2.3 二叉樹的鏈接存儲 4.2.4 二叉樹的遍歷 4.2.5 二叉樹遍歷的應(yīng)用1、 二叉樹的鏈接存儲二叉樹諸結(jié)點(diǎn)被隨機(jī)存放在內(nèi)存空間中，結(jié)點(diǎn)之間的關(guān)系用指針說明。 二叉樹的結(jié)點(diǎn)結(jié)構(gòu) 二叉樹結(jié)點(diǎn)包含三個域：數(shù)據(jù)域data、指針域left和指針域right，其中左、右指針分別指向該結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn).leftright data 二叉樹的鏈接存儲結(jié)構(gòu)ADCBEFGACBEFDG二叉樹結(jié)點(diǎn)類的定義 TemplateClass BinTreeNode friend class B

18、inTree; private:BinTreeNode *left;BinTreeNode *right; public: T data; 2、鏈接存儲的二叉樹的實現(xiàn) BinTreeNode (const T&item, 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; /返

19、回右孩子 void SetLeft(BinTreeNode * L) left = L; / 將左孩子更新為結(jié)點(diǎn) L void SetRight(BinTreeNode * R) right=R; /將右孩子更新為結(jié)點(diǎn) 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 (Bi

20、nTreeNode * t, BinTreeNode* p); /在以t為根的子樹中搜索結(jié)點(diǎn)p的父結(jié)點(diǎn)int Find (BinTreeNode * & t，const T & item) const; /在以t為根的子樹中查找data域為item的結(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 (BinTreeN

21、ode *t) const ; /后根遍歷以結(jié)點(diǎn)t為根的子樹. 二叉樹類BinTree的部分實現(xiàn) (1) 搜索父結(jié)點(diǎn)算法Father ( t, p . q )/在以t為根的二叉樹中搜索p的父結(jié)點(diǎn) F1 判斷t是否存在及p是否為根結(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 . ELSE ( Father(right(t), p .

22、 qR). qqR) . ABDCL1L2(2)搜索二叉樹中符合數(shù)據(jù)域條件的結(jié)點(diǎn)算法Find( t, item . q )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.(3)刪除結(jié)點(diǎn)t及其左右子樹算法DST ( t )DST1. t? IF t THEN RETURN .DST2

23、. 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 .ABECDL1L24.2二叉樹 4.2

24、.1 二叉樹的定義和主要性質(zhì) 4.2.2 二叉樹的順序存儲 4.2.3 二叉樹的鏈接存儲 4.2.4 二叉樹的遍歷 4.2.5 二叉樹遍歷的應(yīng)用 4.2.4 二叉樹的遍歷 二叉樹的遍歷：按照一定次序訪問二叉樹中所有結(jié)點(diǎn)，并且每個結(jié)點(diǎn)僅被訪問一次的過程。 二叉樹的某種（先根、中根、后根或?qū)哟危┍闅v次序是二叉樹中結(jié)點(diǎn)的一個有序序列，稱為二叉樹的先根（中根、后根或?qū)哟危┬蛄小?1. 二叉樹的遞歸遍歷算法遍歷方式先根遍歷： DLR中根遍歷： LDR后根遍歷： LRDLDR二叉樹1)先根遍歷 (前/先序遍歷)若二叉樹為空，則空操作；否則訪問根結(jié)點(diǎn)；先根遍歷左子樹；先根遍歷右子樹。遍歷結(jié)果- + a *

25、b - c d / e f二叉樹先根遍歷算法(遞歸)算法PreOrder(t)PreOrder1 遞歸遍歷 IF tNULL THEN ( PRINT(data(t). PreOrder(left(t). PreOrder(right(t) ).) ABDFCE/遍歷以t為根的子樹,C+實現(xiàn)void BinTree:PreOrder ( BinTreeNode * t ) if ( t != NULL ) cout tdata; PreOrder ( tleft ); PreOrder ( tright ); 若二叉樹為空，則空操作；否則中根遍歷左子樹；訪問根結(jié)點(diǎn)；中根遍歷右子樹。遍歷結(jié)果 a

26、 + b * c - d - e / f2）中根遍歷(中序遍歷)表達(dá)式語法樹二叉樹中根遍歷算法(遞歸)算法InOrder(t)InOrder1 遞歸遍歷 IF tNULL THEN (InOrder(left(t). PRINT(data(t). InOrder(right(t).) 3）后根遍歷 (后序遍歷)若二叉樹為空，則空操作；否則后根遍歷左子樹；后根遍歷右子樹；訪問根結(jié)點(diǎn)。遍歷結(jié)果a b c d - * + e f / -二叉樹后根遍歷算法(遞歸)算法PostOrder(t)PostOrder1 遞歸遍歷 IF tNULL THEN (PostOrder(left(t). PostOr

27、der(right(t). PRINT(data(t). ) ABDFCE先根遍歷序列：A B C D E F中根遍歷序列： B D C A F E后根遍歷序列： D C B F E A 2. 二叉樹的非遞歸遍歷算法 非遞歸的中根遍歷遞歸算法InOrder(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)建一個空堆棧 */NIO2. 入棧 W

28、HILE 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. 返回 GOTO NIO2 .非遞歸的先根遍歷算法，與非遞歸的中根遍歷算法類似，區(qū)別在于輸出語句的位置不同。先根和中根遍歷的非遞歸算法，一個結(jié)點(diǎn)僅進(jìn)棧出棧一次，我們能夠判斷其輸出語句的位置，分別為結(jié)點(diǎn)進(jìn)棧前及出棧后。而后根遍歷輸出結(jié)點(diǎn)的位置應(yīng)為處理完右子樹之后，如果每個結(jié)點(diǎn)還是進(jìn)棧、出棧一次，則無法確定何時輸出結(jié)點(diǎn)，即其左右子樹是否已處理完

29、。非遞歸的后根遍歷算法 設(shè)置一個工作棧： 結(jié)點(diǎn)所處狀態(tài)i = 0, 1或2： 0：結(jié)點(diǎn)及左右子樹均未被訪問； 1：遍歷左子樹； 2：遍歷右子樹。樹中任一結(jié)點(diǎn)q都需進(jìn)棧三次，出棧三次。第一次出棧是為遍歷結(jié)點(diǎn)q的左子樹，第二次出棧是為遍歷結(jié)點(diǎn)q的右子樹，第三次出棧是為訪問結(jié)點(diǎn)q . 結(jié)點(diǎn) 結(jié)點(diǎn)狀態(tài) i1) 將(根結(jié)點(diǎn),0)壓入堆棧。2) 彈棧，對出棧元素(p, i )中標(biāo)號i進(jìn)行判斷， 若 i0，則將(p,1)壓入堆棧；若結(jié)點(diǎn)p的左指針不為空，則將(Left(p), 0) 壓入堆棧，準(zhǔn)備遍歷其左子樹.若 i1，此時已遍歷完結(jié)點(diǎn)p的左子樹，則將(p,2)壓入堆棧；若右指針不為空，則將(Right(p

30、), 0)壓入堆棧，準(zhǔn)備遍歷其右子樹.若 i2，此時已遍歷完結(jié)點(diǎn)p的右子樹，訪問結(jié)點(diǎn)p. 算法NPostOrder(t)NPO1建立堆棧 CREATS(S).NPO2堆棧初始化 S (t,0).NPO3利用棧實現(xiàn)遞歸 WHILE NOT(StackEmpty(S) DO ( (P,i) S. IF i=0 THEN ( S (P,1). IF 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) .

31、 ) 非遞歸的后根遍歷算法由先根序列和中根序列可以唯一地確定一棵二叉樹。例 先根序列 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 B E D F A G HACBEDFGHABCDEFGHABCGDEHF練習(xí)： 已知某二叉樹的先序遍歷序列是ABDGCEFH

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