第四章樹與樹的表示(三)

1、4.5平衡二叉樹平衡二叉樹 假定二叉搜索樹中每個(gè)結(jié)點(diǎn)的查找概率都是相同的，稱查找所有結(jié)點(diǎn)的比較次數(shù)的平均值為樹的“平均查找長(zhǎng)度”（ASL)。一、什么是平衡二叉樹例搜索樹結(jié)點(diǎn)不同插入次序，將導(dǎo)致不同的深度和平均查找長(zhǎng)度ASLJanAprAprFebMarJuneMayFebJulyMayAugAugJulySeptAugJanMarOctOctDecOctAprDecJuneNovSeptSeptNov(a) 自然月份序列ASL(a)=(1+22+33+43+52+61)/12 = 3.5(b) 按July, Feb, May, Mar,Aug, Jan, Apr, Jun, Oct, Sept

2、,Nov, DecASL(b)=3.0(c)月份字符串月份字符串大小順序ASL(c)= 6.5 樹深在最好的情況下是O（logN),所以，二叉搜索樹在最好情況下的查找復(fù)雜度是O（logN)。 上述ASL的計(jì)算結(jié)果表明，一棵樹的ASL值越小，它的結(jié)構(gòu)越好，與完全二叉樹越接近，其查找時(shí)間復(fù)查度也越接近O（logN)。因此，為了保證二叉搜索樹查找的對(duì)數(shù)級(jí)時(shí)間效率，應(yīng)盡可能創(chuàng)建枝繁葉茂的樹，而避免樹枝過(guò)長(zhǎng)、過(guò)少。 最好的結(jié)構(gòu)是完美二叉樹，從根到葉的各條路徑都是相同的，稱這種樹為完全平衡的。 二、定義“平衡因子（Balance Factor，簡(jiǎn)稱BF）: BF(T) = hL-hR，其中hL和hR分別為

3、T的左、右子樹的高度。 平衡二叉樹（Balanced Binary Tree）（AVL樹）空樹，或者任一結(jié)點(diǎn)左、右子樹高度差的絕對(duì)值不超過(guò)1，即|BF(T) | 1 因此，平衡二叉樹上每個(gè)結(jié)點(diǎn)的平衡因子只可能是-1、0和1，否則，只要有一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1， 該二叉樹就不是平衡二叉樹。三、平衡二叉樹的調(diào)整 一般的二叉排序樹是不平衡的，若能通過(guò)某種方法使其既保持有序性，又具有平衡性，就找到了構(gòu)造平衡二叉排序樹的方法，該方法稱為平衡化旋轉(zhuǎn)。 在對(duì)AVL樹進(jìn)行插入或刪除一個(gè)結(jié)點(diǎn)后，通常會(huì)影響到從根結(jié)點(diǎn)到插入(或刪除)結(jié)點(diǎn)的路徑上的某些結(jié)點(diǎn)，這些結(jié)點(diǎn)的子樹可能發(fā)生變化。這時(shí)就需要做“平衡化

4、”處理，即相應(yīng)的局部“旋轉(zhuǎn)”調(diào)整，使得調(diào)整后的樹達(dá)到平衡。1000MarMayNov2Mar1右單旋 MayMay00Mar0NovNov 不平衡的“發(fā)現(xiàn)者”是Mar，“麻煩結(jié)點(diǎn)”Nov 在發(fā)現(xiàn)者右子樹的右邊，因而叫 RR 插入，需要RR 旋轉(zhuǎn)（右單旋）AL1A0BRR插入AL2A1BRR旋轉(zhuǎn)0A0BBRBLBRBLBRALBL1.單旋調(diào)整cc1010011AugApr22May0LL旋轉(zhuǎn)左單旋12May00AugMarNov0AprAug0MarNov0Apr“發(fā)現(xiàn)者”是Mar，“麻煩結(jié)點(diǎn)”Apr 在發(fā)現(xiàn)者左子樹的左邊，因而叫 LL 插入，需要LL 旋轉(zhuǎn)（左單旋）0B1AARLL插入1B2A

5、ARLL旋轉(zhuǎn)BL0B0ABLBRBLBRBRARcc001000110001Jan0Apr1Aug02May1Mar0NovLR左-右雙旋0Apr1Aug2Mar0Jan1May0NovJan旋轉(zhuǎn)“發(fā)現(xiàn)者”是May，“麻煩結(jié)點(diǎn)”Jan在左子樹的右邊，因而叫 LR 插入，需要LR 旋轉(zhuǎn)LR2LR0B0A插入1BA1旋轉(zhuǎn)0 or 10C1 or 0CARCARBABLCLCRBLCLCRBLCLCRAROROR2.雙旋調(diào)整DDDDD0Apr200110110200011010001DecJulyFeb0Apr1Aug1Dec2Mar0Jan01May0July20NovRL右-左雙旋旋轉(zhuǎn) 1Dec

