軟件技術(shù)基礎(chǔ)課件

15-13.4

二叉排序樹及其查找1.二叉排序樹（二叉查找樹）的定義

二叉排序樹或者是一棵空樹，或者是滿足下述要求的二叉樹： (遞歸定義)(1)若它的左子樹非空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；(2)若它的右子樹非空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；(3)它的左右子樹本身也是二叉排序樹。4553100619078123372415-2二叉排序樹的構(gòu)造按二叉排序樹的定義規(guī)則依次將待排數(shù)據(jù)插入二叉樹二叉排序樹的形態(tài)與初始序列有關(guān)，最壞情況為一單支樹15-3二叉排序樹的插入template<classT>voidBS_Tree<T>::insert_BS_Tree(Tx){BSnode<T>*p,*q;p=newBSnode<T>;p->d=x;p->lchild=NULL;p->rchild=NULL;q=BT;if(q==NULL)BT=p;else{while((q->lchild!=p)&&(q->rchild!=p)){if(x<q->d){if(q->lchild!=NULL)q=q->lchild;elseq->lchild=p;}else{if(q->rchild!=NULL)q=q->rchild;elseq->rchild=p;}}}return;}15-4二叉排序樹的刪除要求：刪除任意結(jié)點后，仍然保持二叉排序樹的特征。葉結(jié)點可直接刪除只有右子樹18302326121413qp183023261413q15-5二叉排序樹的刪除只有左子樹18

302326121413qp182326121413q15-6二叉排序樹的刪除左右子樹均有，方案一18302327121413qp28251430232713122825Pr直接鏈接到qr上深度增加15-7二叉排序樹的刪除左右子樹均有，方案二

18302327121413qp282514302327122825P的直接中序（q所指）前趨代替P1315-8二叉排序樹的刪除左右子樹均有，方案三

18302327121413qp2825233027122825P的直接中序（q所指）后繼代替P141315-9基本思想類似于對分查找，從根結(jié)點開始走一條到待查結(jié)點的一條查找路徑，直至查找成功或不成功。

將key與根結(jié)點的關(guān)鍵字比較：二叉排序樹的查找45531006190781233724若key=

根結(jié)點的關(guān)鍵字,查找成功，返回該結(jié)點的指針；若key

根結(jié)點的關(guān)鍵字，在左子樹中查找，遞歸調(diào)用；

若key

根結(jié)點的關(guān)鍵字，在右子樹中查找，遞歸調(diào)用；Key=24查找成功！24

45：繼續(xù)在左子樹中查找24

12：繼續(xù)在右子樹中查找24

37：繼續(xù)在左子樹中查找15-10Template<classT>Bsnode<T>*BS_Tree<T>::search_BS_Tree(Tx){Bsnode<T>*p=NULL;

intflag;p=BT;flag=0;while((p!=NULL)&&(flag==0)){if(p->d==x)flag=1;elseif(x<p->d)p=p->lchild;elsep=p->rchild;}if(p==NULL){cout<<“找不到！”<<endl;return(p);}return(p);}算法實現(xiàn)15-11算法分析在一般情況下，此算法的時間復(fù)雜度為ASL=(1*1+2*2+3*4+4*3)/12=2.9

但是ASL與樹的形狀有關(guān)：對于一組數(shù)據(jù)組成的樹：

{40,17,57,09,53,22,89,28,15,45}15-12對于同樣一組數(shù)據(jù)，由于排列順序不同：{15,57,09,53,89,45,40,28,22,17}ASL=(1*1+2*2+3*2+4*1+5*1+6*1+7*1+8*1)/10=4.1由此可見，為了得到較好的平均查找長度，需要對二叉排序樹進(jìn)行進(jìn)一步的處理。這就是二叉排序樹的平衡化的處理15-13二叉排序樹的平衡化處理HL-HRHL-HR||||||---15-14平衡化處理15-15LL型平衡旋轉(zhuǎn)(1)A的左子樹

B的右子樹,改A的平衡因子為0(2)B的右子樹

A,改B的平衡因子為03.3.3-13.3.3-23.3.3-13.3.3-13.3.3-2+1+215-16RR型平衡旋轉(zhuǎn)-1-2(1)A的右子樹

B的左子樹,改A的平衡因子為0(2)B的左子樹

A,改B的平衡因子為0015-17LR型平衡旋轉(zhuǎn)圖3.3.3-33.3.3-33.3.3-4圖3.3.3-4123+1+23.3.3-33.3.3-415-18算法描述：(1)B的右子樹C上升為根節(jié)點;(2)A的左子樹

C的右子樹;B的右子樹C的左子樹;(逆旋)(3)C的右子樹A;C的左子樹B;(順旋)處理平衡因子:(4)如果C的平衡因子=1;則A的平衡因子-1;B的平衡因子0;(5)否則:

如果C的平衡因子=-1;則A的平衡因子0;B的平衡因子1;(6)C的平衡因子0;輸出新樹根節(jié)點C;結(jié)束。123+1+2

15-19RL型平衡旋轉(zhuǎn)-1-23.3.3-4圖3.3.3-4132

3.3.3-4-1→-215-20算法描述：(1)A的右子樹B上升為根節(jié)點;(2)A的右子樹

B的左子樹;C的左子樹B的右子樹;(順旋)(3)B的左子樹A;B的右子樹C;(逆旋)