二叉搜索樹(BinarySearchTree)課件

二叉搜索樹(BinarySearchTree)定義

二叉搜索樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：每個結點都有一個作為搜索依據(jù)的關鍵碼(key)，所有結點的關鍵碼互不相同。左子樹（如果非空）上所有結點的關鍵碼都小于根結點的關鍵碼。右子樹（如果非空）上所有結點的關鍵碼都大于根結點的關鍵碼。左子樹和右子樹也是二叉搜索樹。1351545504025102030二叉搜索樹例結點左子樹上所有關鍵碼小于結點關鍵碼；右子樹上所有關鍵碼大于結點關鍵碼；注意：若從根結點到某個葉結點有一條路徑，路徑左邊的結點的關鍵碼不一定小于路徑上的結點的關鍵碼。如箭頭所示路徑。2性質(zhì)：如果對一棵二叉搜索樹進行中序遍歷，可以按從小到大的順序，將各結點關鍵碼排列起來，所以也稱二叉搜索樹為二叉排序樹(BST)。二叉搜索樹的類定義——略二叉搜索樹的類定義用二叉鏈表作為它的存儲表示，許多操作的實現(xiàn)與二叉樹類似。3二叉搜索樹的搜索算法在二叉搜索樹上進行搜索，是一個從根結點開始，沿某一個分支逐層向下進行比較判等的過程。它可以是一個遞歸的過程。假設想要在二叉搜索樹中搜索關鍵碼為x

的元素，搜索過程從根結點開始。如果根指針為NULL，則搜索不成功；否則用給定值

x

與根結點的關鍵碼進行比較：若給定值等于根結點關鍵碼，則搜索成功，返回搜索成功信息并報告搜索到結點地址。4若給定值小于根結點的關鍵碼，則繼續(xù)遞歸搜索根結點的左子樹；否則。遞歸搜索根結點的右子樹。搜索45搜索成功搜索28搜索失敗3515455040251020305BSTNode*Search(Tx,

BSTNode*subtree){//遞歸算法：在以

subtree

為根的二叉搜索樹中//

搜索含x的結點。若找到，則函數(shù)返回該結點//的地址，否則函數(shù)返回NULL值。 if(subtree==NULL)returnNULL;

elseif(x<subtree->data) returnSearch(x,subtree->left); elseif(x>subtree->data) returnSearch(x,

subtree->right); elsereturnsubtree; //搜索成功}6BSTNode*Search(Tx,

BSTNode*subtree){//迭代算法：在當前以subtree

為根的二叉搜索//樹中搜索含x的結點。若找到，則函數(shù)返回該//結點的地址，否則函數(shù)返回NULL值。while(subtree!=NULL){

if(x==subtree->data)returnsubtree; if(x<subtree->data)

subtree=subtree->left; elsesubtree=subtree->right;}returnNULL;}7搜索過程是從根結點開始，沿某條路徑自上而下逐層比較判等的過程。搜索成功，搜索指針將停留在樹上某個結點；搜索不成功，搜索指針將走到樹上某個結點的空子樹。設樹的高度為h，最多比較次數(shù)不超過h。8二叉搜索樹的插入算法為了向二叉搜索樹中插入一個新元素，必須先檢查這個元素是否在樹中已經(jīng)存在。在插入之前，先使用搜索算法在樹中檢查要插入的元素在不在樹中。如果搜索成功，說明樹中已經(jīng)有這個元素，不再插入；如果搜索不成功，說明樹中原來沒有關鍵碼等于給定值的結點，把新元素加到搜索操作停止的地方。9插入新結點

28二叉搜索樹的插入每次結點的插入，都要從根結點出發(fā)搜索插入位置，然后把新結點作為葉結點插入。3515455040251020302810二叉搜索樹的插入算法bool

