1、第5章 樹與二叉樹之三趙海燕軟件研究所14 Apr. 20052005-4-142005 Spring Data Structures by Haiyan Zhao2二叉樹（binary tree）n由結(jié)點的有限集合構(gòu)成:q或者為空集q或者由一個根結(jié)點及兩棵不相交的分別稱作這個根的左子樹和右子樹的二叉樹(它們也是結(jié)點的集合)組成n遞歸的定義。二叉樹可以是空集合，因此根可以有空的左子樹或右子樹，或者左右子樹皆為空。也即它的每一個結(jié)點至多有兩棵子樹，并且子樹有左右之分，不能隨意顛倒2005-4-142005 Spring Data Structures by Haiyan Zhao3二叉樹的基本形

2、態(tài)左子樹右子樹右子樹左子樹（1）空二叉樹（2）只有一個根結(jié)點（3）有根結(jié)點 和左子樹（4）有根結(jié)點 和右子樹（5）有根結(jié)點左、右子樹2005-4-142005 Spring Data Structures by Haiyan Zhao4二叉樹 vs 樹n二叉樹不是樹的特殊情形，它們是兩種數(shù)據(jù)結(jié)兩種數(shù)據(jù)結(jié)構(gòu)構(gòu)n 樹和二叉樹之間最主要的差別：q二叉樹中結(jié)點的子樹要區(qū)分為左子樹和右子樹區(qū)分為左子樹和右子樹，即使在結(jié)點只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹 n (3)和（4）是兩棵不同的二叉樹，但作為樹，它們是相同的n 在二叉樹中可定義類似樹中的概念2005-4-142005 Spr

3、ing Data Structures by Haiyan Zhao5滿二叉樹（Full Binary Tree）n如果一棵二叉樹的任何結(jié)點，或者是樹葉，或者恰有兩棵非空子樹，則此二叉樹稱作滿二叉樹2005-4-142005 Spring Data Structures by Haiyan Zhao6完全二叉樹（Complete Binary Tree）n若一棵二叉樹q最多只有最下面的兩層結(jié)點度數(shù)可以小于2q最下面一層的結(jié)點都集中在該層最左邊的若干位置上則稱此二叉樹為完全二叉樹n在許多算法和算法分析中都明顯地或隱含地用到完全二叉樹的概念完全二叉樹一定是滿二叉樹?2005-4-142005 Sp

4、ring Data Structures by Haiyan Zhao7擴充二叉樹（Extended Binary Tree）n當(dāng)二叉樹里出現(xiàn)空的子樹時，就增加新的、特殊的結(jié)點空樹葉q對于原來二叉樹里度數(shù)為1的分支結(jié)點，在它下面增加一個空樹葉q對于原來二叉樹的樹葉，在它下面增加兩個空樹葉n擴充的二叉樹是滿二叉樹，新增加的空樹葉(外部結(jié)點)的個數(shù)等于原來二叉樹的結(jié)點(內(nèi)部結(jié)點)個數(shù)加1 2005-4-142005 Spring Data Structures by Haiyan Zhao8擴充二叉樹n外部路徑長度E 從擴充的二叉樹的根到每個外部結(jié)點的路徑長度之和 n內(nèi)部路徑長度I 擴充的二叉樹里

5、從根到每個內(nèi)部結(jié)點的路徑長度之和 nE和I兩個量之間的關(guān)系為 E=I+2n qn 是內(nèi)部結(jié)點的個數(shù)2005-4-142005 Spring Data Structures by Haiyan Zhao9性質(zhì)性質(zhì)1. . 在非空二叉樹的第i層上至多有2i個結(jié)點（i0）證明：采用歸納法i=0, 結(jié)點數(shù)=1=20 . 假設(shè)對于j(0j i), 結(jié)點數(shù)至多有2j . 對于i=j+1,結(jié)點數(shù)至多為 2* 2j=2j+1 .二叉樹的性質(zhì)二叉樹的性質(zhì)2005-4-142005 Spring Data Structures by Haiyan Zhao10二叉樹的性質(zhì)二叉樹的性質(zhì)性質(zhì)性質(zhì)2. . 深度為 k

6、的二叉樹至多有2k+1-1個結(jié)點 （k 0）122mM1kk0iik0ii證明：假設(shè)第i層上的最大結(jié)點個數(shù)為mi，由性質(zhì)1可知，深度為k的二叉樹中最大的結(jié)點個數(shù)為2005-4-142005 Spring Data Structures by Haiyan Zhao111237612151413548111091234結(jié)點最多的二叉樹： 20+21+22+23結(jié)點最少的二叉樹： 1+1+1+1示例2005-4-142005 Spring Data Structures by Haiyan Zhao12二叉樹的性質(zhì)二叉樹的性質(zhì)性質(zhì)性質(zhì)3. 對任何一棵非空二叉樹T，如果葉結(jié)點 數(shù)為n0,度為2的結(jié)點

