數(shù)據(jù)結(jié)構(gòu)清華大學(xué)殷人昆演示文稿

數(shù)據(jù)結(jié)構(gòu)清華大學(xué)殷人昆演示文稿1當(dāng)前第1頁\共有201頁\編于星期五\0點(diǎn)數(shù)據(jù)結(jié)構(gòu)清華大學(xué)殷人昆2當(dāng)前第2頁\共有201頁\編于星期五\0點(diǎn)樹的定義與基本概念二叉樹二叉樹遍歷二叉樹的計(jì)數(shù)線索二叉樹樹與樹的遍歷樹的應(yīng)用第4章樹與二叉樹當(dāng)前第3頁\共有201頁\編于星期五\0點(diǎn)樹和森林的概念樹的定義

樹是由n(n＞0)個結(jié)點(diǎn)組成的有限集合：有一個特定的稱之為根(root)的結(jié)點(diǎn)；除根以外的其它結(jié)點(diǎn)劃分為m(m≥0)個互不相交的有限集合T1,T2,…,Tm，每個集合又是一棵樹，并且稱之為根的子樹。此定義是離散數(shù)學(xué)和圖論中給出的。它們把樹視為圖的一個極小連通子圖。有n個結(jié)點(diǎn)的樹有n-1條邊，而且不能有回路。當(dāng)前第4頁\共有201頁\編于星期五\0點(diǎn)這種觀點(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叉樹繼承了樹的特性，它還有自己增加的特性，例如當(dāng)前第5頁\共有201頁\編于星期五\0點(diǎn)理論上樹不可是空樹，N叉樹可以是空樹；樹的子樹可以有序，也可以不要求有序，而N叉樹的子樹必須有序。N叉樹的定義也是遞歸的，遞歸到空樹終止；樹則遞歸到只有一個結(jié)點(diǎn)的子樹。樹的子樹棵數(shù)不限，而N叉樹中根的子樹最多N棵。樹可以區(qū)分為外向樹和內(nèi)向樹，而N叉樹一般是外向樹，即邊是有向的，從父指向子。樹可以用N叉樹實(shí)現(xiàn)。二叉樹、B樹等又都是N叉樹的特殊情形。當(dāng)前第6頁\共有201頁\編于星期五\0點(diǎn)樹的特點(diǎn)樹是分層結(jié)構(gòu)，又是遞歸結(jié)構(gòu)。每棵子樹的根結(jié)點(diǎn)有且僅有一個直接前驅(qū)，但可以有0個或多個直接后繼。1層2層4層3層depth=4height=4ACGBDEFKLHMIJ前驅(qū)后繼當(dāng)前第7頁\共有201頁\編于星期五\0點(diǎn)1層2層4層3層depth=4height=4ACGBDEFKLHMIJ結(jié)點(diǎn)結(jié)點(diǎn)的度分支結(jié)點(diǎn)葉結(jié)點(diǎn)子女雙親兄弟祖先樹的度樹深度樹高度森林子孫結(jié)點(diǎn)層次結(jié)點(diǎn)深度結(jié)點(diǎn)高度當(dāng)前第8頁\共有201頁\編于星期五\0點(diǎn)注意，結(jié)點(diǎn)的深度和結(jié)點(diǎn)的高度是不同的。結(jié)點(diǎn)的深度即結(jié)點(diǎn)所處層次，是從根向下逐層計(jì)算的；結(jié)點(diǎn)的高度是從下向上逐層計(jì)算的：葉結(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)。ABCDEFGHILKJ高度=4深度=3當(dāng)前第9頁\共有201頁\編于星期五\0點(diǎn)二叉樹的五種不同形態(tài)LLRR二叉樹(BinaryTree)二叉樹的定義

一棵二叉樹是結(jié)點(diǎn)的一個有限集合，該集合或者為空，或者是由一個根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。這個定義是遞歸的。當(dāng)前第10頁\共有201頁\編于星期五\0點(diǎn)二叉樹的性質(zhì)性質(zhì)1

若二叉樹的層次從1開始,則在二叉樹的第i層最多有2i-1

個結(jié)點(diǎn)。(i≥1)[證明用數(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ì)成立。當(dāng)前第11頁\共有201頁\編于星期五\0點(diǎn)性質(zhì)2高度為h的二叉樹最多有2h

-1個結(jié)點(diǎn)。(h≥1)[證明用求等比級數(shù)前k項(xiàng)和的公式] 高度為h的二叉樹有h

層，各層最多結(jié)點(diǎn)個數(shù)相加，得到等比級數(shù)，求和得： 20+21+22+…+2h-1=2h-1

空樹的高度為0，只有根結(jié)點(diǎn)的樹的高度為1。當(dāng)前第12頁\共有201頁\編于星期五\0點(diǎn)性質(zhì)3

對任何一棵二叉樹,如果其葉結(jié)點(diǎn)有

n0

個,度為2的非葉結(jié)點(diǎn)有

n2

個,則有

n0＝n2＋1證明： 若設(shè)度為1的結(jié)點(diǎn)有n1個，總結(jié)點(diǎn)個數(shù)為n，總邊數(shù)為e，則根據(jù)二叉樹的定義，

n=n0+n1+n2e=2n2+n1=n-1 因此，有

2n2+n1=n0+n1+n2-1 n2=n0-1

n0=n2+1

引申：可用于判斷二叉樹各類結(jié)點(diǎn)個數(shù)。當(dāng)前第13頁\共有201頁\編于星期五\0點(diǎn)定義1

滿二叉樹(FullBinaryTree)

定義2

完全二叉樹(CompleteBinaryTree)若設(shè)二叉樹的高度為h，則共有h

層。除第

h

層外，其它各層(1～h-1)的結(jié)點(diǎn)數(shù)都達(dá)到最大個數(shù)，第h

層從右向左連續(xù)缺若干結(jié)點(diǎn)，這就是完全二叉樹。當(dāng)前第14頁\共有201頁\編于星期五\0點(diǎn)性質(zhì)4

具有n(n≥0)個結(jié)點(diǎn)的完全二叉樹的高度為

log2(n+1)

證明：設(shè)完全二叉樹的高度為h，則有

2h-1-1＜n

≤2h-1

上面h-1層結(jié)點(diǎn)數(shù)

包括第h層的最大結(jié)點(diǎn)數(shù)變形 2h-1＜n+1≤2h

取對數(shù)

h-1＜log2(n+1)≤h

有 h=log2(n+1)

23-124-1當(dāng)前第15頁\共有201頁\編于星期五\0點(diǎn)23-124-1注意：求高度的另一公式為log2n+1,此公式對于n=0

不適用。若設(shè)完全二叉樹中葉結(jié)點(diǎn)有n0

個,則該二叉樹總的結(jié)點(diǎn)數(shù)為n=2n0,或n=2n0–1。若完全二叉樹的結(jié)點(diǎn)數(shù)為奇數(shù)，沒有度為1的結(jié)點(diǎn)；為偶數(shù)，有一個度為1的結(jié)點(diǎn)。右圖為理想平衡樹， 上層都是滿的，第

h層結(jié)點(diǎn)分布在各 處。當(dāng)前第16頁\共有201頁\編于星期五\0點(diǎn)性質(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,

則其右兄弟為i+1。0123745689當(dāng)前第17頁\共有201頁\編于星期五\0點(diǎn)注意：

如果完全二叉樹各層次結(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。12348567910當(dāng)前第18頁\共有201頁\編于星期五\0點(diǎn)完全二叉樹一般二叉樹的順序表示的順序表示00123456789130123567811131378945620126537811491012二叉樹的順序表示當(dāng)前第19頁\共有201頁\編于星期五\0點(diǎn)02614300261430極端情形:只有右單支的二叉樹對于完全二叉樹，因結(jié)點(diǎn)編號連續(xù)，數(shù)據(jù)存儲密集，適于用順序表示；對于一般二叉樹，用鏈表表示較好；當(dāng)前第20頁\共有201頁\編于星期五\0點(diǎn)lchilddatarchilddatalchildrchild左子女指針右子女指針二叉樹的二叉鏈表表示使用二叉鏈表，找子女的時間復(fù)雜度為O(1)，找雙親的時間復(fù)雜度為O(log2i)～O(i)，其中，i

是該結(jié)點(diǎn)編號。當(dāng)前第21頁\共有201頁\編于星期五\0點(diǎn)lchilddataparentrchildparentdatalchildrchild左子女指針雙親指針右子女指針二叉樹的三叉鏈表表示使用三叉鏈表，找子女、雙親的時間都是O(1)。當(dāng)前第22頁\共有201頁\編于星期五\0點(diǎn)AAABBBCCCDDDFFFEEErootrootroot二叉樹二叉鏈表三叉鏈表二叉樹鏈表表示的示例當(dāng)前第23頁\共有201頁\編于星期五\0點(diǎn)二叉樹的定義typedefcharTElemType; //樹結(jié)點(diǎn)數(shù)據(jù)類型typedefstructnode{ //樹結(jié)點(diǎn)定義

TElemType

data; //結(jié)點(diǎn)數(shù)據(jù)域

structnode*lchild,*rchild;

//子女指針域}BiTNode;typedefBiTNode*BinTree;

//樹定義，代表樹的根指針

當(dāng)前第24頁\共有201頁\編于星期五\0點(diǎn)二叉樹遍歷樹的遍歷就是按某種次序訪問樹中的結(jié)點(diǎn)，要求每個結(jié)點(diǎn)訪問一次且僅訪問一次。設(shè)訪問根結(jié)點(diǎn)記作V，遍歷根的左子樹記作L，遍歷根的右子樹記作R，則可能的遍歷次序有前序VLR鏡像VRL中序LVR鏡像RVL后序LRV鏡像RLV

當(dāng)前第25頁\共有201頁\編于星期五\0點(diǎn)中序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則中序遍歷左子樹(L)；訪問根結(jié)點(diǎn)(V)；中序遍歷右子樹(R)。遍歷結(jié)果

a+b*c-d-e/f中序遍歷(InorderTraversal)--/+*abcdef當(dāng)前第26頁\共有201頁\編于星期五\0點(diǎn)二叉樹遞歸的中序遍歷算法voidInOrder(BiTNode*T){

if(T!=NULL){InOrder(T->lchild);visit(T->data);InOrder(T->rchild);

}}visit()是輸出數(shù)據(jù)值的操作，在實(shí)際使用時可用相應(yīng)的操作來替換。當(dāng)前第27頁\共有201頁\編于星期五\0點(diǎn)前序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則訪問根結(jié)點(diǎn)(V)；前序遍歷左子樹(L)；前序遍歷右子樹(R)。遍歷結(jié)果

-+a*b-cd/ef前序遍歷(PreorderTraversal)--/+*abcdef當(dāng)前第28頁\共有201頁\編于星期五\0點(diǎn)二叉樹遞歸的前序遍歷算法voidPreOrder(BiTNode*T){

if(T!=NULL){visit(T->data);PreOrder(T->lchild);PreOrder(T->rchild);

}}與中序遍歷算法相比，visit()

操作放在兩個子樹遞歸前序遍歷的最前面。當(dāng)前第29頁\共有201頁\編于星期五\0點(diǎn)后序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則后序遍歷左子樹(L)；后序遍歷右子樹(R)；訪問根結(jié)點(diǎn)(V)。遍歷結(jié)果

abcd-*+ef/-后序遍歷(PostorderTraversal)d--/+*abcdef當(dāng)前第30頁\共有201頁\編于星期五\0點(diǎn)二叉樹遞歸的后序遍歷算法voidPostOrder(BiTNode*T){

if(T!=NULL){PostOrder(T->lchild);PostOrder(T->rchild);visit(T->data);

}}與中序遍歷算法相比，visit()

操作放在兩個子樹遞歸前序遍歷的最后面。當(dāng)前第31頁\共有201頁\編于星期五\0點(diǎn)計(jì)算二叉樹結(jié)點(diǎn)個數(shù)的遞歸算法應(yīng)用二叉樹遍歷的事例intCount(BiTNode*T){

if(T==NULL)return0;

else

return1+Count(T->lchild)+Count(T->rchild);}空二叉樹的結(jié)點(diǎn)個數(shù)為0，可直接計(jì)算；否則可分別計(jì)算左、右子樹的結(jié)點(diǎn)個數(shù)，再相加得到總結(jié)點(diǎn)個數(shù)。當(dāng)前第32頁\共有201頁\編于星期五\0點(diǎn)求二叉樹高度的遞歸算法intHeight(BiTNode*T){if(T==NULL)return0;

else{intm=

Height(T->lchild);intn=

Height(T->rchild));return(m>n)?m+1:n+1;

}空樹的高度為0；非空樹情形，先計(jì)算根結(jié)點(diǎn)左右子樹的高度，取大者再加一得到二叉樹高度。當(dāng)前第33頁\共有201頁\編于星期五\0點(diǎn)abcecdcc訪問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é)束利用棧的前序遍歷的非遞歸算法ddc當(dāng)前第34頁\共有201頁\編于星期五\0點(diǎn)voidPreOrder(BinTreeT){stackS;InitStack(S);

//遞歸工作棧

BiTNode*p=T;Push(S,NULL);

while(p!=NULL){visit(p->data);if(p->rchild!=NULL)Push(S,p->rchild);if(p->lchild!=NULL)p=p->lchild; //進(jìn)左子樹

elsePop(S,p); //左子樹空,進(jìn)右子樹

}}

當(dāng)前第35頁\共有201頁\編于星期五\0點(diǎn)abcdebaadaa左空退棧訪問左空退棧訪問退棧訪問左空ec退棧訪問cc右空退棧訪問棧空結(jié)束利用棧的中序遍歷的非遞歸算法當(dāng)前第36頁\共有201頁\編于星期五\0點(diǎn)

voidInOrder(BinTreeT){stackS;InitStack(S);//遞歸工作棧

BiTNode*p=

T;

//初始化

do{

while(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));}當(dāng)前第37頁\共有201頁\編于星期五\0點(diǎn)后序遍歷時使用的棧的結(jié)點(diǎn)定義 typedefstruct

{ BiTNode*ptr; //結(jié)點(diǎn)指針

enumtag{L,R};//該結(jié)點(diǎn)退棧標(biāo)記 }StackNode;

根結(jié)點(diǎn)的tag=L，表示從左子樹退出,訪問右子樹。tag=R,表示從右子樹退出,訪問根。ptrtag{L,R}

利用棧的后序遍歷的非遞歸算法當(dāng)前第38頁\共有201頁\編于星期五\0點(diǎn)abcdeaLbLaLbRaLdLbRaLdRbRaLbRaLaLaReLcLaReRcLaRcLaRcRaRaR當(dāng)前第39頁\共有201頁\編于星期五\0點(diǎn)利用棧的后序遍歷的非遞歸算法voidPostOrder(BinTreeT){stackS;InitStack(S);StackNode

w;BiTNode*p=T;

do{

while(p!=NULL){ //向左子樹走

w.ptr=p;w.tag=L;Push(S,w);

p=p->lchild; }

intsucc=1; //繼續(xù)循環(huán)標(biāo)記當(dāng)前第40頁\共有201頁\編于星期五\0點(diǎn)

while(succ&&!StackEmpty(S)){Pop(S,w);p=w.ptr;

switch(w.tag){

//判斷棧頂tag標(biāo)記

caseL:w.tag=R;Push(S,w); succ=0;

p=p->rchild;break; caseR:visit(p->data);

}}}

while(!StackEmpty(S));}當(dāng)前第41頁\共有201頁\編于星期五\0點(diǎn)二叉樹的計(jì)數(shù)由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹。例,前序序列

{ABHFDECKG}和中序序列

{HBDFAEKCG},構(gòu)造二叉樹過程如下：HBDFEKCGAEKCGABHDF當(dāng)前第42頁\共有201頁\編于星期五\0點(diǎn)KCGEKCGABHDFEKCGABHFDEABHFDEABHFDCKG當(dāng)前第43頁\共有201頁\編于星期五\0點(diǎn)612345789612375849如果前序序列固定不變，給出不同的中序序列，可得到不同的二叉樹。問題是：固定前序排列，選擇所有可能的中序排列，可以構(gòu)造出多少種不同的二叉樹？當(dāng)前第44頁\共有201頁\編于星期五\0點(diǎn)123123123123123例如,有3個數(shù)據(jù){1,2,3}，可得5種不同的二叉樹。它們的前序排列均為123，中序序列可能是123，132，213，231，321。那么，如何推廣到一般情形呢？首先，只有一個結(jié)點(diǎn)的不同二叉樹只有一個；有2個結(jié)點(diǎn)的不同二叉樹只有2種，其他情況呢？當(dāng)前第45頁\共有201頁\編于星期五\0點(diǎn)b0=1b1=1b2=2b3=5

b4=14有0個,1個,2個,3個結(jié)點(diǎn)的不同二叉樹如下當(dāng)前第46頁\共有201頁\編于星期五\0點(diǎn)bibn-i-11計(jì)算具有n個結(jié)點(diǎn)的不同二叉樹的棵數(shù)Catalan函數(shù)例當(dāng)前第47頁\共有201頁\編于星期五\0點(diǎn)線索二叉樹(ThreadedBinaryTree)又稱為穿線樹。通過二叉樹遍歷，可將二叉樹中所有結(jié)點(diǎn)的數(shù)據(jù)排列在一個線性序列中，可以找到某數(shù)據(jù)在這種排列下它的前驅(qū)和后繼。希望不必每次都通過遍歷找出這樣的線性序列。只要事先做預(yù)處理，將某種遍歷順序下的前驅(qū)、后繼關(guān)系記在樹的存儲結(jié)構(gòu)中，以后就可以高效地找出某結(jié)點(diǎn)的前驅(qū)、后繼。為此，在二叉樹存儲結(jié)點(diǎn)中增加線索信息。當(dāng)前第48頁\共有201頁\編于星期五\0點(diǎn)線索(Thread)增加前驅(qū)Pred指針和后繼Succ指針的二叉樹predlchilddatarchildsuccabcdepredpredpredsuccsuccsuccD∧∧AE∧∧B∧∧C∧∧rootpredpredpredpredsuccsuccsuccsucc當(dāng)前第49頁\共有201頁\編于星期五\0點(diǎn)這種設(shè)計(jì)的缺點(diǎn)是每個結(jié)點(diǎn)增加兩個指針，當(dāng)結(jié)點(diǎn)數(shù)很大時存儲消耗較大。改造樹結(jié)點(diǎn)，將pred指針和succ指針壓縮到lchild和rchild的空閑指針中，并增設(shè)兩個標(biāo)志ltag和rtag，指明指針是指示子女還是前驅(qū)／后繼。后者稱為線索。ltag(或rtag)=0，表示相應(yīng)指針指示左子女（或右子女結(jié)點(diǎn)）；ltag(或rtag)=1,表示相應(yīng)指針為前驅(qū)（或后繼）線索。lchildltagdatartagrchild

當(dāng)前第50頁\共有201頁\編于星期五\0點(diǎn)中序線索二叉樹及其鏈表表示lchildltagdatartagrchild

abcdepredpredpredsuccsuccsuccDAEB∧C∧rootpredpredsuccsucc0000111111當(dāng)前第51頁\共有201頁\編于星期五\0點(diǎn)typedefintTTElemType;typedefstructnode{

intltag,rtag;

structnode*lchild,*rchild;

TTElemTypedata;}ThreadNode,*ThreadTree;注意，線索二叉樹在樹結(jié)點(diǎn)中增加了ltag和rtag，改變了二叉樹的結(jié)構(gòu)。線索二叉樹的結(jié)構(gòu)定義當(dāng)前第52頁\共有201頁\編于星期五\0點(diǎn)通過中序遍歷建立中序線索二叉樹voidInThread(ThreadNode*t,

ThreadNode*&pre){

//預(yù)設(shè)了一個pre指針，指示t的中序前驅(qū)，在主

//程序中預(yù)置為NULL

if(t!=NULL){ InThread(t->lchild,pre);

//遞歸,左子樹線索化

if(t->lchild==NULL){ t->lchild=pre;t->ltag=1;}

//建立當(dāng)前結(jié)點(diǎn)t的前驅(qū)線索

當(dāng)前第53頁\共有201頁\編于星期五\0點(diǎn)

if(pre&&pre->rchild==NULL){pre->rchild=t;pre->rtag=1;

}

//建立前驅(qū)結(jié)點(diǎn)pre的后繼線索

pre=t; //前驅(qū)跟上當(dāng)前指針

InThread(t->rchild,pre);

//遞歸,右子樹線索化

}}使用此函數(shù)可以把以t為根的子樹一次中序線索化，但中序下最后一個結(jié)點(diǎn)的后繼線索沒有加上，指針

pre

在退出時正在指示這一結(jié)點(diǎn)。當(dāng)前第54頁\共有201頁\編于星期五\0點(diǎn)voidCreateInThread(ThreadTreeT){ThreadNode*pre=NULL; //前驅(qū)指針

if(T!=NULL){

//樹非空,線索化

InThread(T,pre); //中序遍歷線索二叉樹

pre->rchild=NULL;pre->rtag=1;

//后處理,中序最后一個結(jié)點(diǎn)

}}通過該主程序?qū)崿F(xiàn)了對二叉樹的中序線索化。它是基于二叉樹的中序遍歷實(shí)現(xiàn)的。當(dāng)前第55頁\共有201頁\編于星期五\0點(diǎn)0A00B0

0C00D00E0Tpre==NULLt當(dāng)前第56頁\共有201頁\編于星期五\0點(diǎn)0A0

1B0

0C00D00E0Tpre==NULLt當(dāng)前第57頁\共有201頁\編于星期五\0點(diǎn)0A0

1B0

0C0

1D00E0Tpret當(dāng)前第58頁\共有201頁\編于星期五\0點(diǎn)0A0

1B0

0C0

1D1

0E0Tpret當(dāng)前第59頁\共有201頁\編于星期五\0點(diǎn)0A0

1B0

0C0

1D1

1E0Tpret當(dāng)前第60頁\共有201頁\編于星期五\0點(diǎn)0A0

1B0

0C0

1D1

1E1

Tpret當(dāng)前第61頁\共有201頁\編于星期五\0點(diǎn)0A0

1B0

0C1

1D1

1E1

Tpre后處理當(dāng)前第62頁\共有201頁\編于星期五\0點(diǎn)尋找結(jié)點(diǎn)p在中序下的后繼if(p->rtag==1)

后繼為

p->rchildelse

//p->rtag!=1

后繼為結(jié)點(diǎn)

p右子樹

q中的中序下的第一個結(jié)點(diǎn)ABDECFHIKGJ當(dāng)前第63頁\共有201頁\編于星期五\0點(diǎn)ThreadNode

*First(ThreadNode

*t){//函數(shù)返回以*t為根的線索二叉樹中的中序序列下//的第一個結(jié)點(diǎn)

ThreadNode*p=t;

while(p->ltag==0)p=p->lchild;

returnp; //最左下的結(jié)點(diǎn)}ThreadNode*Next(ThreadNode

*p){//函數(shù)返回在線索二叉樹中結(jié)點(diǎn)*p在中序下的后//繼結(jié)點(diǎn)當(dāng)前第64頁\共有201頁\編于星期五\0點(diǎn)

if(p->rtag==0)returnFirst(p->rchild);

//p->rtag==0,后繼為右子樹中序第一個結(jié)點(diǎn)

else

returnp->rchild;

//p->rtag==1,直接返回后繼線索}voidInorder(ThreadNode*t){//以t為根的線索二叉樹的中序遍歷

ThreadNode*p;for(p=First(t);p!=NULL;p=Next(p))

cout<<p->data<<endl;}

當(dāng)前第65頁\共有201頁\編于星期五\0點(diǎn)尋找結(jié)點(diǎn)p在中序下的前驅(qū)if(p->ltag==1)

前驅(qū)為

p->lchildelse

//p->leftThread==0

前驅(qū)為結(jié)點(diǎn)

p

左子樹中序下的最后一個結(jié)點(diǎn)ABDECFHIKGJL當(dāng)前第66頁\共有201頁\編于星期五\0點(diǎn)前序序列

ABDCEp->ltag==1?前驅(qū)線索

=左子女p->rchild==NULL后繼為p->lchild=無后繼

后繼為p->rchildABCED前序線索二叉樹在前序線索二叉樹中尋找當(dāng)前結(jié)點(diǎn)的后繼當(dāng)前第67頁\共有201頁\編于星期五\0點(diǎn)后序序列

DBECAp->rtag==1?后繼線索

=右子女后繼為q的右子樹中后序下第一個結(jié)點(diǎn)

后繼為p->rchild=無后繼

后繼為qABCEDq=p->parentq==NULL?q->rtag==1||q->rchild==p?=后序線索二叉樹在后序線索二 叉樹中尋找當(dāng) 前結(jié)點(diǎn)的后繼當(dāng)前第68頁\共有201頁\編于星期五\0點(diǎn)樹的存儲表示

雙親表示為了操作實(shí)現(xiàn)的方便，有時會規(guī)定結(jié)點(diǎn)的存放順序。例如，可以按樹的前序次序存放樹中的各個結(jié)點(diǎn)，或按樹的層次次序安排所有結(jié)點(diǎn)。樹與樹的遍歷ABCDEFGdataparentABCDEFG-10001130123456當(dāng)前第69頁\共有201頁\編于星期五\0點(diǎn)子女鏈表表示無序樹情形鏈表中各結(jié)點(diǎn)順序任意，有序樹必須自左向右鏈接各個子女結(jié)點(diǎn)。ABCDEFG123∧45∧6∧∧∧∧∧ABCDEFG0123456當(dāng)前第70頁\共有201頁\編于星期五\0點(diǎn)子女指針表示一個合理的想法是在結(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)。當(dāng)前第71頁\共有201頁\編于星期五\0點(diǎn)等數(shù)量的鏈域ABCDEFG

datachild1child2child3childdABCDEFG空鏈域2n+1個當(dāng)前第72頁\共有201頁\編于星期五\0點(diǎn)子女-兄弟表示也稱為樹的二叉樹表示。結(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沿鏈掃描。

datafirstChildnextSibling當(dāng)前第73頁\共有201頁\編于星期五\0點(diǎn)樹的左子女-

右兄弟表示

datafchildnsiblingABCDEFGABCDGFE當(dāng)前第74頁\共有201頁\編于星期五\0點(diǎn)左子女-右兄弟表示的樹的結(jié)構(gòu)定義typedefintTElemType;typedefstructnode{

TElemTypedata;

structnode*fchild,*nsibling;}CSNode,*CSTree;注意，雖然此定義與二叉樹的類似，操作也類似，但語義是不同的。樹結(jié)構(gòu)是遞歸的，可用遞歸函數(shù)實(shí)現(xiàn)相應(yīng)操作。當(dāng)前第75頁\共有201頁\編于星期五\0點(diǎn)尋找雙親子女兄弟的操作TreeNode*FindParent(CSNode*T,CSNode*p){//在以T為根的樹中找結(jié)點(diǎn)p的雙親

if(T==NULL||p==NULL)returnNULL;CSNode*q=T->fchild,*s;

while(q!=NULL&&q!=p){

//循根的長子的兄弟鏈,遞歸在子樹中搜索

if((s=FindParent(q,p))!=NULL)returns;

//在以q為根的子樹找到p的雙親，返回

q=q->nsibling;

}當(dāng)前第76頁\共有201頁\編于星期五\0點(diǎn)

if(q!=NULL&&q==p)returnT;//找到雙親

elsereturnNULL;//未找到雙親}TreeNode*FindfirstChild(CSNode*p){//在樹中找結(jié)點(diǎn)p的第一個子女

if(p!=NULL)returnp->fchild;

else

returnNULL;};TreeNode*FindnextSibling(CSNode*p){//在樹中找結(jié)點(diǎn)p的兄弟當(dāng)前第77頁\共有201頁\編于星期五\0點(diǎn)

if(p!=NULL

)returnp->nsibling;

elsereturnNULL;}深度優(yōu)先遍歷先根次序遍歷后根次序遍歷廣度優(yōu)先遍歷樹的遍歷ABCDEFGABCEDGF二叉樹表示當(dāng)前第78頁\共有201頁\編于星期五\0點(diǎn)當(dāng)樹非空時訪問根結(jié)點(diǎn)依次先根遍歷根的各棵子樹樹先根遍歷ABEFCDG 對應(yīng)二叉樹前序遍歷ABEFCDG樹的先根遍歷結(jié)果與其對應(yīng)二叉樹 表示的前序遍歷結(jié)果相同樹的先根遍歷可以借助對應(yīng)二叉樹的前序遍歷算法實(shí)現(xiàn)ABCEDGF樹的先根次序遍歷ABCDEFG當(dāng)前第79頁\共有201頁\編于星期五\0點(diǎn)樹的先根次序遍歷的遞歸算法voidPreOrder

(CSNode*t){ //以指針t為根,先根次序遍歷

if(t!=NULL){visit(t->data);

//訪問根結(jié)點(diǎn)

CSNode*p

=t->fchild;

//第一棵子樹

while(p!=NULL){

PreOrder(p); //遞歸先根遍歷子樹

p=p->nsibling;}}}當(dāng)前第80頁\共有201頁\編于星期五\0點(diǎn)當(dāng)樹非空時依次后根遍歷根的各棵子樹訪問根結(jié)點(diǎn)樹后根遍歷EFBCGDA 對應(yīng)二叉樹中序遍歷EFBCGDA樹的后根遍歷結(jié)果與其對應(yīng)二叉樹 表示的中序遍歷結(jié)果相同樹的后根遍歷可以借助對應(yīng)二叉樹的中序遍歷算法實(shí)現(xiàn)ABCEDGF樹的后根次序遍歷ABCDEFG當(dāng)前第81頁\共有201頁\編于星期五\0點(diǎn)樹的后根次序遍歷的遞歸算法voidPostOrder(CSNode*t){//以指針t為根,按后根次序遍歷樹

if(t!=NULL){CSNode

*p=t->fchild;while(p!=NULL){ PostOrder(p);

p=p->nsibling;

}visit(t->data); //最后訪問根結(jié)點(diǎn)

}}當(dāng)前第82頁\共有201頁\編于星期五\0點(diǎn)按廣度優(yōu)先次序遍歷樹的結(jié)果

ABCDEFG廣度優(yōu)先遍歷算法 voidLevelOrder(CSTreeT){

//分層遍歷樹，算法用到一個隊(duì)列

QueueQ;InitQueue(Q);

CSNode*p; if(T!=NULL){ //樹不空

EnQueue(Q,T); //根結(jié)點(diǎn)進(jìn)隊(duì)列廣度優(yōu)先(層次次序)遍歷ABCEDGFABCDEFG當(dāng)前第83頁\共有201頁\編于星期五\0點(diǎn)

while(!QueueEmpty(Q)){

DeQueue(Q,p);visit(p->data);

//隊(duì)列中取一個并訪問之

p=p->fchild;

//待訪問結(jié)點(diǎn)的子女結(jié)點(diǎn)進(jìn)隊(duì)列

while(p!=NULL){

EnQueue(Q,p);p=p->nsibling;

}}

}}當(dāng)前第84頁\共有201頁\編于星期五\0點(diǎn)森林與二叉樹的轉(zhuǎn)換將一般樹化為二叉樹表示就是用樹的子女-兄弟表示來存儲樹的結(jié)構(gòu)。森林與二叉樹表示的轉(zhuǎn)換可以借助樹的二叉樹表示來實(shí)現(xiàn)。當(dāng)前第85頁\共有201頁\編于星期五\0點(diǎn)T1T2T3AFHT1T2T3ABCDGIJEKFBCDEGHIKJABCEDHIKJFG3

棵樹的森林各棵樹的二叉樹表示森林的二叉樹表示當(dāng)前第86頁\共有201頁\編于星期五\0點(diǎn)森林轉(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)成的森林。當(dāng)前第87頁\共有201頁\編于星期五\0點(diǎn)二叉樹轉(zhuǎn)換為森林的規(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)換而成的森林。當(dāng)前第88頁\共有201頁\編于星期五\0點(diǎn)例題設(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)化成的二叉樹中根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)是除第一棵外其他樹上的結(jié)點(diǎn)，應(yīng)有m2+m3個，故選擇B。

當(dāng)前第89頁\共有201頁\編于星期五\0點(diǎn)森林的遍歷森林的遍歷也分為深度優(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)成的森林。當(dāng)前第90頁\共有201頁\編于星期五\0點(diǎn)若森林F=?，返回；否則訪問森林的根（也是第一棵樹的根）r1；先根遍歷森林第一棵樹的根的子樹森林{T11,…,T1k}；先根遍歷森林中除第一棵樹外其他樹組成的森林{T2,...,Tm}。注意，②是一個循環(huán)，對于每一個T1i，執(zhí)行樹的先根次序遍歷；③

是一個遞歸過程，重新執(zhí)行T2

為第一棵樹的森林的先根次序遍歷。森林的先根次序遍歷當(dāng)前第91頁\共有201頁\編于星期五\0點(diǎn)森林的先根次序遍歷的結(jié)果序列

ABCDEFGHIKJ這相當(dāng)于對應(yīng)二叉樹的前序遍歷結(jié)果。T1T2T3AFHBCDGIJEKBAEDHIKJFGC當(dāng)前第92頁\共有201頁\編于星期五\0點(diǎn)森林的中根次序遍歷若森林F=?，返回；否則中根遍歷森林

F

第一棵樹的根結(jié)點(diǎn)的子樹森林{T11,…,T1k}；訪問森林的根結(jié)點(diǎn)r1；中根遍歷森林中除第一棵樹外其他樹組成的森林{T2,...,Tm}。注意，與先根次序遍歷相比，訪問根結(jié)點(diǎn)的時機(jī)不同。所以在③的情形，對以T2為第一棵樹的森林遍歷時，重復(fù)執(zhí)行①②③的操作。當(dāng)前第93頁\共有201頁\編于星期五\0點(diǎn)森林的中根次序遍歷的結(jié)果序列

BCEDAGFKIJH這相當(dāng)于對應(yīng)二叉樹中序遍歷的結(jié)果。T1T2T3AFHBCDGIJEKBAEDHIKJFGC當(dāng)前第94頁\共有201頁\編于星期五\0點(diǎn)廣度優(yōu)先遍歷（層次序遍歷）AFHBCDGIJEKABCEDHIKJFG若森林F

為空，返回； 否則依次遍歷各棵樹的 根結(jié)點(diǎn)；依次遍歷各棵樹根 結(jié)點(diǎn)的所有子女；依次遍歷這些子女 結(jié)點(diǎn)的子女結(jié)點(diǎn)；當(dāng)前第95頁\共有201頁\編于星期五\0點(diǎn)樹的應(yīng)用二叉排序樹平衡二叉樹Huffman樹堆并查集當(dāng)前第96頁\共有201頁\編于星期五\0點(diǎn)二叉排序樹(BinarySearchTree)定義

二叉排序樹或者是一棵空樹，或者是具有下列性質(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)鍵字。左子樹和右子樹也是二叉排序樹。當(dāng)前第97頁\共有201頁\編于星期五\0點(diǎn)351545504025102030二叉排序樹例結(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)稱為二叉搜索樹或二叉查找樹。當(dāng)前第98頁\共有201頁\編于星期五\0點(diǎn)例題一棵二叉樹是二叉排序樹的（）條件是樹中任一結(jié)點(diǎn)的關(guān)鍵字值都大于左子女的關(guān)鍵字值，小于右子女的關(guān)鍵字值。 A.充分但不必要B.必要但不充分C.充分且必要D.既不充分也不必要【解答】B。 通俗來講，必要條件是指符合定義則必具有后續(xù)講的特性。顯然一棵二叉樹是二叉排序樹，則樹中任一結(jié)點(diǎn)的關(guān)鍵字值一定大于左子女的關(guān)鍵字值，小于右子女的關(guān)鍵字值。充分條件是指滿足當(dāng)前第99頁\共有201頁\編于星期五\0點(diǎn)

后續(xù)講的特性則定義一定成立。就是說，如果一棵二叉樹任一結(jié)點(diǎn)的關(guān)鍵字值都大于左子女的關(guān)鍵字值，小于右子女的關(guān)鍵字值，則它一定是二叉排序樹。這就不一定了。

右圖描述的二叉樹滿足樹中 任一結(jié)點(diǎn)的關(guān)鍵字值一定大 于左子女的關(guān)鍵字值，小于 右子女的 關(guān)鍵字值，但它不 是二叉排序樹。2515353045102050當(dāng)前第100頁\共有201頁\編于星期五\0點(diǎn)

二叉排序樹的結(jié)構(gòu)定義typedefcharBSTElemType; //樹結(jié)點(diǎn)數(shù)據(jù)類型typedefstructnode{ //二叉排序樹結(jié)點(diǎn)

BSTElemType

data;

structnode*lchild,*rchild;}BSTNode,*BSTree; //二叉排序樹定義從面向?qū)ο笥^點(diǎn)來看，二叉排序樹是二叉樹的特殊情形，它繼承了二叉樹的結(jié)構(gòu)，增加了自己的特性，對數(shù)據(jù)的存放增加了約束。當(dāng)前第101頁\共有201頁\編于星期五\0點(diǎn)二叉排序樹上的查找查找45

查找成功

查找28查找失敗351545504025102030在二叉排序樹上進(jìn)行查找，是一個從根結(jié)點(diǎn)開始，沿某一個分支逐層向下進(jìn)行比較判等的過程。它可以是一個遞歸的過程。當(dāng)前第102頁\共有201頁\編于星期五\0點(diǎn)假設(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)。當(dāng)前第103頁\共有201頁\編于星期五\0點(diǎn)可用判定樹描述查找過程。內(nèi)結(jié)點(diǎn)是樹中原有結(jié)點(diǎn)，外結(jié)點(diǎn)是失敗結(jié)點(diǎn)，代表樹中沒有的數(shù)據(jù)。查找不成功時檢測指針停留在某個失敗結(jié)點(diǎn)。3515455025102030查找22查找45當(dāng)前第104頁\共有201頁\編于星期五\0點(diǎn)二叉排序樹的查找算法voidFind(BSTNode*t,BSTElemTypex,BSTNode*&p,BSTNode*&pr){//在二叉排序樹t中查找關(guān)鍵字等于x的結(jié)點(diǎn)，成功//時p返回找到結(jié)點(diǎn)地址,pr是其雙親結(jié)點(diǎn).不成功//時p為空,pr返回最后走到的結(jié)點(diǎn)地址.

p=t;pr=NULL; //從根查找if(p!=NULL){

while(p!=NULL&&p->data!=x){pr=p;if(p->data<x)p=p->rchild;

elsep=p->lchild;當(dāng)前第105頁\共有201頁\編于星期五\0點(diǎn)

}}}查找的關(guān)鍵字比較次數(shù)最多不超過樹的高度。每次結(jié)點(diǎn)的插入，都要從根結(jié)點(diǎn)出發(fā)查找插入位置，然后把新結(jié)點(diǎn)作為葉結(jié)點(diǎn)插入。為了向二叉排序樹中插入一個新元素，必須先檢查這個元素是否在樹中已經(jīng)存在。二叉排序樹的插入當(dāng)前第106頁\共有201頁\編于星期五\0點(diǎn)為此，在插入之前先使用查找算法在樹中檢查要插入元素有還是沒有。查找成功：樹中已有 這個元素,不再插入。查找不成功：樹中原 來沒有關(guān)鍵字等于給 定值的結(jié)點(diǎn)，把新元 素加到查找操作停止 的地方。35154550402510203028插入新結(jié)點(diǎn)28當(dāng)前第107頁\共有201頁\編于星期五\0點(diǎn)voidInsert

(BSTNode*&t,BSTElemTypex){//將新元素x插到以*t為根的二叉排序樹中

BstNode*pt,*prt,*q;

Find(t,x,pt,prt); //查找結(jié)點(diǎn)插入位置

if(pt==NULL){ //查找失敗時可插入

q=newBstNode;q->data=x; //創(chuàng)建結(jié)點(diǎn)

q->lchild=q->rchild=NULL;

if(prt==NULL)t=q;//空樹

else

if(x<prt->data)ptr->lchild=q;elseptr->rchild=q;}}當(dāng)前第108頁\共有201頁\編于星期五\0點(diǎn)535378537865537865175378658717537865091787537865811787095378651517870981輸入數(shù)據(jù)，建立二叉排序樹的過程輸入數(shù)據(jù){53,78,65,17,87,09,81,15}當(dāng)前第109頁\共有201頁\編于星期五\0點(diǎn)123111132223323同樣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}當(dāng)前第110頁\共有201頁\編于星期五\0點(diǎn)二叉排序樹的刪除在二叉排序樹中刪除一個結(jié)點(diǎn)時，必須將因刪除結(jié)點(diǎn)而斷開的二叉鏈表重新鏈接起來，同時確保二叉排序樹的性質(zhì)不會失去。為保證在刪除后樹的查找性能不至于降低，還需要防止重新鏈接后樹的高度增加。被刪結(jié)點(diǎn)的右子樹為空，可以拿它的左子女結(jié)點(diǎn)頂替它的位置，再釋放它。被刪結(jié)點(diǎn)的左子樹為空，可以拿它的右子女結(jié)點(diǎn)頂替它的位置，再釋放它。被刪結(jié)點(diǎn)的左、右子樹都不為空，可以在它當(dāng)前第111頁\共有201頁\編于星期五\0點(diǎn) 的右子樹中尋找中序下的第一個結(jié)點(diǎn)(所有比被刪關(guān)鍵字大的關(guān)鍵字中它的值最小),用它的值填補(bǔ)到被刪結(jié)點(diǎn)中，再來處理這個結(jié)點(diǎn)的刪除問題。當(dāng)然，也可以到它的左子樹中尋找中序下的最后一個結(jié)點(diǎn)。右子樹空,用左子女頂替5378651787092345刪除4553786517870923當(dāng)前第112頁\共有201頁\編于星期五\0點(diǎn)左子樹空,用右子女頂替在右子樹上找中序下第一個結(jié)點(diǎn)填補(bǔ)8853788817940923刪除7853948817092353788117940945刪除782365538188179409452365當(dāng)前第113頁\共有201頁\編于星期五\0點(diǎn)

