數(shù)據(jù)結(jié)構(gòu)與算法 -第十二講,北方民族大學(xué) 計算機(jī)科學(xué)與工程學(xué)院 王倫津 研究員,二叉樹的性質(zhì)及其遍歷,12、二叉樹的性質(zhì)及二叉樹的遍歷,本講給出二叉樹基本性質(zhì)的七個定理的證明，介紹二叉樹的前序遍歷、中序遍歷、后序遍歷和層序遍歷思想，和二叉樹的存儲結(jié)構(gòu)。 本講的基本要求是：掌握二叉樹的性質(zhì)及其遍歷思想,目 錄,12.1二叉樹的基本性質(zhì) 12.1.1 定理1 滿二叉樹第i層上恰有2i-1個結(jié)點(diǎn)。（i1） 12.1.2 定理2 二叉樹的第i層上結(jié)點(diǎn)個數(shù)不超過2i-1 個。 （i1） 12.1.3 定理3 深度為k的滿二叉樹有2k-1個結(jié)點(diǎn)。 12.1.4 定理4 深度為k的二叉樹，至多有2k-1 個結(jié)點(diǎn)。 12.1.5 定理5 對任意一棵二叉樹，有n0=n2+1,n=2n0+n1-1,其中，n0,n1和n2分別為度為0、1和2的結(jié)點(diǎn)的數(shù)目，n 表示結(jié)點(diǎn)總數(shù)。 12.1.6 定理6 具有n個結(jié)點(diǎn)的二叉樹的深度為log2n+1。,12.2 二叉樹的遍歷 12.3 二叉樹的存儲結(jié)構(gòu) 12.3.1 順序存儲結(jié)構(gòu) 12.3.2 鏈?zhǔn)酱鎯?12.1.7 定理7 若對一棵有n個結(jié)點(diǎn)的順序二叉樹的結(jié)點(diǎn)按層序編號，則對任一結(jié)點(diǎn)i(1in)，有（1）若i=1， 則結(jié)點(diǎn)i是根，無父親；若i1，則其父親是結(jié)點(diǎn)i/2。（2）若2in,則結(jié)點(diǎn)i無左兒子（從而也無右兒子，為葉子）；否則i的左兒子是結(jié)點(diǎn)2i。（3）若2i+1n，則結(jié)點(diǎn)i無右兒子；否則右兒子是結(jié)點(diǎn)2i+1。,12.1 二叉樹的基本性質(zhì),證：使用歸納法。i=1時，結(jié)論顯然成立。設(shè)i=k時結(jié)論成立，則考慮i=k+1的情形。由于(k+1)層上結(jié)點(diǎn)是k層上結(jié)點(diǎn)的兒子，而且滿二叉樹每個非葉子結(jié)點(diǎn)恰好有兩個兒子，故(k+1)層上結(jié)點(diǎn)個數(shù)為k層上結(jié)點(diǎn)個數(shù)的2倍，即22k-1 = 2k = 2(k+1)-1. 這表明，i=k+1時結(jié)論也成立。由歸納法原理，結(jié)論對任意的k都成立，證畢。,定理 1：滿二叉樹第i層上恰好有2i-1個結(jié)點(diǎn)(i1).,證：結(jié)點(diǎn)總數(shù) （定理 1） 2k-1.證畢。,定理 2：二叉樹的第i層上結(jié)點(diǎn)個數(shù)不超過2i-1.(i1).,事實上，這是定理 1的直接推論，因為任何二叉樹，只有滿二叉樹的結(jié)點(diǎn)最多。,定理 3：深度為k的滿二叉樹有2k-1個結(jié)點(diǎn)。,證：顯然，n=n0+n1+n2 另一方面，由于二叉樹除根外每個結(jié)點(diǎn)恰好有一個前趨，所以，非根結(jié)點(diǎn)恰與分枝一一對應(yīng)，故有 n=B+1 （分支實際上就是樹中的連線） 這里，B為分枝數(shù)目。又分枝是由度為1和2的結(jié)點(diǎn)射出的，故有 B=n1+2n2 結(jié)合上面三式，即可導(dǎo)出n0=n2+1與n=2n0+n1-1,定理 4：深度為k的二叉樹，至多有(2k-1)個結(jié)點(diǎn)。,此乃定理 3的直接推論。,定理 5：對任一棵二叉樹，有 n0=n2+1 n=2n0+n1-1 這里，n0、n1和n2分別為度為0、1和2的結(jié)點(diǎn)的數(shù)目，n表示結(jié)點(diǎn)總數(shù)。,證：設(shè)k為順序二叉樹的深度，由定理 4知 n 2k-1 由于這里n與2k均為整數(shù)，故nlog2n (a） 另一方面，由于是順序二叉樹，去掉最后一層后必為滿二叉樹，故(k-1)層以上結(jié)點(diǎn)總數(shù)為2k-1-1，因此有n2k-1-1。由于n與2k-1均為整數(shù)，為2k-1-1加一后，有可能與n相等，但不會變得大于n，故n2k-1，即 klog2n+1 (b ) 現(xiàn)在，我們已得到(a)與（b）兩式，即 log2n klog2n+1 由于k為整數(shù)，故必有k=log2n+1（見圖 120）,定理 6：具有n個結(jié)點(diǎn)的順序二叉樹的深度為log2n+1（這里，符號x表示不大于x的最大整數(shù)）。,定理 7：若對一棵順序二叉樹的結(jié)點(diǎn)按層序編號（即從根所在層起，依次從層號較小的層到層號較大的層、同層從左到右，給各結(jié)點(diǎn)依次編以連續(xù)的號碼），則對任一結(jié)點(diǎn)i（1in，n為結(jié)點(diǎn)數(shù)目，1為根的編號），有 (a)若i=1，則結(jié)點(diǎn)i是根，無父親，若i1，則其父親的編號為i/2; (b)若2in，則結(jié)點(diǎn)i無左兒子(從而也無右兒，為葉子)，否則i的左兒子的編號為2i。 (c)若2i+1n，則結(jié)點(diǎn)i無右孩子，否則它的右孩子結(jié)點(diǎn)的編號為2i+1。,11,9,10,上述是兩種順序二叉樹，從根結(jié)點(diǎn)開始編號，我們發(fā)現(xiàn)所有左結(jié)點(diǎn)編號均為偶數(shù)，所有右結(jié)點(diǎn)均為奇數(shù)。還有兩種順序二叉樹一種就是滿二叉樹，一種是缺一個元素即為滿二叉樹的情況。它們的編號同樣滿足上面的規(guī)律。,證：先證(b)和(c)，用歸納法。當(dāng)i=1時，結(jié)論是顯然的。現(xiàn)設(shè)i=k時結(jié)論(b)成立，考慮i=k+1的情形。若k結(jié)點(diǎn)無左兒子或無右兒子，則(k+1)亦必為葉子（否則就不是順序二叉樹了），故證明(b)時無需考慮此情況，而只需考慮k有兩個兒子的情況。先考慮k與k+1在同一層上，則由順序二叉樹的結(jié)構(gòu)知，若(k+1)有兒子，則必然出現(xiàn)在下一層上k的兩個兒子的緊右邊，由于k的兩個兒子的編號為2k與2k+1（歸納假設(shè)），故(k+1)若有左兒子，則編號為(2k+1)+1即2(k+1)，這表示i=k+1時結(jié)論成立；,若k+1有右兒子（當(dāng)然也有左兒子），則編號為(2k+1)+2，即2(k+1)+1，這表明(iii)在k+1時仍成立。再考慮k與k+1不在同一層的情況，此時，k必在它所在層的最右，而k+1必在下一層的最左，由于順序二叉樹編號是編完上層最右結(jié)點(diǎn)時從下層最左結(jié)點(diǎn)起編號，所以若k+1有兒子，則編號必然為(2i+1)+1與(2i+1)+2，這與k與k+1位于同層的情況相同。至于(a)，則可由(b)與(c)的式子變換而來，證畢。,12.2 二叉樹的遍歷的概念,(一) 基本概念 遍歷就是無重復(fù)無遺漏的訪問。對于樹的遍歷，是指 按一定方式訪問樹中的結(jié)點(diǎn)，使得每個結(jié)點(diǎn)恰好被訪問 一次。訪問方式是指訪問次序。假定執(zhí)行訪問機(jī)構(gòu)是單處理機(jī)的，任何時刻只能對一個目標(biāo)進(jìn)行訪問， 所以，訪問的軌跡是被訪問結(jié)點(diǎn)的線性序列，即遍歷 結(jié)果是樹中各結(jié)點(diǎn)按某種次序的一個線性序列。通過遍 歷，非線性結(jié)構(gòu)被映射成了線性結(jié)構(gòu)。,二叉樹的遍歷方式有前序遍歷、中序遍歷、后序遍歷與層序遍歷四種，現(xiàn)分述如下。,二叉樹前序遍歷定義為： 若樹為空，則不作任何動作，返回，否則，先訪問根結(jié)點(diǎn)，然后按前序方式分別遍歷根的左子樹和右子樹。 簡言之，前序遍歷是按“根左子樹右子樹”的次序遍歷二叉樹。顯然，這是個遞歸定義，下面的中序遍歷和后序遍歷也是按遞歸方式定義的。前序遍歷實例見圖 121.,前序遍歷結(jié)果：1 2 4 5 3 6 7,圖12 1 二叉樹遍歷示例,(二) 前序遍歷,7,簡言之，中序遍歷是按“左子樹根右子樹”的次序遍歷樹。其實例見圖 121,(三) 中序遍歷,二叉樹中序遍歷定義為： 若樹為空，則不作任何動作，返回，否則，先按中序方式遍歷根的左子樹，然后訪問根，最后再按中序方式遍歷根的右子樹。,中序遍歷結(jié)果：2 5 4 1 3 7 6,簡言之，后序遍歷是按“左子樹右子樹根”的次序遍歷二叉樹。其實例見圖121.,(四) 后序遍歷,二叉樹后序遍歷定義為： 若樹為空，則不作任何動作，返回，否則，先分別按后序遍歷方式遍歷根的左子樹與右子樹，然后訪問根。,7,后序遍歷結(jié)果：5 4 2 7 6 3 1,實例見圖,(五) 層序遍歷,層序遍歷是按樹的層序編號的次序訪問各結(jié)點(diǎn)，即按從上層到下層，同層內(nèi)從左到右的次序訪問結(jié)點(diǎn)。,層序遍歷結(jié)果：1 2 3 4 6 5 7,遍歷是樹結(jié)構(gòu)的一種重要的操作（我們在后面還要給出一般樹的遍歷的概念），許多對樹的操作，都是基于遍歷的。另外，遍歷也是樹的一種串行化，即將樹中結(jié)點(diǎn)按某種方式線性輸出。,在前三種方式的定義中，采用了遞歸描述方式，這種描述方式簡潔而準(zhǔn)確。但注意這種描述必須有始基。在上面的定義中，始基就是“若樹為空，則不做任何動作”，若無此句，所定義的遍歷將是個無限動作。,12.3二叉樹的存儲結(jié)構(gòu),二叉樹存儲結(jié)構(gòu)應(yīng)能體現(xiàn)二叉樹的邏輯關(guān)系，即單前驅(qū)多后繼的關(guān)系。在具體的應(yīng)用中，可能要求從任一結(jié)點(diǎn)能直接訪問到它的后繼（即兒子），或直接訪問到它的前驅(qū)（父親），或同時直接訪問父親和兒子。所以，存儲結(jié)構(gòu)的設(shè)計，要按這些要求進(jìn)行。,12.3.1順序存儲結(jié)構(gòu),(一) 順序二叉樹的順序存儲結(jié)構(gòu) 這種存儲結(jié)構(gòu)是按結(jié)點(diǎn)的層序編號的次序，將結(jié)點(diǎn)存儲在一片連續(xù)存儲區(qū)域內(nèi)。由定理 7知，對順序二叉樹，若已知結(jié)點(diǎn)的層序編號，則可推算出它的父親和兒子的編號，所以，在這種存儲結(jié)構(gòu)中，很容易根據(jù)結(jié)點(diǎn)的相對地址計算出它的父親和兒子的相對地址，方法是： x的相對地址x的編號x的父親/兒子的編號(性質(zhì)7) x的父親/兒子的相對地址。,至于結(jié)點(diǎn)的相對地址與編號之間的換算，有下列關(guān)系： 結(jié)點(diǎn)相對地址 = （結(jié)點(diǎn)編號 1）每個結(jié)點(diǎn)所占單元數(shù)目,圖 122給出了這種存儲結(jié)構(gòu)的示例。這種存儲方式，邏輯結(jié)構(gòu)用存儲次序體現(xiàn)，故若不進(jìn)行插入與刪除操作，是一種很經(jīng)濟(jì)的存儲方式,(二) 一般二叉樹的順序存儲,由于定理 7只對順序二叉樹（包括滿二叉樹）成立，所以，對一般的二叉樹而言，若要利用定理 7訪問一個結(jié)點(diǎn)的父親與兒子，則需在該二叉樹中補(bǔ)設(shè)一些虛結(jié)點(diǎn)，使它成為一棵順序二叉樹，然后對結(jié)點(diǎn)按層序編號。這樣處理后，再按順序二叉樹的順序存儲方式存儲。這種帶虛結(jié)點(diǎn)的樹，虛結(jié)點(diǎn)也要對應(yīng)存儲位置，但要設(shè)立虛結(jié)點(diǎn)標(biāo)志。,這種存儲方式中，實結(jié)點(diǎn)是不連續(xù)出現(xiàn)的，所以，若虛結(jié)點(diǎn)對應(yīng)的存儲位置不能被利用，則是一種很大的浪費(fèi)（虛結(jié)點(diǎn)數(shù)目可能很大），圖 123給出了這種存儲結(jié)構(gòu)的示例。,12.3.2 鏈?zhǔn)酱鎯?二叉樹一般多采用鏈?zhǔn)酱鎯Α＿@種存儲方式的基本思想是，令每個樹結(jié)點(diǎn)對應(yīng)一個鏈結(jié)點(diǎn)，鏈結(jié)點(diǎn)除存放與樹結(jié)點(diǎn)有關(guān)的信息外，還要根據(jù)具體應(yīng)用的需要設(shè)置指示父親、兒子的指針。根據(jù)指針設(shè)置情況，存儲方式分為一指針式、二指針式和三指針式。,為每個結(jié)點(diǎn)只設(shè)立指向其前驅(qū)的指針。由于每個結(jié)點(diǎn)的前驅(qū)是唯一的，故每個結(jié)點(diǎn)只需設(shè)一個前驅(qū)指針。在樹中，前驅(qū)稱為父親，所以這種方式也稱父指針式。 顯然，這種存儲方式下，已知某結(jié)點(diǎn)的指針，很容易找到它的父親，但要找到它的兒子，需從葉子起搜索，很耗時。另一問題是，雖可知道兒子，但不能區(qū)分是左兒還是右兒。,(一) 一指針式,為了解決該問題，可在結(jié)點(diǎn)上設(shè)立左右兒標(biāo)志位。因此，一指針式存儲在存儲了左右兒標(biāo)志的情況下，是關(guān)系完備的（即存儲了全部關(guān)系信息）。 對一指針結(jié)構(gòu)，只有知道每個葉子的地址，才能訪問到一棵樹中的每個結(jié)點(diǎn)。因此，需要將一棵樹中各個葉子的地址記錄下來。為此，對每棵樹，設(shè)立一個數(shù)組，將各葉子地址分別保存在數(shù)組的各個元素中。一指針式的結(jié)點(diǎn)結(jié)構(gòu)如圖 124(a)，示例如圖 125(b)。,這種方法是，為每個結(jié)點(diǎn)只設(shè)立指向其后繼的指針。由于二叉樹每個結(jié)點(diǎn)的后繼最多有兩個，故每個結(jié)點(diǎn)需設(shè)二個后繼指針，分別稱為左兒指針和右兒指針。 顯然，在這種儲存方式下，從根出發(fā)可以訪問到所有結(jié)點(diǎn)，所以，記錄下根的地址后，就可以訪問到各個元素。因此，二指針式在已知根的情況下，是關(guān)系完備的。 雖然已知某結(jié)點(diǎn)的指針，很容易找到它的兒子，但要找到它的父親，一般需從根起搜索，很耗時。二指針式的結(jié)點(diǎn)結(jié)構(gòu)如圖 124 (b) ，示例如圖 125 (c)。,(二)二指針式,三指針式是一指針和二指針的結(jié)合，即每個結(jié)點(diǎn)分別設(shè)立三個指針，分別指向其前驅(qū)和兩個后繼。三指針式同時具有一指針和二指針的的優(yōu)點(diǎn)，當(dāng)然是通過存儲空間換來的。三指針式的結(jié)點(diǎn)結(jié)構(gòu)如圖 124 (c)，示例如圖 125 (d)。 顯然，三指針式在關(guān)系存儲方面有冗余（我們前面已指出，二指針是關(guān)系完備的）。與普通鏈?zhǔn)酱鎯σ粯樱鏄涞逆準(zhǔn)酱鎯σ布瓤梢允恰办o態(tài)”的，也可以是“動態(tài)”的。不過，由于動態(tài)鏈?zhǔn)礁嗟仉[蔽了存儲管理細(xì)節(jié)，使我們能用更多的精力考慮其他問題，所以，我們下面一般以動態(tài)為主。當(dāng)然，也將適當(dāng)介紹靜態(tài)方法。,(三)三指針式,下面給出二叉樹結(jié)點(diǎn)（三指針）的數(shù)據(jù)部分的C+描述。關(guān)于它的完整對象描述，將在后面給出。 template /對樹結(jié)點(diǎn)內(nèi)容使用可變類型 struct TBinTreeNode TElem info; /樹結(jié)點(diǎn)內(nèi)容，類型為可變類型（類模板） TBinTreeNode *father; /父