數(shù)據(jù)結構清華大學殷人昆演示文稿

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

樹是由n(n＞0)個結點組成的有限集合：有一個特定的稱之為根(root)的結點；除根以外的其它結點劃分為m(m≥0)個互不相交的有限集合T1,T2,…,Tm，每個集合又是一棵樹，并且稱之為根的子樹。此定義是離散數(shù)學和圖論中給出的。它們把樹視為圖的一個極小連通子圖。有n個結點的樹有n-1條邊，而且不能有回路。當前第4頁\共有201頁\編于星期五\0點這種觀點的典型代表是

Knuth。他認為圖至少有一個頂點，樹也必須至少有一個頂點。樹不能是空樹，但N叉樹可以是空樹。N叉樹是限制根的子樹最多不能超過N棵的樹。隨著對樹討論的深入，人們放寬了對樹結構的限制。若把樹當作層次結構單獨對待，樹中允許結點個數(shù)為0。這樣，樹與N叉樹就沒有不可逾越的鴻溝了。從面向對象觀點，N叉樹是樹的特殊實現(xiàn)：樹是父類，N叉樹是子類。N叉樹繼承了樹的特性，它還有自己增加的特性，例如當前第5頁\共有201頁\編于星期五\0點理論上樹不可是空樹，N叉樹可以是空樹；樹的子樹可以有序，也可以不要求有序，而N叉樹的子樹必須有序。N叉樹的定義也是遞歸的，遞歸到空樹終止；樹則遞歸到只有一個結點的子樹。樹的子樹棵數(shù)不限，而N叉樹中根的子樹最多N棵。樹可以區(qū)分為外向樹和內(nèi)向樹，而N叉樹一般是外向樹，即邊是有向的，從父指向子。樹可以用N叉樹實現(xiàn)。二叉樹、B樹等又都是N叉樹的特殊情形。當前第6頁\共有201頁\編于星期五\0點樹的特點樹是分層結構，又是遞歸結構。每棵子樹的根結點有且僅有一個直接前驅，但可以有0個或多個直接后繼。1層2層4層3層depth=4height=4ACGBDEFKLHMIJ前驅后繼當前第7頁\共有201頁\編于星期五\0點1層2層4層3層depth=4height=4ACGBDEFKLHMIJ結點結點的度分支結點葉結點子女雙親兄弟祖先樹的度樹深度樹高度森林子孫結點層次結點深度結點高度當前第8頁\共有201頁\編于星期五\0點注意，結點的深度和結點的高度是不同的。結點的深度即結點所處層次，是從根向下逐層計算的；結點的高度是從下向上逐層計算的：葉結點的高度為1,其他結點的高度是取它的所有子女結點最大高度加一。樹的深度與高度相等。 樹的深度按離根最遠的 葉結點算，樹的高度按 根結點算，都是6。葉結點也稱為終端結點， 非葉結點也稱為非終端 結點。ABCDEFGHILKJ高度=4深度=3當前第9頁\共有201頁\編于星期五\0點二叉樹的五種不同形態(tài)LLRR二叉樹(BinaryTree)二叉樹的定義

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

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

個結點。(i≥1)[證明用數(shù)學歸納法]i=1時，根結點只有1個，21-1=20=1；若設i=k

時性質成立，即該層最多有2k-1

個結點，則當i=k+1

時，由于第k

層每個結點最多可有2個子女，第k+1層最多結點個數(shù)可有2*2k-1=2k

個，故性質成立。當前第11頁\共有201頁\編于星期五\0點性質2高度為h的二叉樹最多有2h

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

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

空樹的高度為0，只有根結點的樹的高度為1。當前第12頁\共有201頁\編于星期五\0點性質3

對任何一棵二叉樹,如果其葉結點有

n0

個,度為2的非葉結點有

n2

個,則有