二叉排序樹性能分析對于有n個關(guān)鍵字的集合，其關(guān)鍵字有n!

種不同排列，可構(gòu)成不同二叉排序樹有

(棵)用樹的查找效率來評價(jià)這些二叉排序樹。用判定樹來描述查找過程，在判定樹中，○表示內(nèi)結(jié)點(diǎn)，它包含關(guān)鍵字集合中的某一個關(guān)鍵字；□表示外結(jié)點(diǎn)，代表各關(guān)鍵字間隔中的不在關(guān)鍵字集合中的關(guān)鍵字。它們是查找失敗時到達(dá)的結(jié)點(diǎn),物理上實(shí)際不存在。當(dāng)前第114頁\共有201頁\編于星期五\0點(diǎn)在每兩個外部結(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。可能的判定樹如下所示。doiftodoiftoq0q1p1q2p2q3p3q0q1q2q3p1p2p3(a)(b)當(dāng)前第115頁\共有201頁\編于星期五\0點(diǎn)doiftoq0q1p1q2p2q3p3doiftoq0q1p1q2p2q3p3(d)(c)doiftoq0q1p1q2p2q3p3(e)當(dāng)前第116頁\共有201頁\編于星期五\0點(diǎn)一棵判定樹的查找成功的平均查找長度ASLsucc定義為該樹所有內(nèi)結(jié)點(diǎn)上的權(quán)值p[i]與查找該結(jié)點(diǎn)時所需的關(guān)鍵字比較次數(shù)c[i](=l[i])乘積之和：查找不成功的平均查找長度ASLunsucc為樹中所有外結(jié)點(diǎn)上權(quán)值q[j]與到達(dá)該外結(jié)點(diǎn)所需關(guān)鍵字比較次數(shù)c'[j](=l'[j]-1)乘積之和：當(dāng)前第117頁\共有201頁\編于星期五\0點(diǎn)相等查找概率的情形設(shè)樹中所有內(nèi)、外結(jié)點(diǎn)的查找概率都相等：