7、數(shù)為n2,則n0=n2+1 證明： n0+n1+n2 = 所有結(jié)點的度數(shù)和+1 = n1+ 2*n2 +1 由此可得： n0=n2+12005-4-142005 Spring Data Structures by Haiyan Zhao13性質(zhì)性質(zhì)4. 4. 具有n個結(jié)點的完全二叉樹的深度k為 log2n . 二叉樹的性質(zhì)二叉樹的性質(zhì)證明： n = 20 + 21 + 22 + + 2k-1 + mk = 2k 1 + mk 2k-1 n 2k+1-1 2k n 2k+1 k log2n k+1 k = log2n 2005-4-142005 Spring Data Structures by

8、 Haiyan Zhao14123761254811109完全二叉樹層次序列反映出它的結(jié)構(gòu)1 2 3 4 5 6 7 8 9 10 11 12完全二叉樹示例2005-4-142005 Spring Data Structures by Haiyan Zhao15性質(zhì)性質(zhì)5.5. 如果對一棵有n個結(jié)點的完全二叉樹按層次次序從1開始編號，則對任一結(jié)點i （1 in)，有： 1）i=1，序號結(jié)點i是根；i1, 其雙親結(jié)點是 i/2 2）2i n，序號為i的結(jié)點的左子女結(jié)點的序號為2i；2in ,序號為i的結(jié)點無左子女 3）2i+1 n，序號為i的結(jié)點的右子女結(jié)點的序號為2i+1; 2i+1 n,序號

9、為i的結(jié)點無右子女二叉樹的性質(zhì)二叉樹的性質(zhì)2005-4-142005 Spring Data Structures by Haiyan Zhao16證明證明: 1.對于（2）和（3）當(dāng)i=1時,若2i = 2 n，左子女結(jié)點的序號為2。2i+1 = 3 n，右子女結(jié)點的序號為3。2.假設(shè)對于序號為j的結(jié)點，命題成立。3.對于i=j+1， 其左子女結(jié)點的序號等于j的右子女結(jié)點的序號加1，即2j+1+1=2(j+1) 其右子女結(jié)點的序號等于：2(j+1)+1。4.根據(jù)（2）和（3），可知i的父結(jié)點的序號為i/2. 結(jié)論結(jié)論：完全二叉樹的層次序列，反映了它的結(jié)構(gòu)。完全二叉樹的層次序列，反映了它的結(jié)構(gòu)

10、。二叉樹的性質(zhì)二叉樹的性質(zhì)2005-4-142005 Spring Data Structures by Haiyan Zhao17123jj+1 2j 2j+1 2(j+1) 2(j+1)+1性質(zhì)性質(zhì)5的示例的示例2005-4-142005 Spring Data Structures by Haiyan Zhao18性質(zhì)性質(zhì)6.6. 在擴充的二叉樹中，新增加的外部結(jié)點個數(shù)比原來的內(nèi)部結(jié)點個數(shù)多1。二叉樹的性質(zhì)二叉樹的性質(zhì)證明證明：n 個結(jié)點的二叉樹擴充后 邊數(shù) = 2n; 結(jié)點數(shù) = 2n+1滿二叉樹定理：非空滿二叉樹樹葉數(shù)等于其分支結(jié)點數(shù)加1。2005-4-142005 Spring D

11、ata Structures by Haiyan Zhao19二叉樹的性質(zhì)二叉樹的性質(zhì)性質(zhì)性質(zhì)7 7. 對任意擴充二叉樹，外部路徑長度E和內(nèi)部路徑長度I之間滿足 E = I + 2n的關(guān)系， 其中n為內(nèi)部結(jié)點個數(shù)。2005-4-142005 Spring Data Structures by Haiyan Zhao20abcedf示例2005-4-142005 Spring Data Structures by Haiyan Zhao21二叉樹的性質(zhì)二叉樹的性質(zhì)證明證明：當(dāng)n=1時，I=0, E=2, 此等式成立。 設(shè)有n個內(nèi)部結(jié)點的擴充二叉樹，下式成立。 En = In+2n (1) 對于

12、n+1 個內(nèi)部結(jié)點的擴充二叉樹，去掉一個原來為樹葉、路徑長度為K的內(nèi)部結(jié)點，內(nèi)部路徑長度變?yōu)椋?In = In+1-K (2) 外部路徑長度變?yōu)椋?En = En+1-2(K+1)+K = En+1 -K-2 即： En+1= En+K+2 En+1 = (In+2n) +K+2 = (In+1-K) +2n+K+2 代入（1） 代入（2） = In+1+2(n+1) 2005-4-142005 Spring Data Structures by Haiyan Zhao22二叉樹的基本運算二叉樹的基本運算n二叉樹的類型：BTree；二叉樹中結(jié)點的類型：BNode。除了樹上的一般運算之外，1.