n0＝n2＋1證明： 若設度為1的結點有n1個，總結點個數(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

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

滿二叉樹(FullBinaryTree)

定義2

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

層。除第

h

層外，其它各層(1～h-1)的結點數(shù)都達到最大個數(shù)，第h

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

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

log2(n+1)

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

2h-1-1＜n

≤2h-1

上面h-1層結點數(shù)

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

取對數(shù)

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

有 h=log2(n+1)

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

不適用。若設完全二叉樹中葉結點有n0

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

h層結點分布在各 處。當前第16頁\共有201頁\編于星期五\0點性質5

如將一棵有n個結點的完全二叉樹自頂向下，同一層自左向右連續(xù)給結點編號:0,1,2,…,n-1，則有以下關系：

若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當前第17頁\共有201頁\編于星期五\0點注意：

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

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

TElemType

data; //結點數(shù)據(jù)域

structnode*lchild,*rchild;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

if(T==NULL)return0;

else

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

else{intm=

Height(T->lchild);intn=

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

}空樹的高度為0；非空樹情形，先計算根結點左右子樹的高度，取大者再加一得到二叉樹高度。當前第33頁\共有201頁\編于星期五\0點abcecdcc訪問a進棧c左進b訪問b進棧d左進空退棧d訪問d左進空退棧c訪問c左進e訪問e左進空退棧結束利用棧的前序遍歷的非遞歸算法ddc當前第34頁\共有201頁\編于星期五\0點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; //進左子樹

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

}}

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

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

BiTNode*p=

T;

//初始化

do{

while(p!=NULL) //子樹非空找中序第一個

{Push(S,p);p=p->lchild;}//邊找邊進棧

if(!StackEmpty(S)){

//棧非空

Pop(S,p);//子樹中序第一個退棧

visit(p->data);

//訪問之

p=p->rchild; //向右子樹走

}

}while(p!=NULL||!StackEmpty(S));}當前第37頁\共有201頁\編于星期五\0點后序遍歷時使用的棧的結點定義 typedefstruct

{ BiTNode*ptr; //結點指針

enumtag{L,R};//該結點退棧標記 }StackNode;

根結點的tag=L，表示從左子樹退出,訪問右子樹。tag=R,表示從右子樹退出,訪問根。ptrtag{L,R}

利用棧的后序遍歷的非遞歸算法當前第38頁\共有201頁\編于星期五\0點abcdeaLbLaLbRaLdLbRaLdRbRaLbRaLaLaReLcLaReRcLaRcLaRcRaRaR當前第39頁\共有201頁\編于星期五\0點利用棧的后序遍歷的非遞歸算法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)標記當前第40頁\共有201頁\編于星期五\0點

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

switch(w.tag){

//判斷棧頂tag標記

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

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

}}}

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

{ABHFDECKG}和中序序列

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

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

當前第50頁\共有201頁\編于星期五\0點中序線索二叉樹及其鏈表表示lchildltagdatartagrchild

abcdepredpredpredsuccsuccsuccDAEB∧C∧rootpredpredsuccsucc0000111111當前第51頁\共有201頁\編于星期五\0點typedefintTTElemType;typedefstructnode{

intltag,rtag;

structnode*lchild,*rchild;

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

ThreadNode*&pre){

//預設了一個pre指針，指示t的中序前驅，在主

//程序中預置為NULL

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

//遞歸,左子樹線索化

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

//建立當前結點t的前驅線索

當前第53頁\共有201頁\編于星期五\0點

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

}

//建立前驅結點pre的后繼線索

pre=t; //前驅跟上當前指針

InThread(t->rchild,pre);

//遞歸,右子樹線索化

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

pre

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

if(T!=NULL){

//樹非空,線索化

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

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

//后處理,中序最后一個結點

}}通過該主程序實現(xiàn)了對二叉樹的中序線索化。它是基于二叉樹的中序遍歷實現(xiàn)的。當前第55頁\共有201頁\編于星期五\0點0A00B0

0C00D00E0Tpre==NULLt當前第56頁\共有201頁\編于星期五\0點0A0

1B0