Insert(Te,BSTNode&subtree){//遞歸算法：在以subtree

為根的二叉搜索樹中插入//值為e的結點。若樹中已有結點e，則不插入

if(subtree==NULL){//新結點作為葉結點插入

subtree=newBSTNode(e);//創(chuàng)建新結點 returntrue;}elseif(e<subtree->data)Insert(e,subtree->left); elseif(e>subtree->data)Insert(e,subtree->right);};11注意參數(shù)表中引用型指針參數(shù)subtree的使用。利用二叉搜索樹的插入算法，可以很方便地建立二叉搜索樹。

12輸入數(shù)據(jù)

{53,78,65,17,87,09,81,15}53537853786553786517537865871753786509178753786581178709537865151787098113voidcreateBST(TEndValue){//從鍵盤上輸入元素序列,建立一棵二叉搜索樹，//參數(shù)

EndValue

表示序列的結束符

root=NULL;//root為樹根，初始化為空樹

cin>>x; //輸入數(shù)據(jù)

while(x.key!=EndValue){ //RefValue是一個輸入結束標志

Insert(x,root);cin>>x; //插入，再輸入數(shù)據(jù)

}}14二叉搜索樹的刪除算法在二叉搜索樹中刪除一個結點時，必須將因刪除結點而斷開的二叉鏈表重新鏈接起來，同時確保二叉搜索樹的性質(zhì)不會失去。為保證在刪除后樹的搜索性能不至于降低，還需要防止重新鏈接后樹的高度增加。刪除葉結點，只需將其雙親結點指向它的指針清零，再釋放它即可。被刪結點右子樹為空，可以拿它的左子女結點頂替它的位置，再釋放它。15被刪結點左子樹為空，可以拿它的右子女結點頂替它的位置，再釋放它。被刪結點左、右子樹都不為空，可以在它的右子樹中尋找中序下的第一個結點(關鍵碼最小),用它的值填補到被刪結點中，再來處理這個結點的刪除問題。5378651787092345刪除45右子樹空,用左子女頂替53786517870923168853788817940923刪除78左子樹空,用右子女頂替53948817092353788117940945刪除78在右子樹上找中序下第一個結點填補236553818817940945236517二叉搜索樹的刪除算法bool

Remove(x,BSTNode&subtree){//遞歸算法：在以subtree

為根的二叉搜索樹中//

刪除含x的結點

if(subtree==NULL)return

false;

if(x<subtree->data)//在左子樹中執(zhí)行刪除 returnRemove(x,subtree->left);

elseif(x>subtree->data)//在右子樹中執(zhí)行刪除

return

Remove(x,subtree->right);

else{//

找到了被刪結點18

//1.左、右子女均不空 if(subtree->left!=NULL&&

subtree->right!=NULL){ //subtree指示關鍵碼為x的結點，它有兩個子女 temp=subtree->right;

//到右子樹搜尋中序下第一個結點

while(temp->left!=NULL)temp=temp->left;

subtree->data=temp->data;

//用該結點數(shù)據(jù)代替根結點數(shù)據(jù) Remove(temp->data,subtree->right); }19 else{//subtree指示的結點最多有一個子女 temp=subtree;

if(subtree->left==NULL)subtree=

subtree->right; elsesubtree=subtree->left;deletetemp; returntrue; } }}注意在刪除算法參數(shù)表引用型指針參數(shù)的使用。20

二叉搜索樹性能分析對于有n個關鍵碼的集合，其關鍵碼有n!種不同排列，可構成不同二叉搜索樹有

(棵)

{2,1,3}{1,2,3}{1,3,2}{2,3,1}{3,1,2}{3,2,1}

12311113222332321同樣3個數(shù)據(jù){1,2,3}，輸入順序不同，建立起來的二叉搜索樹的形態(tài)也不同。這直接影響到二叉搜索樹的搜索性能。如果輸入序列選得不好，會建立起一棵單支樹，使得二叉搜索樹的高度達到最大。用樹的搜索效率來評價這些二叉搜索樹。為此，在二叉搜索樹中加入外結點，形成判定樹。外結點表示失敗結點，內(nèi)結點表示搜索樹中已有的數(shù)據(jù)。這樣的判定樹即為擴充的二叉搜索樹。22舉例說明。已知關鍵碼集合

{a1,a2,a3}=

{do,if,to}，對應搜索概率p1,p2,p3,在各搜索不成功間隔內(nèi)搜索概率分別為q0,q1,q2,q3。可能的二叉搜索樹如下所示。doiftodoiftoq0q1p1q2p2q3p3q0q1q2q3p1p2p3(a)(b)23判定樹doiftoq0q1p1q2p2q3p3doiftoq0q1p1q2p2q3p3(d)(c)doiftoq0q1p1q2p2q3p3(e)24在判定樹中

○表示內(nèi)部結點，包含了關鍵碼集合中的某一個關鍵碼；□表示外部結點，代表各關鍵碼間隔中的不在關鍵碼集合中的關鍵碼。在每兩個外部結點間必存在一個內(nèi)部結點。一棵判定樹上