13、BNode leftchild(BNode p) 求二叉樹中某個指定結(jié)點的左子女結(jié)點，當(dāng)指定結(jié)點沒有左子女時，返回一特殊值NULL；2. BNode rightchild(BNode p) 求二叉樹中某個指定結(jié)點的右子女結(jié)點，當(dāng)指定結(jié)點沒有右子女時，返回一特殊值NULL；3. 二叉樹的周游2005-4-142005 Spring Data Structures by Haiyan Zhao23周游二叉樹n周游 系統(tǒng)地訪問數(shù)據(jù)結(jié)構(gòu)中的每個結(jié)點。每個結(jié)點都正好被訪問且僅被訪問到一次。n周游一棵二叉樹的過程實際上就是把二叉樹的結(jié)點放入一個線性序列的過程，或者說是把二叉樹進行線性化 2005-4-14

14、2005 Spring Data Structures by Haiyan Zhao24周游二叉樹的方法n深度優(yōu)先周游二叉樹（depth-first traversal）n廣度優(yōu)先周游二叉樹（breadth-first traversal）2005-4-142005 Spring Data Structures by Haiyan Zhao25深度優(yōu)先周游二叉樹n通過變換根結(jié)點的周游順序，可以得到以下三種方案： q前序周游(DLR次序)：n訪問根結(jié)點；前序周游左子樹；前序周游右子樹。q中序周游(LDR次序)，也稱對稱序周游：n中序周游左子樹；訪問根結(jié)點；中序周游右子樹。q后序周游(LRD次序)