0C00D00E0Tpre==NULLt當前第57頁\共有201頁\編于星期五\0點0A0

1B0

0C0

1D00E0Tpret當前第58頁\共有201頁\編于星期五\0點0A0

1B0

0C0

1D1

0E0Tpret當前第59頁\共有201頁\編于星期五\0點0A0

1B0

0C0

1D1

1E0Tpret當前第60頁\共有201頁\編于星期五\0點0A0

1B0

0C0

1D1

1E1

Tpret當前第61頁\共有201頁\編于星期五\0點0A0

1B0

0C1

1D1

1E1

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

后繼為

p->rchildelse

//p->rtag!=1

后繼為結點

p右子樹

q中的中序下的第一個結點ABDECFHIKGJ當前第63頁\共有201頁\編于星期五\0點ThreadNode

*First(ThreadNode

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

ThreadNode*p=t;

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

returnp; //最左下的結點}ThreadNode*Next(ThreadNode

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

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

//p->rtag==0,后繼為右子樹中序第一個結點

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;}

當前第65頁\共有201頁\編于星期五\0點尋找結點p在中序下的前驅if(p->ltag==1)

前驅為

p->lchildelse

//p->leftThread==0

前驅為結點

p

左子樹中序下的最后一個結點ABDECFHIKGJL當前第66頁\共有201頁\編于星期五\0點前序序列

ABDCEp->ltag==1?前驅線索

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

后繼為p->rchildABCED前序線索二叉樹在前序線索二叉樹中尋找當前結點的后繼當前第67頁\共有201頁\編于星期五\0點后序序列

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

=右子女后繼為q的右子樹中后序下第一個結點

后繼為p->rchild=無后繼

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

雙親表示為了操作實現(xiàn)的方便，有時會規(guī)定結點的存放順序。例如，可以按樹的前序次序存放樹中的各個結點，或按樹的層次次序安排所有結點。樹與樹的遍歷ABCDEFGdataparentABCDEFG-10001130123456當前第69頁\共有201頁\編于星期五\0點子女鏈表表示無序樹情形鏈表中各結點順序任意，有序樹必須自左向右鏈接各個子女結點。ABCDEFG123∧45∧6∧∧∧∧∧ABCDEFG0123456當前第70頁\共有201頁\編于星期五\0點子女指針表示一個合理的想法是在結點中存放指向每一個子女結點的指針。但由于各個結點的子女數(shù)不同，每個結點設置數(shù)目不等的指針，將很難管理。為此，設置等長的結點，每個結點包含的指針個數(shù)相等，等于樹的度（degree）。這保證結點有足夠的指針指向它的所有子女結點。但可能產(chǎn)生很多空閑指針，造成存儲浪費。當前第71頁\共有201頁\編于星期五\0點等數(shù)量的鏈域ABCDEFG

datachild1child2child3childdABCDEFG空鏈域2n+1個當前第72頁\共有201頁\編于星期五\0點子女-兄弟表示也稱為樹的二叉樹表示。結點構造為：firstChild指向該結點的第一個子女結點。無序樹時，可任意指定一個結點為第一個子女。nextSibling指向該結點的下一個兄弟。任一結點在存儲時總是有順序的。若想找某結點的所有子女，可先找firstChild,再反復用nextSibling沿鏈掃描。

datafirstChildnextSibling當前第73頁\共有201頁\編于星期五\0點樹的左子女-

右兄弟表示

datafchildnsiblingABCDEFGABCDGFE當前第74頁\共有201頁\編于星期五\0點左子女-右兄弟表示的樹的結構定義typedefintTElemType;typedefstructnode{

TElemTypedata;

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

}當前第76頁\共有201頁\編于星期五\0點

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

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

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

else

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

if(p!=NULL

)returnp->nsibling;

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

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

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

//訪問根結點

CSNode*p

=t->fchild;

//第一棵子樹

