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