軟件技術(shù)基礎(chǔ)3-3.ppt

《軟件技術(shù)基礎(chǔ)3-3.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、3.4二叉排序樹及其查找一、定義所謂二叉排序樹是指滿足下列條件的二叉樹：（1）左子樹上的所有結(jié)點(diǎn)值均小于根結(jié)點(diǎn)值。（2）右子樹上的所有結(jié)點(diǎn)值均不小于根結(jié)點(diǎn)值。（3）左、右子樹也滿足上述兩個(gè)條件二、二叉排序樹的特性二叉排序樹有一個(gè)重要特性：中序遍歷二叉排序樹可以得到有序序列。因此，由無序序列構(gòu)造二叉排序樹實(shí)際上就將一個(gè)無序序列變成了有序序列。另外，由于在二叉排序樹中插入的新結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，因此，在對(duì)二叉排序樹進(jìn)行插入運(yùn)算時(shí)，不需移動(dòng)其他結(jié)點(diǎn)，而只需改動(dòng)插入位置上的葉子結(jié)點(diǎn)指針即可。三、二叉排序樹的構(gòu)造依次讀入給定序列中的每一個(gè)

2、元素，然后進(jìn)行如下處理：（1）若當(dāng)前的二叉排序樹為空，則讀入的元素為根結(jié)點(diǎn)。（2）若讀入的元素值小于根結(jié)點(diǎn)值，則將元素插入到左子樹中。（3）若讀入的元素值不小于根結(jié)點(diǎn)值，則將元素插入到右子樹中。無論是插入到左子樹還是右子樹，都是同樣按照上述方法處理。四、二叉排序樹的刪除為了刪除一個(gè)元素，首先要找到被刪除元素所在的結(jié)點(diǎn)p和它的父結(jié)點(diǎn)q，然后分以下3種情況進(jìn)行處理：（1）p為葉子結(jié)點(diǎn)：直接刪除，修改父結(jié)點(diǎn)指針。（2）p為單支樹：將P的子樹鏈到q上。（3）p的左右子樹均不空：將p的左子樹的右鏈最右邊的結(jié)點(diǎn)s的值填入p中，將s的左鏈鏈

3、到s的父結(jié)點(diǎn)的右指針。五、二叉排序樹查找算法算法描述:輸入一個(gè)值，在該樹中查找，若找到輸出該結(jié)點(diǎn)值；否則，顯示查找失敗。與根比，相等，查找成功，比根小，在左子樹查比根大，在右子樹查查左右子樹時(shí)按同樣的方法查structtree*search_btree(structtree*root,charkey){if(!root){cout<info!=key)/*查找key的循環(huán)*/{if(keyinfo)root=root->left;/*沿左路查找

4、*/elseroot=root->right;if(root==0){cout<info!=key)*/if(root!=0)cout<info);returnroot;}舉例對(duì)數(shù)列{10，18，3，4，9，13，25}，生成二叉排序樹。10（1）1018（2）10318（3）103184（4）1034189（5）（7）10394181325103491813（6）多層索引樹及其查找索引是提高數(shù)據(jù)存

5、取效率的基本方法。但如果索引本身很大，那么對(duì)索引的查找代價(jià)也就很大。因此，在實(shí)際應(yīng)用中，一般采用多層索引樹。多層索引的應(yīng)用很廣泛，二叉排序樹實(shí)際上就是一種多層索引樹。在二叉排序樹中，每個(gè)結(jié)點(diǎn)有一個(gè)關(guān)鍵字（即結(jié)點(diǎn)值），并且還有兩個(gè)指針。在對(duì)二叉排序樹進(jìn)行查找的過程中，當(dāng)查找的關(guān)鍵字小于結(jié)點(diǎn)中的關(guān)鍵字時(shí)，就沿左指針往下找；當(dāng)查找的關(guān)鍵字大于結(jié)點(diǎn)中的關(guān)鍵字時(shí)，就沿右指針往下找；當(dāng)兩者相等時(shí)，說明查找成功。由此可以看出，二叉排序樹中結(jié)點(diǎn)的關(guān)鍵字起著指示查找路徑的作用。結(jié)點(diǎn)結(jié)構(gòu)一般來說，多層索引村中的每個(gè)結(jié)點(diǎn)包含2m個(gè)關(guān)鍵字域和2m＋1

6、個(gè)指針域。多層索引樹中的結(jié)點(diǎn)結(jié)構(gòu)如圖所示。LINK1KEY1LINK2KEY2…LINK2mKEY2mLINK2m+1B-樹B-樹是一種動(dòng)態(tài)調(diào)節(jié)的平衡多路查找樹。B-樹的定義如下：一棵2m＋l階的樹，或?yàn)榭?，或?yàn)闈M足下列條件的度為2m＋l的樹。（1）樹中每個(gè)結(jié)點(diǎn)最多有2m＋l棵子樹，且除根結(jié)點(diǎn)外的所有非葉子結(jié)點(diǎn)至少有m+1棵子樹，而根結(jié)點(diǎn)至少有兩棵子樹（除非根結(jié)點(diǎn)又是葉子結(jié)點(diǎn)）。（2）所有葉子結(jié)點(diǎn)均在最后一層上。（3）除葉子結(jié)點(diǎn)外的每個(gè)結(jié)點(diǎn)結(jié)構(gòu)如前圖所示。其中：KEYi（1≤i≤2m）為關(guān)鍵字域，用于存放關(guān)鍵字及有關(guān)數(shù)據(jù)信息；

7、LINKi（1≤i≤2m＋l）為指針域，指向各子樹的根結(jié)點(diǎn)。對(duì)于度為n＋1（1≤n≤2m）的結(jié)點(diǎn)，前n個(gè)關(guān)鍵字域內(nèi)容按關(guān)鍵字有序，即KEYi＜KEYi＋1（1≤i

8、樹的存儲(chǔ)空間。其中：N（i）表示結(jié)點(diǎn)i中的關(guān)鍵字個(gè)數(shù)n。如果結(jié)點(diǎn)i為非葉子結(jié)點(diǎn)，則此結(jié)點(diǎn)有N（i）+1棵子樹，PRT（i）指向結(jié)點(diǎn)i的父結(jié)點(diǎn)。KEY（i，j）是結(jié)點(diǎn)i的第j（1≤j≤2m）個(gè)關(guān)鍵字域。LINK（i，j）是結(jié)點(diǎn)i的第j（1≤j≤2m+1）個(gè)指針域。B-樹的存儲(chǔ)結(jié)