while(p!=NULL){

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

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

if(t!=NULL){CSNode

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

p=p->nsibling;

}visit(t->data); //最后訪問根結點

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

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

//分層遍歷樹，算法用到一個隊列

QueueQ;InitQueue(Q);

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

EnQueue(Q,T); //根結點進隊列廣度優(yōu)先(層次次序)遍歷ABCEDGFABCDEFG當前第83頁\共有201頁\編于星期五\0點

while(!QueueEmpty(Q)){

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

//隊列中取一個并訪問之

p=p->fchild;

//待訪問結點的子女結點進隊列

while(p!=NULL){

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

}}

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

棵樹的森林各棵樹的二叉樹表示森林的二叉樹表示當前第86頁\共有201頁\編于星期五\0點森林轉化成二叉樹的規(guī)則若F為空，即n=0，則對應的二叉樹B為空樹。若F不空，則二叉樹B的根是F第一棵樹T1

的根；其左子樹為B(T11,T12,…,T1m)，其中，T11,T12,…,T1m

是T1的根的子樹；其右子樹為B(T2,T3,…,Tn)，其中，T2,T3,…,Tn

是除

T1

外其它樹構成的森林。當前第87頁\共有201頁\編于星期五\0點二叉樹轉換為森林的規(guī)則如果B為空，則對應的森林F也為空。如果B非空，則F中第一棵樹T1

的根為B的根；T1的根的子樹森林{T11,T12,…,T1m}

是由B的根的左子樹LB轉換而來；F中除了T1

之外其余的樹組成的森林{T2,T3,…,Tn}

是由B的根的右子樹RB轉換而成的森林。當前第88頁\共有201頁\編于星期五\0點例題設森林中有三棵樹，第一、第二和第三棵樹中的結點個數(shù)分別為m1，m2和m3。那么在由該森林轉化成的二叉樹中根結點的右子樹上有（）個結點。 A.m1+m2 B.m2+m3 C.m3+m1 D.m1+m2+m3【解答】在由森林轉化成的二叉樹中根結點的右子樹上的結點是除第一棵外其他樹上的結點，應有m2+m3個，故選擇B。

當前第89頁\共有201頁\編于星期五\0點森林的遍歷森林的遍歷也分為深度優(yōu)先遍歷（包括先根次序遍歷和中根次序遍歷）和廣度優(yōu)先遍歷。深度優(yōu)先遍歷給定森林F，若F=?，則遍歷結束。否則若F={{T1={r1,T11,…,T1k},T2,...,Tm}，則可以導出先根遍歷、中根遍歷兩種方法。其中，r1是第一棵樹的根結點，{T11,…,T1k}是第一棵樹的子樹森林，{T2,...,Tm}是除去第一棵樹之后剩余的樹構成的森林。當前第90頁\共有201頁\編于星期五\0點若森林F=?，返回；否則訪問森林的根（也是第一棵樹的根）r1；先根遍歷森林第一棵樹的根的子樹森林{T11,…,T1k}；先根遍歷森林中除第一棵樹外其他樹組成的森林{T2,...,Tm}。注意，②是一個循環(huán)，對于每一個T1i，執(zhí)行樹的先根次序遍歷；③

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

為第一棵樹的森林的先根次序遍歷。森林的先根次序遍歷當前第91頁\共有201頁\編于星期五\0點森林的先根次序遍歷的結果序列

ABCDEFGHIKJ這相當于對應二叉樹的前序遍歷結果。T1T2T3AFHBCDGIJEKBAEDHIKJFGC當前第92頁\共有201頁\編于星期五\0點森林的中根次序遍歷若森林F=?，返回；否則中根遍歷森林

F

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

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

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

二叉排序樹或者是一棵空樹，或者是具有下列性質的二叉樹：每個結點都有一個作為查找依據(jù)的關鍵字(key)，所有結點的關鍵字互不相同。左子樹（如果非空）上所有結點的關鍵字都小于根結點的關鍵字。右子樹（如果非空）上所有結點的關鍵字都大于根結點的關鍵字。左子樹和右子樹也是二叉排序樹。當前第97頁\共有201頁\編于星期五\0點351545504025102030二叉排序樹例結點左子樹上所有關鍵 字小于結點關鍵字；結點右子樹上所有關鍵 字大于結點關鍵字；如果對一棵二叉排序樹 進行中序遍歷，可以按 從小到大的順序將各結 點關鍵字排列起來。注意，國外教材統(tǒng)稱為二叉搜索樹或二叉查找樹。當前第98頁\共有201頁\編于星期五\0點例題一棵二叉樹是二叉排序樹的（）條件是樹中任一結點的關鍵字值都大于左子女的關鍵字值，小于右子女的關鍵字值。 A.充分但不必要B.必要但不充分C.充分且必要D.既不充分也不必要【解答】B。 通俗來講，必要條件是指符合定義則必具有后續(xù)講的特性。顯然一棵二叉樹是二叉排序樹，則樹中任一結點的關鍵字值一定大于左子女的關鍵字值，小于右子女的關鍵字值。充分條件是指滿足當前第99頁\共有201頁\編于星期五\0點

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

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

二叉排序樹的結構定義typedefcharBSTElemType; //樹結點數(shù)據(jù)類型typedefstructnode{ //二叉排序樹結點

BSTElemType

data;

structnode*lchild,*rchild;}BSTNode,*BSTree; //二叉排序樹定義從面向對象觀點來看，二叉排序樹是二叉樹的特殊情形，它繼承了二叉樹的結構，增加了自己的特性，對數(shù)據(jù)的存放增加了約束。當前第101頁\共有201頁\編于星期五\0點二叉排序樹上的查找查找45

查找成功

查找28查找失敗351545504025102030在二叉排序樹上進行查找，是一個從根結點開始，沿某一個分支逐層向下進行比較判等的過程。它可以是一個遞歸的過程。當前第102頁\共有201頁\編于星期五\0點假設想要在二叉排序樹中查找關鍵字為x的元素，查找過程從根結點開始。如果根指針為NULL，則查找不成功；否則用給定值x與根結點的關鍵字進行比較：如果給定值等于根結點的關鍵字值，則查找成功。如果給定值小于根結點的關鍵字值，則繼續(xù)遞歸查找根結點的左子樹；否則。遞歸查找根結點的右子樹。查找成功時檢測指針停留在樹中某個結點。當前第103頁\共有201頁\編于星期五\0點可用判定樹描述查找過程。內(nèi)結點是樹中原有結點，外結點是失敗結點，代表樹中沒有的數(shù)據(jù)。查找不成功時檢測指針停留在某個失敗結點。3515455025102030查找22查找45當前第104頁\共有201頁\編于星期五\0點二叉排序樹的查找算法voidFind(BSTNode*t,BSTElemTypex,BSTNode*&p,BSTNode*&pr){//在二叉排序樹t中查找關鍵字等于x的結點，成功//時p返回找到結點地址,pr是其雙親結點.不成功//時p為空,pr返回最后走到的結點地址.

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;當前第105頁\共有201頁\編于星期五\0點

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

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

BstNode*pt,*prt,*q;

Find(t,x,pt,prt); //查找結點插入位置

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

q=newBstNode;q->data=x; //創(chuàng)建結點

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

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

else

if(x<prt->data)ptr->lchild=q;elseptr->rchild=q;}}當前第108頁\共有201頁\編于星期五\0點535378537865537865175378658717537865091787537865811787095378651517870981輸入數(shù)據(jù)，建立二叉排序樹的過程輸入數(shù)據(jù){53,78,65,17,87,09,81,15}當前第109頁\共有201頁\編于星期五\0點123111132223323同樣3個數(shù)據(jù){1,2,3

}，輸入順序不同，建立起來的二叉排序樹的形態(tài)也不同。這直接影響到二叉排序樹的查找性能。如果輸入序列選得不好，會建立起一棵單支樹，使得二叉排序樹的高度達到最大。

