1、第4章 樹與二叉樹,清華大學(xué)計算機(jī)系 殷人昆,數(shù)據(jù)結(jié)構(gòu)課件,第四章 樹與二叉樹,層層疊疊 縱向展開 化復(fù)雜為簡單的參天大樹,202-2,樹的定義與基本概念 二叉樹 二叉樹遍歷 二叉樹的計數(shù) 線索二叉樹 樹與樹的遍歷 樹的應(yīng)用,第 4 章 樹與二叉樹,202-3,樹和森林的概念,樹的定義 樹是由n (n0) 個結(jié)點(diǎn)組成的有限集合： 有一個特定的稱之為根(root)的結(jié)點(diǎn)； 除根以外的其它結(jié)點(diǎn)劃分為 m (m0) 個 互不相交的有限集合T1, T2, , Tm，每個集合又是一棵樹，并且稱之為根的子樹。 此定義是離散數(shù)學(xué)和圖論中給出的。它們把樹視為圖的一個極小連通子圖。有 n 個結(jié)點(diǎn)的樹有 n-1

2、條邊，而且不能有回路。,202-4,這種觀點(diǎn)的典型代表是 Knuth。他認(rèn)為圖至少有一個頂點(diǎn)，樹也必須至少有一個頂點(diǎn)。樹不能是空樹，但 N 叉樹可以是空樹。N 叉樹是限制根的子樹最多不能超過 N 棵的樹。 隨著對樹討論的深入，人們放寬了對樹結(jié)構(gòu)的限制。若把樹當(dāng)作層次結(jié)構(gòu)單獨(dú)對待，樹中允許結(jié)點(diǎn)個數(shù)為0。這樣，樹與N叉樹就沒有不可逾越的鴻溝了。 從面向?qū)ο笥^點(diǎn)，N叉樹是樹的特殊實(shí)現(xiàn)：樹是父類，N叉樹是子類。N叉樹繼承了樹的特性，它還有自己增加的特性，例如,202-5,理論上樹不可是空樹，N叉樹可以是空樹； 樹的子樹可以有序，也可以不要求有序，而N叉樹的子樹必須有序。 N叉樹的定義也是遞歸的，遞歸到

3、空樹終止；樹則遞歸到只有一個結(jié)點(diǎn)的子樹。 樹的子樹棵數(shù)不限，而N叉樹中根的子樹最多N棵。 樹可以區(qū)分為外向樹和內(nèi)向樹，而N叉樹一般是外向樹，即邊是有向的，從父指向子。 樹可以用N叉樹實(shí)現(xiàn)。二叉樹、B樹等又都是N叉樹的特殊情形。,202-6,樹的特點(diǎn),樹是分層結(jié)構(gòu)，又是遞歸結(jié)構(gòu)。每棵子樹的根結(jié)點(diǎn)有且僅有一個直接前驅(qū)，但可以有 0 個或多個直接后繼。,202-7,結(jié)點(diǎn) 結(jié)點(diǎn)的度 分支結(jié)點(diǎn) 葉結(jié)點(diǎn),子女 雙親 兄弟 祖先,樹的度 樹深度 樹高度 森林,子孫 結(jié)點(diǎn)層次 結(jié)點(diǎn)深度 結(jié)點(diǎn)高度,202-8,注意，結(jié)點(diǎn)的深度和結(jié)點(diǎn)的高度是不同的。結(jié)點(diǎn)的深度即結(jié)點(diǎn)所處層次，是從根向下逐層計算的；結(jié)點(diǎn)的高度是從下

4、向上逐層計算的：葉結(jié)點(diǎn)的高度為1, 其他結(jié)點(diǎn)的高度是取它的所有子女結(jié)點(diǎn)最大高度加一。 樹的深度與高度相等。 樹的深度按離根最遠(yuǎn)的 葉結(jié)點(diǎn)算，樹的高度按 根結(jié)點(diǎn)算，都是6。 葉結(jié)點(diǎn)也稱為終端結(jié)點(diǎn)， 非葉結(jié)點(diǎn)也稱為非終端 結(jié)點(diǎn)。,高度=4,深度=3,202-9,二叉樹的五種不同形態(tài),L,L,R,R,二叉樹 (Binary Tree),二叉樹的定義 一棵二叉樹是結(jié)點(diǎn)的一個有限集合，該集合或者為空，或者是由一個根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。 這個定義是遞歸的。,202-10,二叉樹的性質(zhì),性質(zhì)1 若二叉樹的層次從 1 開始, 則在二叉樹的第 i 層最多有 2i-1 個結(jié)

5、點(diǎn)。( i1) 證明用數(shù)學(xué)歸納法 i = 1時，根結(jié)點(diǎn)只有1個，21-1 = 20 =1； 若設(shè) i = k 時性質(zhì)成立，即該層最多有 2k-1 個結(jié)點(diǎn)，則當(dāng) i = k+1 時，由于第 k 層每個結(jié)點(diǎn)最多可有 2 個子女，第 k+1 層最多結(jié)點(diǎn)個數(shù)可有 2*2k-1 = 2k 個，故性質(zhì)成立。,202-11,性質(zhì)2 高度為 h 的二叉樹最多有 2h -1個結(jié)點(diǎn)。(h1) 證明用求等比級數(shù)前k項(xiàng)和的公式 高度為 h 的二叉樹有 h 層，各層最多結(jié)點(diǎn)個數(shù)相加，得到等比級數(shù)，求和得： 20 + 21 + 22 + + 2h-1 = 2h-1 空樹的高度為 0，只有根結(jié)點(diǎn)的樹的高度為 1。,202-