p[i]=1/3,1≤i≤3q[j]=1/4,0≤j≤3圖(a):

ASLsucc=1/3*(3+2+1)=6/3=2ASLunsucc=1/4*(3+3+2+1)=9/4圖(b):

ASLsucc=1/3*(2+1+2)=5/3ASLunsucc=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當(dāng)前第118頁\共有201頁\編于星期五\0點(diǎn)圖(b)的情形所得的平均查找長度最小。一般把平均查找長度達(dá)到最小的判定樹稱作最優(yōu)二叉排序樹。在相等查找概率的情形下，最優(yōu)二叉排序樹的上面h-1（h是高度）層都是滿的，只有第h

層不滿。如果結(jié)點(diǎn)集中在該層的左邊，則它是完全二叉樹；如果結(jié)點(diǎn)散落在該層各個地方，則有人稱之為理想平衡樹。當(dāng)前第119頁\共有201頁\編于星期五\0點(diǎn)平衡二叉樹

高度不平衡高度平衡ABCABCDEDE平衡二叉樹的定義一棵AVL樹或者是空樹，或者是具有下列性質(zhì)的二叉排序樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的高度之差的絕對值不超過1。當(dāng)前第120頁\共有201頁\編于星期五\0點(diǎn)

結(jié)點(diǎn)的平衡因子balancefactor每個結(jié)點(diǎn)附加一個數(shù)字，給出該結(jié)點(diǎn)左子樹的高度減去右子樹的高度所得的高度差，這個數(shù)字即為結(jié)點(diǎn)的平衡因子bf（balancefactor）。平衡二叉樹任一結(jié)點(diǎn)平衡因子只能取-1,0,1。如果一個結(jié)點(diǎn)的平衡因子的絕對值大于1，則這棵二叉排序樹就失去了平衡，不再是平衡二叉樹。如果一棵二叉排序樹是高度平衡的,且有n個結(jié)點(diǎn)，其高度可保持在O(log2n),平均查找長度也可保持在O(log2n)。當(dāng)前第121頁\共有201頁\編于星期五\0點(diǎn)平衡化旋轉(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)時，平衡二