{2,1,3}{1,2,3}{1,3,2}{2,3,1}{3,1,2}{3,2,1}當前第110頁\共有201頁\編于星期五\0點二叉排序樹的刪除在二叉排序樹中刪除一個結點時，必須將因刪除結點而斷開的二叉鏈表重新鏈接起來，同時確保二叉排序樹的性質不會失去。為保證在刪除后樹的查找性能不至于降低，還需要防止重新鏈接后樹的高度增加。被刪結點的右子樹為空，可以拿它的左子女結點頂替它的位置，再釋放它。被刪結點的左子樹為空，可以拿它的右子女結點頂替它的位置，再釋放它。被刪結點的左、右子樹都不為空，可以在它當前第111頁\共有201頁\編于星期五\0點 的右子樹中尋找中序下的第一個結點(所有比被刪關鍵字大的關鍵字中它的值最小),用它的值填補到被刪結點中，再來處理這個結點的刪除問題。當然，也可以到它的左子樹中尋找中序下的最后一個結點。右子樹空,用左子女頂替5378651787092345刪除4553786517870923當前第112頁\共有201頁\編于星期五\0點左子樹空,用右子女頂替在右子樹上找中序下第一個結點填補8853788817940923刪除7853948817092353788117940945刪除782365538188179409452365當前第113頁\共有201頁\編于星期五\0點

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