6、12,性質(zhì)3 對任何一棵二叉樹, 如果其葉結(jié)點(diǎn)有 n0 個, 度為2的非葉結(jié)點(diǎn)有 n2 個, 則有 n0n21 證明： 若設(shè)度為 1 的結(jié)點(diǎn)有 n1 個，總結(jié)點(diǎn)個數(shù)為 n，總邊數(shù)為 e，則根據(jù)二叉樹的定義， n = n0+n1+n2 e = 2n2+n1 = n-1 因此，有 2n2+n1 = n0+n1+n2-1 n2 = n0-1 n0 = n2+1 引申：可用于判斷二叉樹各類結(jié)點(diǎn)個數(shù)。,202-13,定義1 滿二叉樹 (Full Binary Tree) 定義2 完全二叉樹 (Complete Binary Tree) 若設(shè)二叉樹的高度為 h，則共有 h 層。除第 h 層外，其它各層 (

7、1h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個數(shù)，第 h 層從右向左連續(xù)缺若干結(jié)點(diǎn)，這就是完全二叉樹。,202-14,性質(zhì)4 具有 n (n0) 個結(jié)點(diǎn)的完全二叉樹的高度為 log2(n+1) 證明：設(shè)完全二叉樹的高度為 h，則有 2h-1-1n 2h-1 上面h-1層結(jié)點(diǎn)數(shù) 包括第h層的最大結(jié)點(diǎn)數(shù) 變形 2h-1n+12h 取對數(shù) h-1log2(n+1)h 有 h = log2(n+1),23-1,24-1,202-15,23-1,24-1,注意： 求高度的另一公式為 log2n +1, 此公式對于 n = 0 不適用。 若設(shè)完全二叉樹中葉結(jié)點(diǎn)有 n0 個, 則該二叉樹總的結(jié)點(diǎn)數(shù)為 n = 2n0, 或

8、 n = 2n0 1。 若完全二叉樹的結(jié)點(diǎn)數(shù)為奇數(shù)，沒有度為1的結(jié)點(diǎn)；為偶數(shù)，有一個度為1的結(jié)點(diǎn)。 右圖為理想平衡樹， 上層都是滿的，第 h 層結(jié)點(diǎn)分布在各 處。,202-16,性質(zhì)5 如將一棵有 n 個結(jié)點(diǎn)的完全二叉樹自頂向下，同一層自左向右連續(xù)給結(jié)點(diǎn)編號: 0, 1, 2, , n-1，則有以下關(guān)系： 若i = 0, 則 i 無雙親； 若i 0, 則 i 的雙親為(i-1)/2。 若2*i+1 n, 則 i 的左子女為 2*i+1； 若2*i+2 n, 則 i 的右子女為2*i+2。 若 i 為偶數(shù), 且i != 0, 則 其左兄弟為i-1； 若 i 為奇數(shù), 且i != n-1, 則其右

9、兄弟為i+1。,202-17,注意： 如果完全二叉樹各層次結(jié)點(diǎn)從 1 開始編號：1, 2, 3, , n，則有以下關(guān)系： 若i = 1, 則 i 無雙親； 若i 1, 則 i 的雙親為i / 2。 若2*i = n, 則 i 的左子女為 2*i； 若2*i+1 = n, 則 i 的右子女為2*i+1 若 i 為奇數(shù), 且i != 1, 則其左兄弟為i-1； 若 i 為偶數(shù), 且i != n, 則其右兄弟為i+1。,202-18,完全二叉樹 一般二叉樹 的順序表示 的順序表示,二叉樹的順序表示,202-19,極端情形: 只有右單支的二叉樹,對于完全二叉樹，因結(jié)點(diǎn)編號連續(xù)，數(shù)據(jù)存儲密集，適于用順序

10、表示； 對于一般二叉樹，用鏈表表示較好；,202-20,lchild data rchild,data,lchild,rchild,左子女指針 右子女指針,二叉樹的二叉鏈表表示,使用二叉鏈表，找子女的時間復(fù)雜度為O(1)，找雙親的時間復(fù)雜度為O(log2i)O(i)，其中，i 是該結(jié)點(diǎn)編號。,202-21,二叉樹的三叉鏈表表示,使用三叉鏈表，找子女、雙親的時間都是O(1)。,202-22,二叉樹 二叉鏈表 三叉鏈表,二叉樹鏈表表示的示例,202-23,二叉樹的定義,typedef char TElemType; /樹結(jié)點(diǎn)數(shù)據(jù)類型 typedef struct node /樹結(jié)點(diǎn)定義 TElem

11、Type data; /結(jié)點(diǎn)數(shù)據(jù)域 struct node *lchild, *rchild; /子女指針域 BiTNode; typedef BiTNode *BinTree; /樹定義，代表樹的根指針,202-24,二叉樹遍歷,樹的遍歷就是按某種次序訪問樹中的結(jié)點(diǎn)，要求每個結(jié)點(diǎn)訪問一次且僅訪問一次。設(shè) 訪問根結(jié)點(diǎn)記作 V， 遍歷根的左子樹記作 L， 遍歷根的右子樹記作 R， 則可能的遍歷次序有 前序 VLR 鏡像 VRL 中序 LVR 鏡像 RVL 后序 LRV 鏡像 RLV,202-25,中序遍歷二叉樹算法的框架是： 若二叉樹為空，則空操作； 否則 中序遍歷左子樹 (L)； 訪問根結(jié)點(diǎn)

12、(V)； 中序遍歷右子樹 (R)。 遍歷結(jié)果 a + b * c - d - e / f,中序遍歷 (Inorder Traversal),-,-,/,+,*,a,b,c,d,e,f,202-26,二叉樹遞歸的中序遍歷算法,void InOrder ( BiTNode *T ) if ( T != NULL ) InOrder ( T-lchild ); visit ( T-data ); InOrder ( T-rchild ); visit()是輸出數(shù)據(jù)值的操作，在實(shí)際使用時可用相應(yīng)的操作來替換。,202-27,前序遍歷二叉樹算法的框架是： 若二叉樹為空，則空操作； 否則 訪問根結(jié)點(diǎn) (V

13、)； 前序遍歷左子樹 (L)； 前序遍歷右子樹 (R)。 遍歷結(jié)果 - + a * b - c d / e f,前序遍歷 (Preorder Traversal),-,-,/,+,*,a,b,c,d,e,f,202-28,二叉樹遞歸的前序遍歷算法,void PreOrder (BiTNode *T) if (T != NULL) visit (T-data); PreOrder (T-lchild); PreOrder (T-rchild); 與中序遍歷算法相比，visit() 操作放在兩個子樹遞歸前序遍歷的最前面。,202-29,后序遍歷二叉樹算法的框架是： 若二叉樹為空，則空操作； 否則

14、后序遍歷左子樹 (L)； 后序遍歷右子樹 (R)； 訪問根結(jié)點(diǎn) (V)。 遍歷結(jié)果 a b c d - * + e f / -,后序遍歷 (Postorder Traversal),d,-,-,/,+,*,a,b,c,d,e,f,202-30,二叉樹遞歸的后序遍歷算法,void PostOrder (BiTNode *T) if (T != NULL) PostOrder (T-lchild); PostOrder (T-rchild); visit (T-data); 與中序遍歷算法相比，visit() 操作放在兩個子樹遞歸前序遍歷的最后面。,202-31,計算二叉樹結(jié)點(diǎn)個數(shù)的遞歸算法,應(yīng)用

15、二叉樹遍歷的事例,int Count (BiTNode *T) if (T = NULL) return 0; else return 1+ Count (T-lchild) + Count (T-rchild); 空二叉樹的結(jié)點(diǎn)個數(shù)為 0，可直接計算；否則可分別計算左、右子樹的結(jié)點(diǎn)個數(shù)，再相加得到總結(jié)點(diǎn)個數(shù)。,202-32,求二叉樹高度的遞歸算法,int Height ( BiTNode *T ) if (T = NULL) return 0; else int m = Height (T-lchild); int n = Height (T-rchild); return (m n) ?

16、m+1 : n+1; 空樹的高度為 0；非空樹情形，先計算根結(jié)點(diǎn)左右子樹的高度，取大者再加一得到二叉樹高度。,202-33,a,b,c,e,c,d c,c,訪問 a 進(jìn)棧 c 左進(jìn) b,訪問 b 進(jìn)棧 d 左進(jìn) 空,退棧 d 訪問 d 左進(jìn) 空,退棧 c 訪問 c 左進(jìn) e,訪問 e 左進(jìn) 空 退棧 ,結(jié)束,利用棧的前序遍歷的非遞歸算法,d,d,c,202-34,void PreOrder(BinTree T) stack S; InitStack(S); /遞歸工作棧 BiTNode * p = T; Push (S, NULL); while (p != NULL) visit(p-dat

17、a); if (p-rchild != NULL) Push(S, p-rchild); if (p-lchild != NULL) p = p-lchild; /進(jìn)左子樹 else Pop(S, p); /左子樹空, 進(jìn)右子樹 ,202-35,a,b,c,d,e,b a,a,d a,a,左空,退棧 訪問,左空,退棧 訪問,退棧 訪問,左空,e c,退棧訪問,c,c,右空,退棧訪問 棧空結(jié)束,利用棧的中序遍歷的非遞歸算法,202-36,void InOrder(BinTree T) stack S; InitStack(S); /遞歸工作棧 BiTNode *p = T; /初始化 do wh

18、ile (p != NULL) /子樹非空找中序第一個 Push(S, p); p = p-lchild; /邊找邊進(jìn)棧 if (!StackEmpty(S) /棧非空 Pop(S, p); /子樹中序第一個退棧 visit(p-data); /訪問之 p = p-rchild; /向右子樹走 while ( p != NULL | !StackEmpty(S) ); ,202-37,后序遍歷時使用的棧的結(jié)點(diǎn)定義 typedef struct BiTNode *ptr; /結(jié)點(diǎn)指針 enum tag L, R ; /該結(jié)點(diǎn)退棧標(biāo)記 StackNode; 根結(jié)點(diǎn)的 tag = L，表示從左子樹退

19、出, 訪問右子樹。 tag = R, 表示從右子樹退出, 訪問根。,利用棧的后序遍歷的非遞歸算法,202-38,a,b,c,d,e,aL,bL aL,bR aL,dL bR aL,dR bR aL,bR aL,aL,aR,eL cL aR,eR cL aR,cL aR,cR aR,aR,202-39,利用棧的后序遍歷的非遞歸算法,void PostOrder(BinTree T) stack S; InitStack(S); StackNode w; BiTNode *p = T; do while (p != NULL) /向左子樹走 w.ptr = p; w.tag = L; Push(S

20、, w); p = p-lchild; int succ = 1; /繼續(xù)循環(huán)標(biāo)記,202-40,while (succ ,202-41,二叉樹的計數(shù),由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹。 例, 前序序列 ABHFDECKG 和中序序列 HBDFAEKCG , 構(gòu)造二叉樹過程如下：,202-42,202-43,6,1,2,3,4,5,7,8,9,6,1,2,3,7,5,8,4,9,如果前序序列固定不變，給出不同的中序序列，可得到不同的二叉樹。 問題是：固定前序排列，選擇所有可能的中序排列，可以構(gòu)造出多少種不同的二叉樹？,202-44,1,2,3,1,2,3,1,2,3,1,2,

21、3,1,2,3,例如, 有 3 個數(shù)據(jù) 1, 2, 3 ，可得 5 種不同的二叉樹。它們的前序排列均為 123，中序序列可能是 123，132，213，231，321。 那么，如何推廣到一般情形呢？首先，只有一個結(jié)點(diǎn)的不同二叉樹只有一個；有 2 個結(jié)點(diǎn)的不同二叉樹只有 2 種，其他情況呢？,202-45,b0 =1,b1 =1,b2 =2,b3 =5,b4 =14,有0個, 1個, 2個, 3個結(jié)點(diǎn)的不同二叉樹如下,202-46,bi,bn-i-1,1,計算具有 n 個結(jié)點(diǎn)的不同二叉樹的棵數(shù),Catalan函數(shù) 例,202-47,線索二叉樹 (Threaded Binary Tree),又稱為

22、穿線樹。 通過二叉樹遍歷，可將二叉樹中所有結(jié)點(diǎn)的數(shù)據(jù)排列在一個線性序列中，可以找到某數(shù)據(jù)在這種排列下它的前驅(qū)和后繼。 希望不必每次都通過遍歷找出這樣的線性序列。只要事先做預(yù)處理，將某種遍歷順序下的前驅(qū)、后繼關(guān)系記在樹的存儲結(jié)構(gòu)中，以后就可以高效地找出某結(jié)點(diǎn)的前驅(qū)、后繼。 為此，在二叉樹存儲結(jié)點(diǎn)中增加線索信息。,202-48,線索 (Thread),增加前驅(qū)Pred指針和后繼Succ指針的二叉樹,202-49,這種設(shè)計的缺點(diǎn)是每個結(jié)點(diǎn)增加兩個指針，當(dāng)結(jié)點(diǎn)數(shù)很大時存儲消耗較大。 改造樹結(jié)點(diǎn)，將 pred 指針和 succ 指針壓縮到 lchild 和 rchild 的空閑指針中，并增設(shè)兩個標(biāo)志 l

23、tag 和 rtag，指明指針是指示子女還是前驅(qū)后繼。后者稱為線索。 ltag (或rtag) = 0，表示相應(yīng)指針指示左子女（或右子女結(jié)點(diǎn)）； ltag (或rtag) = 1, 表示相應(yīng)指針為前驅(qū)（或后繼）線索。,202-50,中序線索二叉樹及其鏈表表示,202-51,typedef int TTElemType; typedef struct node int ltag, rtag; struct node *lchild, *rchild; TTElemType data; ThreadNode, *ThreadTree; 注意，線索二叉樹在樹結(jié)點(diǎn)中增加了ltag和rtag，改變了二叉

24、樹的結(jié)構(gòu)。,線索二叉樹的結(jié)構(gòu)定義,202-52,通過中序遍歷建立中序線索二叉樹,void InThread (ThreadNode *t, ThreadNode * /建立當(dāng)前結(jié)點(diǎn) t 的前驅(qū)線索,202-53,if ( pre /遞歸, 右子樹線索化 使用此函數(shù)可以把以 t 為根的子樹一次中序線索化，但中序下最后一個結(jié)點(diǎn)的后繼線索沒有加上，指針 pre 在退出時正在指示這一結(jié)點(diǎn)。,202-54,void CreateInThread (ThreadTree T) ThreadNode *pre = NULL; /前驅(qū)指針 if ( T != NULL ) /樹非空, 線索化 InThread

25、 (T, pre);/中序遍歷線索二叉樹 pre-rchild = NULL; pre-rtag = 1; /后處理, 中序最后一個結(jié)點(diǎn) 通過該主程序?qū)崿F(xiàn)了對二叉樹的中序線索化。它是基于二叉樹的中序遍歷實(shí)現(xiàn)的。,202-55,202-56,202-57,202-58,202-59,202-60,202-61,202-62,尋找結(jié)點(diǎn) p 在中序下的后繼,if (p-rtag =1) 后繼為 p-rchild else /p-rtag != 1 后繼為結(jié)點(diǎn) p 右子樹 q 中的中序下的第一 個結(jié)點(diǎn),202-63,ThreadNode * First ( ThreadNode *t ) /函數(shù)返回以

26、 *t 為根的線索二叉樹中的中序序列下 /的第一個結(jié)點(diǎn) ThreadNode *p = t; while ( p-ltag = 0 ) p = p-lchild; return p; /最左下的結(jié)點(diǎn) ThreadNode * Next ( ThreadNode * p ) /函數(shù)返回在線索二叉樹中結(jié)點(diǎn) *p 在中序下的后 /繼結(jié)點(diǎn),202-64,if ( p-rtag = 0 ) return First(p-rchild); /p-rtag=0, 后繼為右子樹中序第一個結(jié)點(diǎn) else return p-rchild; /p-rtag=1, 直接返回后繼線索 void Inorder ( Th

27、readNode * t ) /以 t 為根的線索二叉樹的中序遍歷 ThreadNode * p; for ( p = First (t); p != NULL; p = Next (p) ) cout data endl; ,202-65,尋找結(jié)點(diǎn) p 在中序下的前驅(qū),if (p-ltag=1) 前驅(qū)為 p-lchild else /p-leftThread=0 前驅(qū)為結(jié)點(diǎn) p 左子樹 中序下的最后一個結(jié) 點(diǎn),202-66,前序線索二叉樹,在前序線索二叉樹中尋找當(dāng)前結(jié)點(diǎn)的后繼,202-67,后序序列 D B E C A,后序線索二叉樹,在后序線索二 叉樹中尋找當(dāng) 前結(jié)點(diǎn)的后繼,202-68,

28、樹的存儲表示 雙親表示 為了操作實(shí)現(xiàn)的方便，有時會規(guī)定結(jié)點(diǎn)的存放順序。例如，可以按樹的前序次序存放樹中的各個結(jié)點(diǎn)，或按樹的層次次序安排所有結(jié)點(diǎn)。,樹與樹的遍歷,202-69,子女鏈表表示,無序樹情形鏈表中各結(jié)點(diǎn)順序任意，有序樹必須自左向右鏈接各個子女結(jié)點(diǎn)。,202-70,子女指針表示,一個合理的想法是在結(jié)點(diǎn)中存放指向每一個子女結(jié)點(diǎn)的指針。但由于各個結(jié)點(diǎn)的子女?dāng)?shù)不同，每個結(jié)點(diǎn)設(shè)置數(shù)目不等的指針，將很難管理。 為此，設(shè)置等長的結(jié)點(diǎn)，每個結(jié)點(diǎn)包含的指針個數(shù)相等，等于樹的度（degree）。 這保證結(jié)點(diǎn)有足夠的指針指向它的所有子女結(jié)點(diǎn)。但可能產(chǎn)生很多空閑指針，造成存儲浪費(fèi)。,202-71,等數(shù)量的鏈域

29、,空鏈域2n+1個,202-72,子女-兄弟表示,也稱為樹的二叉樹表示。結(jié)點(diǎn)構(gòu)造為： firstChild 指向該結(jié)點(diǎn)的第一個子女結(jié)點(diǎn)。無序樹時，可任意指定一個結(jié)點(diǎn)為第一個子女。 nextSibling 指向該結(jié)點(diǎn)的下一個兄弟。任一結(jié)點(diǎn)在存儲時總是有順序的。 若想找某結(jié)點(diǎn)的所有子女，可先找firstChild,再反復(fù)用 nextSibling 沿鏈掃描。,202-73,樹的左子女 - 右兄弟表示,202-74,左子女-右兄弟表示的樹的結(jié)構(gòu)定義,typedef int TElemType; typedef struct node TElemType data; struct node *fchi

30、ld, *nsibling; CSNode, *CSTree; 注意，雖然此定義與二叉樹的類似，操作也類似，但語義是不同的。 樹結(jié)構(gòu)是遞歸的，可用遞歸函數(shù)實(shí)現(xiàn)相應(yīng)操作。,202-75,尋找雙親 子女 兄弟的操作,TreeNode *FindParent ( CSNode *T, CSNode *p ) /在以 T 為根的樹中找結(jié)點(diǎn) p 的雙親 if (T = NULL | p = NULL) return NULL; CSNode *q = T-fchild, *s; while (q != NULL ,202-76,if (q != NULL TreeNode * FindnextSibli

31、ng ( CSNode *p ) /在樹中找結(jié)點(diǎn) p 的兄弟,202-77,if ( p != NULL ) return p-nsibling; else return NULL; 深度優(yōu)先遍歷 先根次序遍歷 后根次序遍歷 廣度優(yōu)先遍歷,樹的遍歷,二叉樹表示,202-78,當(dāng)樹非空時 訪問根結(jié)點(diǎn) 依次先根遍歷根的各棵子樹 樹先根遍歷 ABEFCDG 對應(yīng)二叉樹前序遍歷 ABEFCDG 樹的先根遍歷結(jié)果與其對應(yīng)二叉樹 表示的前序遍歷結(jié)果相同 樹的先根遍歷可以借助對應(yīng)二叉樹的前序遍歷算法實(shí)現(xiàn),樹的先根次序遍歷,202-79,樹的先根次序遍歷的遞歸算法,void PreOrder ( CSNode

32、 *t ) /以指針 t 為根, 先根次序遍歷 if ( t != NULL ) visit ( t-data ); /訪問根結(jié)點(diǎn) CSNode *p = t-fchild; /第一棵子樹 while ( p != NULL ) PreOrder (p); /遞歸先根遍歷子樹 p = p-nsibling; ,202-80,當(dāng)樹非空時 依次后根遍歷根的各棵子樹 訪問根結(jié)點(diǎn) 樹后根遍歷 EFBCGDA 對應(yīng)二叉樹中序遍歷 EFBCGDA 樹的后根遍歷結(jié)果與其對應(yīng)二叉樹 表示的中序遍歷結(jié)果相同 樹的后根遍歷可以借助對應(yīng)二叉樹的中序遍歷算法實(shí)現(xiàn),樹的后根次序遍歷,202-81,樹的后根次序遍歷的遞歸

33、算法,void PostOrder ( CSNode *t ) /以指針 t 為根, 按后根次序遍歷樹 if ( t != NULL ) CSNode *p = t-fchild; while ( p != NULL ) PostOrder ( p ); p = p-nsibling; visit ( t-data ); /最后訪問根結(jié)點(diǎn) ,202-82,按廣度優(yōu)先次序遍歷樹的結(jié)果 ABCDEFG 廣度優(yōu)先遍歷算法 void LevelOrder ( CSTree T ) /分層遍歷樹，算法用到一個隊列 Queue Q; InitQueue(Q); CSNode *p; if ( T != N

34、ULL ) /樹不空 EnQueue(Q, T); /根結(jié)點(diǎn)進(jìn)隊列,廣度優(yōu)先(層次次序)遍歷,202-83,while ( ! QueueEmpty(Q) ) DeQueue(Q, p); visit(p-data); /隊列中取一個并訪問之 p = p-fchild; /待訪問結(jié)點(diǎn)的子女結(jié)點(diǎn)進(jìn)隊列 while ( p != NULL ) EnQueue ( Q, p ); p = p-nsibling; ,202-84,森林與二叉樹的轉(zhuǎn)換,將一般樹化為二叉樹表示就是用樹的子女-兄弟表示來存儲樹的結(jié)構(gòu)。 森林與二叉樹表示的轉(zhuǎn)換可以借助樹的二叉樹表示來實(shí)現(xiàn)。,202-85,A,F,H,T1 T2

35、 T3,A,B,C,D,G,I,J,E,K,F,B,C,D,E,G,H,I,K,J,A,B,C,E,D,H,I,K,J,F,G,3 棵樹的森林,各棵樹的二叉樹表示,森林的二叉樹表示,202-86,森林轉(zhuǎn)化成二叉樹的規(guī)則,若 F 為空，即 n = 0，則對應(yīng)的二叉樹 B 為空樹。 若 F 不空，則 二叉樹 B 的根是 F 第一棵樹 T1 的根； 其左子樹為 B (T11, T12, , T1m )，其中，T11, T12, , T1m 是 T1 的根的子樹； 其右子樹為 B (T2, T3, , Tn )，其中，T2, T3, , Tn 是除 T1 外其它樹構(gòu)成的森林。,202-87,二叉樹轉(zhuǎn)換

36、為森林的規(guī)則,如果 B 為空，則對應(yīng)的森林 F 也為空。 如果 B 非空，則 F 中第一棵樹 T1 的根為 B 的根； T1 的根的子樹森林 T11, T12, , T1m 是由 B 的根的左子樹 LB 轉(zhuǎn)換而來； F 中除了 T1 之外其余的樹組成的森林 T2, T3, , Tn 是由 B 的根的右子樹 RB 轉(zhuǎn)換而成的森林。,202-88,例題,設(shè)森林中有三棵樹，第一、第二和第三棵樹中的結(jié)點(diǎn)個數(shù)分別為 m1，m2 和 m3。那么在由該森林轉(zhuǎn)化成的二叉樹中根結(jié)點(diǎn)的右子樹上有（ ）個結(jié)點(diǎn)。 A. m1+m2 B. m2+m3 C. m3+m1 D. m1+m2+m3 【解答】在由森林轉(zhuǎn)化成的二

37、叉樹中根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)是除第一棵外其他樹上的結(jié)點(diǎn)，應(yīng)有m2+m3 個，故選擇 B。,202-89,森林的遍歷,森林的遍歷也分為深度優(yōu)先遍歷（包括先根次序遍歷和中根次序遍歷）和廣度優(yōu)先遍歷。 深度優(yōu)先遍歷 給定森林 F，若 F = ，則遍歷結(jié)束。否則 若F = T1 = r1, T11, , T1k , T2, ., Tm，則可以導(dǎo)出先根遍歷、中根遍歷兩種方法。其中，r1 是第一棵樹的根結(jié)點(diǎn)，T11, , T1k是第一棵樹的子樹森林，T2, .,Tm是除去第一棵樹之后剩余的樹構(gòu)成的森林。,202-90,若森林F = ，返回；否則 訪問森林的根（也是第一棵樹的根）r1； 先根遍歷森林第一棵樹

38、的根的子樹森林T11, , T1k； 先根遍歷森林中除第一棵樹外其他樹組成的森林T2, .,Tm。 注意， 是一個循環(huán)，對于每一個T1i，執(zhí)行樹的先根次序遍歷； 是一個遞歸過程，重新執(zhí)行 T2 為第一棵樹的森林的先根次序遍歷。,森林的先根次序遍歷,202-91,森林的先根次序遍歷的結(jié)果序列 ABCDE FG HIKJ 這相當(dāng)于對應(yīng)二叉樹的前序遍歷結(jié)果。,202-92,森林的中根次序遍歷,若森林 F = ，返回；否則 中根遍歷森林 F 第一棵樹的根結(jié)點(diǎn)的子樹森林T11, , T1k； 訪問森林的根結(jié)點(diǎn) r1； 中根遍歷森林中除第一棵樹外其他樹組成的森林T2, ., Tm。 注意，與先根次序遍歷相

39、比，訪問根結(jié)點(diǎn)的時機(jī)不同。所以在的情形，對以T2為第一棵樹的森林遍歷時，重復(fù)執(zhí)行的操作。,202-93,森林的中根次序遍歷的結(jié)果序列 BCEDA GF KIJH 這相當(dāng)于對應(yīng)二叉樹中序遍歷的結(jié)果。,202-94,廣度優(yōu)先遍歷（層次序遍歷）,AFH BCDGIJ EK,A,B,C,E,D,H,I,K,J,F,G,若森林 F 為空，返回； 否則 依次遍歷各棵樹的 根結(jié)點(diǎn)； 依次遍歷各棵樹根 結(jié)點(diǎn)的所有子女； 依次遍歷這些子女 結(jié)點(diǎn)的子女結(jié)點(diǎn)； ,202-95,樹的應(yīng)用,二叉排序樹 平衡二叉樹 Huffman樹 堆 并查集,202-96,二叉排序樹 ( Binary Search Tree ),定義

40、 二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹： 每個結(jié)點(diǎn)都有一個作為查找依據(jù)的關(guān)鍵字(key)，所有結(jié)點(diǎn)的關(guān)鍵字互不相同。 左子樹（如果非空）上所有結(jié)點(diǎn)的關(guān)鍵字都小于根結(jié)點(diǎn)的關(guān)鍵字。 右子樹（如果非空）上所有結(jié)點(diǎn)的關(guān)鍵字都大于根結(jié)點(diǎn)的關(guān)鍵字。 左子樹和右子樹也是二叉排序樹。,202-97,二叉排序樹例,結(jié)點(diǎn)左子樹上所有關(guān)鍵 字小于結(jié)點(diǎn)關(guān)鍵字； 結(jié)點(diǎn)右子樹上所有關(guān)鍵 字大于結(jié)點(diǎn)關(guān)鍵字； 如果對一棵二叉排序樹 進(jìn)行中序遍歷，可以按 從小到大的順序?qū)⒏鹘Y(jié) 點(diǎn)關(guān)鍵字排列起來。 注意，國外教材統(tǒng)稱為二叉搜索樹或二叉查找樹。,202-98,例題,一棵二叉樹是二叉排序樹的（ ）條件是樹中任一結(jié)點(diǎn)的

41、關(guān)鍵字值都大于左子女的關(guān)鍵字值，小于右子女的關(guān)鍵字值。 A. 充分但不必要 B. 必要但不充分 C. 充分且必要 D. 既不充分也不必要 【解答】 B。 通俗來講，必要條件是指符合定義則必具有后續(xù)講的特性。顯然一棵二叉樹是二叉排序樹，則樹中任一結(jié)點(diǎn)的關(guān)鍵字值一定大于左子女的關(guān)鍵字值，小于右子女的關(guān)鍵字值。充分條件是指滿足,202-99,后續(xù)講的特性則定義一定成立。就是說，如果一棵二叉樹任一結(jié)點(diǎn)的關(guān)鍵字值都大于左子女的關(guān)鍵字值，小于右子女的關(guān)鍵字值，則它一定是二叉排序樹。這就不一定了。 右圖描述的二叉樹滿足樹中 任一結(jié)點(diǎn)的關(guān)鍵字值一定大 于左子女的關(guān)鍵字值，小于 右子女的關(guān)鍵字值，但它不 是二叉

42、排序樹。,202-100,二叉排序樹的結(jié)構(gòu)定義,typedef char BSTElemType;/樹結(jié)點(diǎn)數(shù)據(jù)類型 typedef struct node /二叉排序樹結(jié)點(diǎn) BSTElemType data; struct node *lchild, *rchild; BSTNode, *BSTree;/二叉排序樹定義 從面向?qū)ο笥^點(diǎn)來看，二叉排序樹是二叉樹的特殊情形，它繼承了二叉樹的結(jié)構(gòu)，增加了自己的特性，對數(shù)據(jù)的存放增加了約束。,202-101,二叉排序樹上的查找,查找45 查找成功,查找28 查找失敗,在二叉排序樹上進(jìn)行查找，是一個從根結(jié)點(diǎn)開始，沿某一個分支逐層向下進(jìn)行比較判等的過程。它

43、可以是一個遞歸的過程。,202-102,假設(shè)想要在二叉排序樹中查找關(guān)鍵字為x的元素，查找過程從根結(jié)點(diǎn)開始。 如果根指針為NULL，則查找不成功；否則用給定值 x 與根結(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較： 如果給定值等于根結(jié)點(diǎn)的關(guān)鍵字值，則查找成功。 如果給定值小于根結(jié)點(diǎn)的關(guān)鍵字值，則繼續(xù)遞歸查找根結(jié)點(diǎn)的左子樹； 否則。遞歸查找根結(jié)點(diǎn)的右子樹。 查找成功時檢測指針停留在樹中某個結(jié)點(diǎn)。,202-103,可用判定樹描述查找過程。內(nèi)結(jié)點(diǎn)是樹中原有結(jié)點(diǎn)，外結(jié)點(diǎn)是失敗結(jié)點(diǎn)，代表樹中沒有的數(shù)據(jù)。 查找不成功時檢測指針停留在某個失敗結(jié)點(diǎn)。,查找22,查找45,202-104,二叉排序樹的查找算法,void Find ( B

44、STNode * t, BSTElemType x, BSTNode *,202-105, 查找的關(guān)鍵字比較次數(shù)最多不超過樹的高度。 每次結(jié)點(diǎn)的插入，都要從根結(jié)點(diǎn)出發(fā)查找插入位置，然后把新結(jié)點(diǎn)作為葉結(jié)點(diǎn)插入。 為了向二叉排序樹中插入一個新元素，必須先檢查這個元素是否在樹中已經(jīng)存在。,二叉排序樹的插入,202-106,為此，在插入之前先使用查找算法在樹中檢查要插入元素有還是沒有。 查找成功：樹中已有 這個元素,不再插入。 查找不成功：樹中原 來沒有關(guān)鍵字等于給 定值的結(jié)點(diǎn)，把新元 素加到查找操作停止 的地方。,202-107,void Insert ( BSTNode * ,202-108,輸入

45、數(shù)據(jù)，建立二叉排序樹的過程,輸入數(shù)據(jù) 53, 78, 65, 17, 87, 09, 81, 15 ,202-109,同樣 3 個數(shù)據(jù) 1, 2, 3 ，輸入順序不同，建立起來的二叉排序樹的形態(tài)也不同。這直接影響到二叉排序樹的查找性能。 如果輸入序列選得不好，會建立起一棵單支樹，使得二叉排序樹的高度達(dá)到最大。 2, 1, 3 1, 2, 3 1, 3, 2 2, 3, 1 3, 1, 2 3, 2, 1,202-110,二叉排序樹的刪除,在二叉排序樹中刪除一個結(jié)點(diǎn)時，必須將因刪除結(jié)點(diǎn)而斷開的二叉鏈表重新鏈接起來，同時確保二叉排序樹的性質(zhì)不會失去。 為保證在刪除后樹的查找性能不至于降低，還需要防

46、止重新鏈接后樹的高度增加。 被刪結(jié)點(diǎn)的右子樹為空，可以拿它的左子女結(jié)點(diǎn)頂替它的位置，再釋放它。 被刪結(jié)點(diǎn)的左子樹為空，可以拿它的右子女結(jié)點(diǎn)頂替它的位置，再釋放它。 被刪結(jié)點(diǎn)的左、右子樹都不為空，可以在它,202-111,的右子樹中尋找中序下的第一個結(jié)點(diǎn)(所有比被刪關(guān)鍵字大的關(guān)鍵字中它的值最小),用它的值填補(bǔ)到被刪結(jié)點(diǎn)中，再來處理這個結(jié)點(diǎn)的刪除問題。當(dāng)然，也可以到它的左子樹中尋找中序下的最后一個結(jié)點(diǎn)。,右子樹空, 用 左子女頂替,202-112,左子樹空, 用右子女頂替,在右子樹上找中序下第一個結(jié)點(diǎn)填補(bǔ),202-113,二叉排序樹性能分析,對于有 n 個關(guān)鍵字的集合，其關(guān)鍵字有 n! 種不同排列

47、，可構(gòu)成不同二叉排序樹有 (棵) 用樹的查找效率來評價這些二叉排序樹。 用判定樹來描述查找過程，在判定樹中，表示內(nèi)結(jié)點(diǎn)，它包含關(guān)鍵字集合中的某一個關(guān)鍵字；表示外結(jié)點(diǎn)，代表各關(guān)鍵字間隔中的不在關(guān)鍵字集合中的關(guān)鍵字。它們是查找失敗時到達(dá)的結(jié)點(diǎn), 物理上實(shí)際不存在。,202-114,在每兩個外部結(jié)點(diǎn)間必存在一個內(nèi)部結(jié)點(diǎn)。 例，已知關(guān)鍵字集合 a1, a2, a3 = do, if, to ，對應(yīng)查找概率 p1, p2, p3, 在各查找不成功間隔內(nèi)查找概率分別為 q0, q1, q2, q3。可能的判定樹如下所示。,202-115,202-116,一棵判定樹的查找成功的平均查找長度ASLsucc 定

48、義為該樹所有內(nèi)結(jié)點(diǎn)上的權(quán)值 pi與查找該結(jié)點(diǎn)時所需的關(guān)鍵字比較次數(shù)ci (= li)乘積之和： 查找不成功的平均查找長度ASLunsucc為樹中所有外結(jié)點(diǎn)上權(quán)值qj與到達(dá)該外結(jié)點(diǎn)所需關(guān)鍵字比較次數(shù)cj (= lj-1)乘積之和：,202-117,相等查找概率的情形,設(shè)樹中所有內(nèi)、外結(jié)點(diǎn)的查找概率都相等： pi = 1/3, 1 i 3 qj = 1/4, 0 j 3 圖(a): ASLsucc = 1/3*( 3 + 2 +1 ) = 6/3 = 2 ASLunsucc = 1/4*( 3 + 3 +2 + 1 ) = 9/4 圖(b): ASLsucc = 1/3*( 2 + 1 + 2 )

49、 = 5/3 ASLunsucc = 1/4*( 2 + 2 + 2 + 2 ) = 8/4 圖(c): ASLsucc = 2, ASLunsucc = 9/4 圖(d): ASLsucc = 2, ASLunsucc = 9/4 圖(e): ASLsucc = 2, ASLunsucc = 9/4,202-118,圖(b)的情形所得的平均查找長度最小。一般把平均查找長度達(dá)到最小的判定樹稱作最優(yōu)二叉排序樹。 在相等查找概率的情形下，最優(yōu)二叉排序樹的上面 h-1（h是高度）層都是滿的，只有第 h 層不滿。如果結(jié)點(diǎn)集中在該層的左邊，則它是完全二叉樹；如果結(jié)點(diǎn)散落在該層各個地方，則有人稱之為理想平

50、衡樹。,202-119,平衡二叉樹,高度不平衡 高度平衡,平衡二叉樹的定義 一棵AVL樹或者是空樹，或者是具有下列性質(zhì)的二叉排序樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的高度之差的絕對值不超過1。,202-120,結(jié)點(diǎn)的平衡因子 balance factor,每個結(jié)點(diǎn)附加一個數(shù)字，給出該結(jié)點(diǎn)左子樹的高度減去右子樹的高度所得的高度差，這個數(shù)字即為結(jié)點(diǎn)的平衡因子 bf（balance factor）。 平衡二叉樹任一結(jié)點(diǎn)平衡因子只能取 -1, 0, 1。 如果一個結(jié)點(diǎn)的平衡因子的絕對值大于 1，則這棵二叉排序樹就失去了平衡，不再是平衡二叉樹。 如果一棵二叉排序樹是高度平衡的, 且有

51、n 個結(jié)點(diǎn)，其高度可保持在O(log2n),平均查找長度也可保持在O(log2n)。,202-121,平衡化旋轉(zhuǎn),如果在一棵平衡二叉樹中插入一個新結(jié)點(diǎn)，造成了不平衡。必須調(diào)整樹的結(jié)構(gòu)，使之平衡化。 平衡化旋轉(zhuǎn)有兩類： 單旋轉(zhuǎn) (LL旋轉(zhuǎn)和RR旋轉(zhuǎn)) 雙旋轉(zhuǎn) (LR旋轉(zhuǎn)和RL旋轉(zhuǎn)) 每插入一個新結(jié)點(diǎn)時，平衡二叉樹中相關(guān)結(jié)點(diǎn)的平衡狀態(tài)會發(fā)生改變。因此，在插入一個新結(jié)點(diǎn)后，需要從插入位置沿通向根的路徑回溯，檢查各結(jié)點(diǎn)的平衡因子。,202-122,如果在某一結(jié)點(diǎn)發(fā)現(xiàn)高度不平衡，停止回溯。從發(fā)生不平衡的結(jié)點(diǎn)起，沿剛才回溯的路徑取直接下兩層的結(jié)點(diǎn)。 如果這三個結(jié)點(diǎn)處于一條直線上，則采用單旋轉(zhuǎn)進(jìn)行平衡化。單

52、旋轉(zhuǎn)可按其方向分為LL旋轉(zhuǎn)和RR旋轉(zhuǎn), 其中一個是另一 個的鏡像，其方向與不平衡的形狀相關(guān)。 如果這三個結(jié)點(diǎn)處于一條折線上，則采用雙旋轉(zhuǎn)進(jìn)行平衡化。雙旋轉(zhuǎn)分為LR旋轉(zhuǎn)和RL旋轉(zhuǎn)兩類。,202-123,左單旋轉(zhuǎn)（RR單旋）,-1,0,0,在結(jié)點(diǎn)A的右子女C的右子樹E中插入新結(jié)點(diǎn)，該子樹高度增1導(dǎo)致結(jié)點(diǎn)A的平衡因子變成-2，出現(xiàn)不平衡。為使樹恢復(fù)平衡，從A沿插入路徑連續(xù)取3個結(jié)點(diǎn)A、C和E，以結(jié)點(diǎn)C為旋轉(zhuǎn)軸，讓結(jié)點(diǎn)A反時針旋轉(zhuǎn)。,202-124,右單旋轉(zhuǎn)（LL單旋）,在結(jié)點(diǎn)A的左子女的左子樹D上插入新結(jié)點(diǎn)使其高度增1導(dǎo)致結(jié)點(diǎn)A的平衡因子增到+2，造成不平衡。為使樹恢復(fù)平衡，從A沿插入路徑連續(xù)取3

53、個結(jié)點(diǎn)A、B和D，以結(jié)點(diǎn)B為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A順時針旋轉(zhuǎn)。,202-125,在結(jié)點(diǎn)A的左子女的右子樹中插入新結(jié)點(diǎn)，該子樹的高度增1導(dǎo)致結(jié)點(diǎn)A的平衡因子變?yōu)?2，發(fā)生了不平衡。,先左后右雙旋轉(zhuǎn)（LR雙旋）,202-126,從結(jié)點(diǎn)A起沿插入路徑選取3個結(jié)點(diǎn)A、B和E，先以結(jié)點(diǎn)E為旋轉(zhuǎn)軸，將結(jié)點(diǎn)B反時針旋轉(zhuǎn)，E頂替原B的位置。再以結(jié)點(diǎn)E為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A順時針旋轉(zhuǎn)。,202-127,先右后左雙旋轉(zhuǎn)（RL雙旋）,在根結(jié)點(diǎn)A的右子女的左子樹中F或G上插入新結(jié)點(diǎn)，該子樹高度增1。結(jié)點(diǎn)A的平衡因子變?yōu)?2，發(fā)生了不平衡。,202-128,從結(jié)點(diǎn)A起沿插入路徑選取3個結(jié)點(diǎn)A、C和D。首以結(jié)點(diǎn)D為旋轉(zhuǎn)軸，將結(jié)點(diǎn)C

54、順時針旋轉(zhuǎn), 以D代替原來C的位置。再以D為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A反時針旋轉(zhuǎn)，恢復(fù)樹的平衡。,202-129,平衡二叉樹的插入,在向一棵本來是高度平衡的平衡二叉樹中插入一個新結(jié)點(diǎn)時，如果樹中某個結(jié)點(diǎn)的平衡因子的絕對值 |bf|1，則出現(xiàn)了不平衡，需要做平衡化處理。 算法從一棵空樹開始，通過輸入一系列元素關(guān)鍵字，逐步建立平衡二叉樹。 在插入新結(jié)點(diǎn)后，需從插入結(jié)點(diǎn)沿通向根的路徑向上回溯，如果發(fā)現(xiàn)有不平衡的結(jié)點(diǎn)，需從這個結(jié)點(diǎn)出發(fā)，使用平衡旋轉(zhuǎn)方法進(jìn)行平衡化處理。,202-130,設(shè)新結(jié)點(diǎn)p的平衡因子為0，其父結(jié)點(diǎn)為pr。插入新結(jié)點(diǎn)后pr的平衡因子值有三種情況： 結(jié)點(diǎn)pr的平衡因子為0。說明剛才是在 pr

55、的較矮的子樹上插入了新結(jié)點(diǎn)，此時不需做平衡化處理，返回主程序。子樹的高度不變。 結(jié)點(diǎn)pr的平衡因子的絕對值 |bf| = 1。說明插入前pr的平衡因子是0，插入新結(jié)點(diǎn)后，以pr為根的子樹不需平衡化旋轉(zhuǎn)。但該子樹高度增加，,202-131,還需從結(jié)點(diǎn)pr向根方向回溯，繼續(xù)考查結(jié)點(diǎn)pr雙親(pr = Parent(pr)的平衡狀態(tài)。 結(jié)點(diǎn)pr的平衡因子的絕對值|bf| = 2。說明新結(jié)點(diǎn)在較高的子樹上插入，造成了不平衡，需要做平衡化旋轉(zhuǎn)。此時可進(jìn)一步分2種情況討論： 若結(jié)點(diǎn)pr的bf = -2，說明右子樹高，結(jié)合其右子女q 的bf分別處理：,202-132,若q的bf與pr同符號(=-1)，執(zhí)行R

56、R單旋。 若q的bf與pr異符號(=1)，執(zhí)行RL雙旋。,左單旋轉(zhuǎn),插入后,202-133,若結(jié)點(diǎn)pr的bf = 2，說明左子樹高，結(jié)合其左子女q 的bf分別處理： 若q的bf與pr同符號(=1)，執(zhí)行LL單旋； 若q的bf與pr異符號(=-1)，執(zhí)行LR雙旋。 下面舉例說明在平衡二叉樹上的插入過程。,右單旋轉(zhuǎn),先左后右雙旋轉(zhuǎn),202-134,例，輸入關(guān)鍵字序列為 16, 3, 7, 11, 9, 26, 18, 14, 15 ，插入和調(diào)整過程如下。,202-135,202-136,從空樹開始的建樹過程,202-137,平衡二叉樹的刪除,如果被刪結(jié)點(diǎn)x最多只有一個子女，那么問題比較簡單: 將結(jié)點(diǎn)x從樹中刪去。 因?yàn)榻Y(jié)點(diǎn)x最多有一個子女，可以簡單地把x的雙親結(jié)點(diǎn)中原來指向結(jié)點(diǎn)x的指針改指到這個子女結(jié)點(diǎn)； 如果