第5章樹與二叉樹PPT課件

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

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

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

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

5、從根到每個(gè)內(nèi)部結(jié)點(diǎn)的路徑長(zhǎng)度之和 nE和I兩個(gè)量之間的關(guān)系為 E=I+2n qn 是內(nèi)部結(jié)點(diǎn)的個(gè)數(shù)2005-4-142005 Spring Data Structures by Haiyan Zhao9性質(zhì)性質(zhì)1. . 在非空二叉樹的第i層上至多有2i個(gè)結(jié)點(diǎn)（i0）證明：采用歸納法i=0, 結(jié)點(diǎn)數(shù)=1=20 . 假設(shè)對(duì)于j(0j i), 結(jié)點(diǎn)數(shù)至多有2j . 對(duì)于i=j+1,結(jié)點(diǎn)數(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個(gè)結(jié)點(diǎn) （k 0）122mM1kk0iik0ii證明：假設(shè)第i層上的最大結(jié)點(diǎn)個(gè)數(shù)為mi，由性質(zhì)1可知，深度為k的二叉樹中最大的結(jié)點(diǎn)個(gè)數(shù)為2005-4-142005 Spring Data Structures by Haiyan Zhao111237612151413548111091234結(jié)點(diǎn)最多的二叉樹： 20+21+22+23結(jié)點(diǎn)最少的二叉樹： 1+1+1+1示例2005-4-142005 Spring Data Structures by Haiyan Zhao12二叉樹的性質(zhì)二叉樹的性質(zhì)性質(zhì)性質(zhì)3. 對(duì)任何一棵非空二叉樹T，如果葉結(jié)點(diǎn) 數(shù)為n0,度為2的結(jié)點(diǎn)

7、數(shù)為n2,則n0=n2+1 證明： n0+n1+n2 = 所有結(jié)點(diǎn)的度數(shù)和+1 = n1+ 2*n2 +1 由此可得： n0=n2+12005-4-142005 Spring Data Structures by Haiyan Zhao13性質(zhì)性質(zhì)4. 4. 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度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. 如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹按層次次序從1開始編號(hào)，則對(duì)任一結(jié)點(diǎn)i （1 in)，有： 1）i=1，序號(hào)結(jié)點(diǎn)i是根；i1, 其雙親結(jié)點(diǎn)是 i/2 2）2i n，序號(hào)為i的結(jié)點(diǎn)的左子女結(jié)點(diǎn)的序號(hào)為2i；2in ,序號(hào)為i的結(jié)點(diǎn)無(wú)左子女 3）2i+1 n，序號(hào)為i的結(jié)點(diǎn)的右子女結(jié)點(diǎn)的序號(hào)為2i+1; 2i+1 n,序號(hào)

9、為i的結(jié)點(diǎn)無(wú)右子女二叉樹的性質(zhì)二叉樹的性質(zhì)2005-4-142005 Spring Data Structures by Haiyan Zhao16證明證明: 1.對(duì)于（2）和（3）當(dāng)i=1時(shí),若2i = 2 n，左子女結(jié)點(diǎn)的序號(hào)為2。2i+1 = 3 n，右子女結(jié)點(diǎn)的序號(hào)為3。2.假設(shè)對(duì)于序號(hào)為j的結(jié)點(diǎn)，命題成立。3.對(duì)于i=j+1， 其左子女結(jié)點(diǎn)的序號(hào)等于j的右子女結(jié)點(diǎn)的序號(hào)加1，即2j+1+1=2(j+1) 其右子女結(jié)點(diǎn)的序號(hào)等于：2(j+1)+1。4.根據(jù)（2）和（3），可知i的父結(jié)點(diǎn)的序號(hào)為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. 在擴(kuò)充的二叉樹中，新增加的外部結(jié)點(diǎn)個(gè)數(shù)比原來(lái)的內(nèi)部結(jié)點(diǎn)個(gè)數(shù)多1。二叉樹的性質(zhì)二叉樹的性質(zhì)證明證明：n 個(gè)結(jié)點(diǎn)的二叉樹擴(kuò)充后 邊數(shù) = 2n; 結(jié)點(diǎn)數(shù) = 2n+1滿二叉樹定理：非空滿二叉樹樹葉數(shù)等于其分支結(jié)點(diǎn)數(shù)加1。2005-4-142005 Spring D

11、ata Structures by Haiyan Zhao19二叉樹的性質(zhì)二叉樹的性質(zhì)性質(zhì)性質(zhì)7 7. 對(duì)任意擴(kuò)充二叉樹，外部路徑長(zhǎng)度E和內(nèi)部路徑長(zhǎng)度I之間滿足 E = I + 2n的關(guān)系， 其中n為內(nèi)部結(jié)點(diǎn)個(gè)數(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時(shí)，I=0, E=2, 此等式成立。 設(shè)有n個(gè)內(nèi)部結(jié)點(diǎn)的擴(kuò)充二叉樹，下式成立。 En = In+2n (1) 對(duì)于

12、n+1 個(gè)內(nèi)部結(jié)點(diǎn)的擴(kuò)充二叉樹，去掉一個(gè)原來(lái)為樹葉、路徑長(zhǎng)度為K的內(nèi)部結(jié)點(diǎn)，內(nèi)部路徑長(zhǎng)度變?yōu)椋?In = In+1-K (2) 外部路徑長(zhǎng)度變?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二叉樹的基本運(yùn)算二叉樹的基本運(yùn)算n二叉樹的類型：BTree；二叉樹中結(jié)點(diǎn)的類型：BNode。除了樹上的一般運(yùn)算之外，1.