種不同排列，可構成不同二叉排序樹有

(棵)用樹的查找效率來評價這些二叉排序樹。用判定樹來描述查找過程，在判定樹中，○表示內(nèi)結點，它包含關鍵字集合中的某一個關鍵字；□表示外結點，代表各關鍵字間隔中的不在關鍵字集合中的關鍵字。它們是查找失敗時到達的結點,物理上實際不存在。當前第114頁\共有201頁\編于星期五\0點在每兩個外部結點間必存在一個內(nèi)部結點。例，已知關鍵字集合

{a1,a2,a3}

=

{do,if,to

}，對應查找概率

p1,p2,p3,在各查找不成功間隔內(nèi)查找概率分別為

q0,q1,q2,q3?？赡艿呐卸淙缦滤?。doiftodoiftoq0q1p1q2p2q3p3q0q1q2q3p1p2p3(a)(b)當前第115頁\共有201頁\編于星期五\0點doiftoq0q1p1q2p2q3p3doiftoq0q1p1q2p2q3p3(d)(c)doiftoq0q1p1q2p2q3p3(e)當前第116頁\共有201頁\編于星期五\0點一棵判定樹的查找成功的平均查找長度ASLsucc定義為該樹所有內(nèi)結點上的權值p[i]與查找該結點時所需的關鍵字比較次數(shù)c[i](=l[i])乘積之和：查找不成功的平均查找長度ASLunsucc為樹中所有外結點上權值q[j]與到達該外結點所需關鍵字比較次數(shù)c'[j](=l'[j]-1)乘積之和：當前第117頁\共有201頁\編于星期五\0點相等查找概率的情形設樹中所有內(nèi)、外結點的查找概率都相等：

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

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

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

結點的平衡因子balancefactor每個結點附加一個數(shù)字，給出該結點左子樹的高度減去右子樹的高度所得的高度差，這個數(shù)字即為結點的平衡因子bf（balancefactor）。平衡二叉樹任一結點平衡因子只能取-1,0,1。如果一個結點的平衡因子的絕對值大于1，則這棵二叉排序樹就失去了平衡，不再是平衡二叉樹。如果一棵二叉排序樹是高度平衡的,且有n個結點，其高度可保持在O(log2n),平均查找長度也可保持在O(log2n)。當前第121頁\共有201頁\編于星期五\0點平衡化旋轉如果在一棵平衡二叉樹中插入一個新結點，造成了不平衡。必須調(diào)整樹的結構，使之平衡化。平衡化旋轉有兩類：

單旋轉

(LL旋轉和RR旋轉)

雙旋轉

(LR旋轉和RL旋轉)每插入一個新結點時，平衡二