6、1Aug0Feb2Mar1Jan1May0July0NovFeb一般情況調(diào)整如下:RL2RLA00B插入A11B旋轉(zhuǎn)0 or 10C1 or 0ALCALCABCLCRBRCLCRBRALCLCRBRORORDDDDD1 01Jan1 10 01 2110Dec MarMay110100AprApr0 Feb 0 July0112 020 010 2020 11Nov00JuneOctSeptApr June1 1 0Dec Dec MarAugAug Feb JanJulyAug Feb July0 0 011JanMar1 1 0 00 1June2MayNov0MayJune1Nov 0

7、Oct0Oct 0Sept注意：有時(shí)候插入元素即便不需要調(diào)整結(jié)構(gòu)，也可能需要重新計(jì)算一些平衡因子。typedef struct AVLNode *Position;typedef Position AVLTree; /* AVL樹類型 */typedef struct AVLNode ElementType Data; /* 結(jié)點(diǎn)數(shù)據(jù) */ AVLTree Left; /* 指向左子樹 */ AVLTree Right; /* 指向右子樹 */ int Height; /* 樹高 */四、AVL樹的插入int Max ( int a, int b ) return a b ? a : b;AV

8、LTree Insert( AVLTree T, ElementType X ) /* 將X插入AVL樹T中，并且返回調(diào)整后的AVL樹 */if ( !T ) /* 若插入空樹，則新建包含一個(gè)結(jié)點(diǎn)的樹 */ T = (AVLTree)malloc(sizeof(struct AVLNode); T-Data = X; T-Height = 0; T-Left = T-Right = NULL; /* if (插入空樹) 結(jié)束 */ else if ( X Data ) /* 插入T的左子樹 */ T-Left = Insert( T-Left, X); /* 如果需要左旋 */ if ( Ge

9、tHeight(T-Left)-GetHeight(T-Right) = 2 ) if ( X Left-Data ) T = SingleLeftRotation(T); /* 左單旋 */ else T = DoubleLeftRightRotation(T); /* 左-右雙旋 */ /* else if (插入左子樹) 結(jié)束 */ else if ( X T-Data ) /* 插入T的右子樹 */ T-Right = Insert( T-Right, X ); /* 如果需要右旋 */ if ( GetHeight(T-Left)-GetHeight(T-Right) = -2 )

10、if ( X T-Right-Data ) T = SingleRightRotation(T); /* 右單旋 */ else T = DoubleRightLeftRotation(T); /* 右-左雙旋 */ /* else if (插入右子樹) 結(jié)束 */ /* else X = T-Data，無(wú)須插入 */T-Height = Max( GetHeight(T-Left), GetHeight(T-Right) ) + 1; /* 別忘了更新樹高 */return T;AVLTree SingleLeftRotation ( AVLTree A )16. /* 注意：A必須有一個(gè)左

11、子結(jié)點(diǎn)B */17. /* 將A與B做左單旋，更新A與B的高度，返回新的根結(jié)點(diǎn)B */ 18. 19. AVLTree B = A-Left;20. A-Left = B-Right;21. B-Right = A;22. A-Height = Max( GetHeight(A-Left), GetHeight(A-Right) ) + 1;23. B-Height = Max( GetHeight(B-Left), A-Height ) + 1;24. 25. return B;26.27. 28.AVLTree DoubleLeftRightRotation ( AVLTree A )29

12、. /* 注意：A必須有一個(gè)左子結(jié)點(diǎn)B，且B必須有一個(gè)右子結(jié)點(diǎn)C */30. /* 將A、B與C做兩次單旋，返回新的根結(jié)點(diǎn)C */31. 32. /* 將B與C做右單旋，C被返回 */33. A-Left = SingleRightRotation(A-Left);34. /* 將A與C做左單旋，C被返回 */35. return SingleLeftRotation(A);36.37. 38./*/39./* 對(duì)稱的右單旋與右-左雙旋請(qǐng)自己實(shí)現(xiàn) */40./*/41. AVLTree SingleLeftRotation ( AVLTree A ) /* 注意：A必須有一個(gè)左子結(jié)點(diǎn)B */

13、/* 將A與B做左單旋，更新A與B的高度，返回新的根結(jié)點(diǎn)B */ AVLTree B = A-Left; A-Left = B-Right; B-Right = A; A-Height = Max( GetHeight(A-Left), GetHeight(A-Right) ) + 1; B-Height = Max( GetHeight(B-Left), A-Height ) + 1; return B; AVLTree DoubleLeftRightRotation ( AVLTree A ) /* 注意：A必須有一個(gè)左子結(jié)點(diǎn)B，且B必須有一個(gè)右子結(jié)點(diǎn)C */ /* 將A、B與C做兩次單旋

14、，返回新的根結(jié)點(diǎn)C */A-Left = SingleRightRotation(A-Left); /* 將B與C做右單旋，C被返回 */ return SingleLeftRotation(A);/* 將A與C做左單旋，C被返回 */ 作業(yè)：1、在分量111的數(shù)組中按從小到大順序存放11個(gè)元素，如果用順序查找和二分查找分別查找這11個(gè)元素，哪個(gè)位置的元素在這兩種方法的查找中總次數(shù)最少？.A.1 B.2 C.3 D.62、在分量111的數(shù)組中按從小到大順序存放11個(gè)元素，如果進(jìn)行二分查找，查找次數(shù)最少的元素位于什么位置？.A.1 B.5 C.6 D.11測(cè)驗(yàn)：1.1.設(shè)有如圖設(shè)有如圖6-27所

15、示的二叉樹。所示的二叉樹。 分別用順序存儲(chǔ)方法和鏈接存儲(chǔ)方法畫出該二叉樹的存分別用順序存儲(chǔ)方法和鏈接存儲(chǔ)方法畫出該二叉樹的存儲(chǔ)結(jié)構(gòu)。儲(chǔ)結(jié)構(gòu)。 寫出該二叉樹的先序、中序、后序遍歷序列。寫出該二叉樹的先序、中序、后序遍歷序列。2.2.已知一棵二叉樹的先序遍歷序列和中序遍歷序列分別為已知一棵二叉樹的先序遍歷序列和中序遍歷序列分別為ABDGHCEFI和和GDHBAECIF，請(qǐng)畫出這棵二叉樹，然后給出該，請(qǐng)畫出這棵二叉樹，然后給出該樹的后序遍歷序列。樹的后序遍歷序列。圖圖6-27 二叉樹二叉樹adebfgchkmn3、一棵度為 m的樹有n個(gè)節(jié)點(diǎn)。若每個(gè)節(jié)點(diǎn)直接用m個(gè)鏈指向相應(yīng)的兒子，則表示這個(gè)樹所需要的

16、總空間是n*(m+1) (假定每個(gè)鏈以及表示節(jié)點(diǎn)的數(shù)據(jù)域都是一個(gè)單位空間).。當(dāng)采用兒子/兄弟（First Child/Next Sibling）表示法時(shí)，所需的總空間是：.A.3n B.2n C.n*m D.n*(m-1)4、如果一個(gè)完全二叉樹最底下一層為第六層（根為第一層）且該層共有8個(gè)葉結(jié)點(diǎn)，那么該完全二叉樹共有多少個(gè)結(jié)點(diǎn)？.A.31 B.39 C.63 D.715、若有一二叉樹的總結(jié)點(diǎn)數(shù)為98，只有一個(gè)兒子的結(jié)點(diǎn)數(shù)為48，則該樹的葉結(jié)點(diǎn)數(shù)是多少？.A.25 B.50 C.不確定 D.這樣的樹不存在6、設(shè)深度為d（只有一個(gè)根結(jié)點(diǎn)時(shí)，d為1）的二叉樹只有度為0和2的結(jié)點(diǎn)，則此類二叉樹的結(jié)點(diǎn)

17、數(shù)至少為2d-1.A. B.7、假定只有四個(gè)結(jié)點(diǎn)A、B、C、D的二叉樹，其前序遍歷序列為ABCD，則下面哪個(gè)序列是不可能的中序遍歷序列？.A. ABCD B. ACDB C. DCBA D. DABC8、對(duì)于二叉樹，如果其中序遍歷結(jié)果與前序遍歷結(jié)果一樣，那么可以斷定該二叉樹_.A.是完全二叉樹 B.所有結(jié)點(diǎn)都沒(méi)有左兒子C.所有結(jié)點(diǎn)都沒(méi)有右兒子 D.這樣的樹不存在9、已知一二叉樹的后序和中序遍歷的結(jié)果分別是FDEBGCA 和FDBEACG,那么該二叉樹的前序遍歷結(jié)果是什么？.A. ABDFECG B. ABDEFCG C. ABDFEGC D. ABCDEFG10、假定只有四個(gè)結(jié)點(diǎn)A、B、C、D

18、的二叉樹，其前序遍歷序列為ABCD，則下面哪個(gè)序列是不可能的中序遍歷序列？.A. ABCD B. ACDB C. DCBA D. DABC11、對(duì)于二叉樹，如果其中序遍歷結(jié)果與前序遍歷結(jié)果一樣，那么可以斷定該二叉樹_.A.是完全二叉樹 B.所有結(jié)點(diǎn)都沒(méi)有左兒子C.所有結(jié)點(diǎn)都沒(méi)有右兒子 D.這樣的樹不存在12、已知一二叉樹的后序和中序遍歷的結(jié)果分別是FDEBGCA 和FDBEACG,那么該二叉樹的前序遍歷結(jié)果是什么？.A. ABDFECG B. ABDEFCG C. ABDFEGC D.ABCDEFG13、非遞歸方法中序遍歷下面這顆二叉樹，其堆棧操作序列（P代表為push,O代表為pop)是什么？.A.PPOOPOPPOOB.PPPPPOOOOOC.PPOOOPPOOD.PPOPOOPPOO14、已知有顆5個(gè)結(jié)點(diǎn)的二叉樹，其前序遍歷序列是a?，中序遍歷序列是a?，可以斷定：.A.該樹根結(jié)點(diǎn)是a，且沒(méi)有左子樹 B.該樹根結(jié)點(diǎn)是a，且沒(méi)有右子樹C.該樹最左邊的結(jié)點(diǎn)