13、BNode leftchild(BNode p) 求二叉樹中某個(gè)指定結(jié)點(diǎn)的左子女結(jié)點(diǎn)，當(dāng)指定結(jié)點(diǎn)沒有左子女時(shí)，返回一特殊值NULL；2. BNode rightchild(BNode p) 求二叉樹中某個(gè)指定結(jié)點(diǎn)的右子女結(jié)點(diǎn)，當(dāng)指定結(jié)點(diǎn)沒有右子女時(shí)，返回一特殊值NULL；3. 二叉樹的周游2005-4-142005 Spring Data Structures by Haiyan Zhao23周游二叉樹n周游 系統(tǒng)地訪問(wèn)數(shù)據(jù)結(jié)構(gòu)中的每個(gè)結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)都正好被訪問(wèn)且僅被訪問(wèn)到一次。n周游一棵二叉樹的過(guò)程實(shí)際上就是把二叉樹的結(jié)點(diǎn)放入一個(gè)線性序列的過(guò)程，或者說(shuō)是把二叉樹進(jìn)行線性化 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通過(guò)變換根結(jié)點(diǎn)的周游順序，可以得到以下三種方案： q前序周游(DLR次序)：n訪問(wèn)根結(jié)點(diǎn)；前序周游左子樹；前序周游右子樹。q中序周游(LDR次序)，也稱對(duì)稱序周游：n中序周游左子樹；訪問(wèn)根結(jié)點(diǎn)；中序周游右子樹。q后序周游(LRD次序)

15、：n后序周游左子樹；后序周游右子樹；訪問(wèn)根結(jié)點(diǎn)。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á)式的二叉樹表示對(duì)右圖進(jìn)行前序、后序和中序次序周游可分別得到如下的結(jié)點(diǎn)序列： 前序序列：-ab+cd 前綴表示(波蘭表示法) 后序序列：ab-cd+ 后綴表示(逆波

16、蘭表示法) 對(duì)稱序列：a-b c+d 中綴表示2005-4-142005 Spring Data Structures by Haiyan Zhao28二叉樹的周游算法二叉樹的周游算法n按實(shí)現(xiàn)方式分為：q遞歸算法遞歸算法 void visit(BNode p); /*p是被周游的二叉樹的結(jié)點(diǎn)*/q非遞歸算法非遞歸算法 算法中維持一個(gè)棧2005-4-142005 Spring Data Structures by Haiyan Zhao29深度優(yōu)先遞歸實(shí)現(xiàn)：前序次序1.訪問(wèn)根； 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)先遞歸實(shí)現(xiàn)：對(duì)稱序 n按對(duì)稱序周游根的左子樹；inOrder(leftchild(p);n訪問(wèn)根； visit(p);n按對(duì)稱序周游根的右子樹；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)先遞歸實(shí)現(xiàn)：后序次序 n按后序次序周游根的左子樹；postOrder(leftchild(p);n按后序次序周游根的右子樹；postOrder(rightchild(p);n訪問(wè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)先非遞歸實(shí)現(xiàn)：前序次序n用自定義的棧來(lái)代替系統(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)先非遞歸實(shí)現(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)先非遞歸實(shí)現(xiàn)：后序次序n每個(gè)結(jié)點(diǎn)要到其左、右子樹都周游完時(shí)才得訪問(wèn)，所以在周游其左、右子樹之前都需進(jìn)棧。當(dāng)該結(jié)點(diǎn)出棧時(shí)，需要判斷是q從左子樹回來(lái)（第一次：剛周游完左子樹，此時(shí)需要周游右子樹）q從右子樹回來(lái)（第二次：剛周游完右子樹，此時(shí)需要訪問(wèn)該結(jié)點(diǎn)）因此，進(jìn)棧的結(jié)點(diǎn)需要伴隨著一個(gè)標(biāo)記tag。 1 周游左子樹(第一次出棧） 2 周游右子樹(第二次出棧）tag =2005-4-142005 Spring Data Structures by Haiyan Zhao35DLRD.tag =1; D進(jìn)棧；后序周游L;cont

22、inueflag = t ;D出棧； D.tag=2; D進(jìn)棧； continueflag= f ; /*下一步要訪問(wèn)右子樹R，不能退棧*/ p=rightchild(p);深度優(yōu)先非遞歸實(shí)現(xiàn)：后序次序2005-4-142005 Spring Data Structures by Haiyan Zhao36typedef struct BNode ptr; /*進(jìn)棧結(jié)點(diǎn)*/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é)點(diǎn)*/ char continueflag; /*標(biāo)記，是否繼續(xù)退棧*/ if (t=NULL) return; st = createEmptyStack( ); p = root(t); /*從根結(jié)點(diǎn)開始*/ 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)壓入棧中，然后按出棧的順序訪問(wèn)結(jié)點(diǎn)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ǎn)：減少了遞歸調(diào)用的開銷n缺點(diǎn)：程序員需要決

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