15、：n后序周游左子樹；后序周游右子樹；訪問根結(jié)點。DLR2005-4-142005 Spring Data Structures by Haiyan Zhao26深度優(yōu)先周游二叉樹n深度周游如下二叉樹n前序周游：ABDCEGFHI n中序周游：DBAEGCHFI n后序周游：DBGEHIFCA 某種序列下的前驅(qū)/后繼2005-4-142005 Spring Data Structures by Haiyan Zhao27-+abcd表達(dá)式的二叉樹表示對右圖進行前序、后序和中序次序周游可分別得到如下的結(jié)點序列： 前序序列：-ab+cd 前綴表示(波蘭表示法) 后序序列：ab-cd+ 后綴表示(逆波

16、蘭表示法) 對稱序列：a-b c+d 中綴表示2005-4-142005 Spring Data Structures by Haiyan Zhao28二叉樹的周游算法二叉樹的周游算法n按實現(xiàn)方式分為：q遞歸算法遞歸算法 void visit(BNode p); /*p是被周游的二叉樹的結(jié)點*/q非遞歸算法非遞歸算法 算法中維持一個棧2005-4-142005 Spring Data Structures by Haiyan Zhao29深度優(yōu)先遞歸實現(xiàn)：前序次序1.訪問根； visit(p);2.按前序次序周游根的左子樹； preOrder(leftchild(p);3.按前序次序周游根的右

17、子樹; preOrder(rightchild(p); void preOrder(BNode p) if (p= =NULL) return; visit(p); preOrder(leftchild(p); preOrder(rightchild(p);2005-4-142005 Spring Data Structures by Haiyan Zhao30深度優(yōu)先遞歸實現(xiàn)：對稱序 n按對稱序周游根的左子樹；inOrder(leftchild(p);n訪問根； visit(p);n按對稱序周游根的右子樹；inOrder(rightchild(p); void inOrder(BNode p

18、) if (p= =NULL) return; inOrder(leftchild(p); visit(p); inOrder(rightchild(p);2005-4-142005 Spring Data Structures by Haiyan Zhao31深度優(yōu)先遞歸實現(xiàn)：后序次序 n按后序次序周游根的左子樹；postOrder(leftchild(p);n按后序次序周游根的右子樹；postOrder(rightchild(p);n訪問根； visit(p); void postOrder(BNode p) if (p= =NULL) return; postOrder(leftchil

19、d(p); postOrder(rightchild(p); visit(p);2005-4-142005 Spring Data Structures by Haiyan Zhao32深度優(yōu)先非遞歸實現(xiàn)：前序次序n用自定義的棧來代替系統(tǒng)的棧void preOrder(BNode p) do while (p != NULL) visit(p); push(st,p); p = leftchild(p); while (p = NULL) & (!isEmptyStack(st) p = top(st); pop(st); p = rightchild(p); while (p!=NU

20、LL | !isEmptyStack(st);2005-4-142005 Spring Data Structures by Haiyan Zhao33深度優(yōu)先非遞歸實現(xiàn)：中序次序 void inOrder(BNode p) do while (p!=NULL) push(st, p); p=leftchild(p);while (p = NULL & (!isEmptyStack(st) p = top(st); pop(st); visit(p); p=rightchild(p); while(p!=NULL | !isEmptyStack(st)2005-4-142005 Spr

21、ing Data Structures by Haiyan Zhao34深度優(yōu)先非遞歸實現(xiàn)：后序次序n每個結(jié)點要到其左、右子樹都周游完時才得訪問，所以在周游其左、右子樹之前都需進棧。當(dāng)該結(jié)點出棧時，需要判斷是q從左子樹回來（第一次：剛周游完左子樹，此時需要周游右子樹）q從右子樹回來（第二次：剛周游完右子樹，此時需要訪問該結(jié)點）因此，進棧的結(jié)點需要伴隨著一個標(biāo)記tag。 1 周游左子樹(第一次出棧） 2 周游右子樹(第二次出棧）tag =2005-4-142005 Spring Data Structures by Haiyan Zhao35DLRD.tag =1; D進棧；后序周游L;cont

22、inueflag = t ;D出棧； D.tag=2; D進棧； continueflag= f ; /*下一步要訪問右子樹R，不能退棧*/ p=rightchild(p);深度優(yōu)先非遞歸實現(xiàn)：后序次序2005-4-142005 Spring Data Structures by Haiyan Zhao36typedef struct BNode ptr; /*進棧結(jié)點*/int tag; /*標(biāo)記*/ Elem;struct Stack Elem sMAXNUM;int t; ;typedef struct Stack *PStack; /*棧的指針類型*/棧中元素的類型2005-4-142

23、005 Spring Data Structures by Haiyan Zhao37算法算法5.13 使用棧的后序次序周游算法使用棧的后序次序周游算法void nPostOrder1(BTree t) Stack st; Elem stnode; BNode p; /*當(dāng)前要處理的結(jié)點*/ char continueflag; /*標(biāo)記，是否繼續(xù)退棧*/ if (t=NULL) return; st = createEmptyStack( ); p = root(t); /*從根結(jié)點開始*/ do while (p!=NULL) stnode.ptr=p; stnode.tag=1; pus

24、h(st, stnode); p =leftchild(p); continueflag= t ; while (continueflag=t)&(! isEmptyStack(st) stnode=top(st); pop(st); p=stnode.ptr; if (stnode.tag =1) stnode.tag = 2; push(st,stnode); continueflag =f ; p=rightchild(p); else visit(p); while(!isEmptyStack(st); 2005-4-142005 Spring Data Structures

25、by Haiyan Zhao38算法算法5.14 使用棧的后序次序周游使用棧的后序次序周游n把后序次序的逆序列(DRL)壓入棧中，然后按出棧的順序訪問結(jié)點void postOrder2(BTree t) Stack st; BNode p; if (t=NULL) return; st = createEmptyStack(); p = root(t); stackchild(st, p); / 把后序次序的逆序列推入棧 while (!isEmptyStack(st) visit(top(st); pop(st);2005-4-142005 Spring Data Structures by

26、 Haiyan Zhao39void stackchild(Stack st, BNode p) if (p=NULL) return; push(st, p); if (rightchild(p) != NULL) stackchild(st, rightchild(p); if (leftchild(p) != NULL) stackchild(st, leftchild(p);算法5.14 使用棧的后序次序周游DLR2005-4-142005 Spring Data Structures by Haiyan Zhao40非遞歸方式周游二叉樹n優(yōu)點：減少了遞歸調(diào)用的開銷n缺點：程序員需要決

27、定棧的大小q（太小容易發(fā)生棧溢出，太大浪費）2005-4-142005 Spring Data Structures by Haiyan Zhao41廣度優(yōu)先周游二叉樹 （breadth-first）n從二叉樹的第一層（根結(jié)點）開始，自上至下逐層遍歷；在同一層中，按照從左到右的順序?qū)Y(jié)點逐一訪問 n例如：ABCDEFGHIn適用于完全二叉樹等2005-4-142005 Spring Data Structures by Haiyan Zhao42樹/樹林與二叉樹的轉(zhuǎn)換n在樹或樹林與二叉樹之間有一個自然的一一對應(yīng)的關(guān)系q任何樹林都唯一地對應(yīng)到一棵二叉樹；反過來，任何二叉樹也都唯一地對應(yīng)到一個樹林樹、樹林二叉樹2005-4-142005 Spring Data Structures by Haiyan Zhao43樹、樹林轉(zhuǎn)換為二叉樹n 執(zhí)行步驟：（1）在所有相鄰的兄弟結(jié)點之間連一條線；（2）對每個非終端結(jié)點，只保留它到其最左子女的連線，刪去它與其它子女的連線；（3）以根結(jié)點為軸心，將整棵樹進行旋轉(zhuǎn)。2005-4-142005 Spring Data Structure