大學(xué)《數(shù)據(jù)結(jié)構(gòu)》第八章：查找-第三節(jié)-樹(shù)表的查找（一）

第三節(jié)樹(shù)表的查找（一）一、二叉排序樹(shù)1、二叉排序樹(shù)的概念（1）二叉排序樹(shù)的定義二叉排序樹(shù)(BinarySortTree，BST)又稱(chēng)二叉查找，是一種特殊的二叉樹(shù)，二叉排序樹(shù)或者是空樹(shù)，或者是滿(mǎn)足如下性質(zhì)的二叉樹(shù)：①若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；②若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；③左、右子樹(shù)本身又各是一棵二叉排序樹(shù)。【例】下圖的就是一棵二叉排序樹(shù)中序遍歷序列：15，16，18，19，20，22，30，35，42（2）二叉排序樹(shù)的重要性質(zhì)中根遍歷一棵二叉排序樹(shù)所得的結(jié)點(diǎn)訪(fǎng)問(wèn)序列是按鍵值的遞增序列。（3）二叉排序樹(shù)的數(shù)據(jù)類(lèi)型定義typedefstructnode{KeyTypekey；//關(guān)鍵字DataTypeother；//其他數(shù)據(jù)域structnode*lchild，*rchild；//左右子樹(shù)指針}BsTNode；//結(jié)點(diǎn)類(lèi)型typedefBsTNode*BsTree；//二叉排序樹(shù)類(lèi)型2、二叉排序樹(shù)的插入（1）算法思想在二叉排序樹(shù)中插入新結(jié)點(diǎn)，要保證插入后仍滿(mǎn)足BST性質(zhì)。其插入過(guò)程是：①若二叉排序樹(shù)T為空，則為待插入的關(guān)鍵字key申請(qǐng)一個(gè)新結(jié)點(diǎn)，并令其為根；②若二叉排序樹(shù)T不為空，則將key和根的關(guān)鍵字比較：若二者相等，則說(shuō)明樹(shù)中已有此關(guān)鍵字key，無(wú)須插入。若key<T→key，則將key插入根的左子樹(shù)中。若key>T→key，則將它插入根的右子樹(shù)中。子樹(shù)中的插入過(guò)程與上述的樹(shù)中插入過(guò)程相同。如此進(jìn)行下去，直到將key作為一個(gè)新的葉結(jié)點(diǎn)的關(guān)鍵字插入到二叉排序樹(shù)中，或者直到發(fā)現(xiàn)樹(shù)中已有此關(guān)鍵字為止。（2）實(shí)例分析【例】寫(xiě)出把無(wú)序序列（20，10，30，15，25，5，35，12，27）建成二叉排序樹(shù)的過(guò)程?！窘獯稹坎捎弥瘘c(diǎn)插入結(jié)點(diǎn)的方法即可建立相應(yīng)的二叉排序樹(shù)。建成二叉排序樹(shù)的過(guò)程如圖所示（3）算法描述BSTreeInsertBST(BSTreeT，BSTNode*S){BSTNode*f，*p=T；while(p)//找插入位置｛f=p；//f記錄p的雙親，為將來(lái)插入結(jié)點(diǎn)if(S->key<p->key)p=p->lchild；elsep=p->rchild；}if(T==NULL)T=S；//T為空樹(shù)，新結(jié)點(diǎn)作為根結(jié)點(diǎn)elseif(S->key<f->key)f->lchild=S；//作為雙親的左孩子插入elsef->rchild=S；//作為雙親的右孩子插入returnT；｝3、二叉排序樹(shù)的生成（1）算法思想從空的二叉樹(shù)開(kāi)始，每輸入一個(gè)結(jié)點(diǎn)數(shù)據(jù)，生成一個(gè)新結(jié)點(diǎn)，就調(diào)用一次插入算法將它插入到當(dāng)前生成的二又排序樹(shù)中（2）算法描述BSTreeCreateBST(void){//從空樹(shù)開(kāi)始，建立一棵二叉排序樹(shù)BSTreeT=NULL；//初始化T為空樹(shù)KeyTypekey；BSTNode*S；scanf("％d"，&key)；//輸入第一個(gè)關(guān)鍵字while(key)//假設(shè)key=0是輸入結(jié)束{S=(BSTNode*)malloc(Sizeof(BSTNode))；S->key=key；//生成新結(jié)點(diǎn)S->1child=S->rchiId=NULL：T=InsertBST(T，S)；//將新結(jié)點(diǎn)*S插入二叉排序樹(shù)Tscanf("％d"，&key)；//輸入下一個(gè)關(guān)鍵字｝returnT；//返回建立的二叉排序樹(shù)｝【例】已知某二叉排序樹(shù)10個(gè)結(jié)點(diǎn)的值依次為1~10，其結(jié)構(gòu)如圖所示，試標(biāo)出該二叉樹(shù)各結(jié)點(diǎn)所對(duì)應(yīng)的具體值?！痉治觥扛鶕?jù)二叉排序樹(shù)的的特點(diǎn)：對(duì)二叉排序樹(shù)進(jìn)行中序遍歷，得到的是從小到大的序列。給題中給出的二叉樹(shù)各結(jié)點(diǎn)填入字符，如圖所示；再對(duì)該二叉樹(shù)進(jìn)行中序遍歷得到序列：（D，J，I，G，B，A，E，H，C，F(xiàn)）；根據(jù)二叉排序樹(shù)的的特點(diǎn)和題目要求，這個(gè)序列對(duì)應(yīng)序列（1，2，3，4，5，6，7，8，9，10）；將二叉樹(shù)中的字符改為對(duì)應(yīng)得數(shù)字即可。【解答】二叉樹(shù)各結(jié)點(diǎn)所對(duì)應(yīng)的具體值如圖所示。4、二叉排序樹(shù)上的查找（1）算法思想若二叉排序樹(shù)為空，則表明查找失敗，應(yīng)返回空指針。否則，若給定值key等于根結(jié)點(diǎn)的關(guān)鍵字，則表明查找成功，返回當(dāng)前根結(jié)點(diǎn)指針；若給定值key小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在根結(jié)點(diǎn)的左子樹(shù)中查找，若給定值key大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在根結(jié)點(diǎn)的右子樹(shù)中查找。顯然，這是一個(gè)遞歸的查找過(guò)程，（2）算法描述BSTNode*SearchBST(BSTreeT，KeyTypex){//在二叉排序樹(shù)上查找關(guān)鍵字值為x的結(jié)點(diǎn)if(T==NULL||T->key==x)returnT；if(x<T->key)returnSearchBST(T->lchild，x)；elsereturnSearchBST(T->rchild，x)；}（3）算法分析二叉排序樹(shù)上的查找長(zhǎng)度與二叉排序樹(shù)的形態(tài)有關(guān)，若二叉排序樹(shù)是一棵理想的平衡樹(shù)（是指樹(shù)中任一結(jié)點(diǎn)的左右子樹(shù)的高度差不能大于1），則進(jìn)行查找的時(shí)間復(fù)雜度為O(log2n)；若退化為一棵單支樹(shù)，則其查找的時(shí)間復(fù)雜度為O(n)。對(duì)于一般情況，其時(shí)間復(fù)雜度應(yīng)為O(log2n)?！纠拷o定表（20，15，18，12，25，27，30，22，17，20，28），按數(shù)據(jù)元素在表中的次序構(gòu)造一棵二叉排序樹(shù)，求出其平均查找長(zhǎng)度?！窘獯稹堪凑諛?gòu)造二叉排序樹(shù)方法，構(gòu)造結(jié)果如圖所示。平均查找長(zhǎng)度為：（1+2×2+4×3+3×4+5×1）/11=34/115、二叉排序樹(shù)上的刪除從BST樹(shù)上刪除一個(gè)結(jié)點(diǎn)，仍然要保證刪除后滿(mǎn)足BST的性質(zhì)。設(shè)被刪除結(jié)點(diǎn)為p，其父結(jié)點(diǎn)為f，如圖（a）所示的BST樹(shù)。具體刪除情況分析如下：（1）若p是葉子結(jié)點(diǎn)：直接刪除p，如圖（b）所示。（2）若p只有一棵子樹(shù)（左子樹(shù)或右子樹(shù)），直接用p的左子樹(shù)（或右子樹(shù)）取代p的位置而成為f的一棵子樹(shù)。即原來(lái)p是f的左子樹(shù)，則p的子樹(shù)成為f的左子樹(shù)；原來(lái)p是f的右子樹(shù)，則p的子樹(shù)成為f的右子樹(shù)，如圖（c）所示。（3）若p既有左子樹(shù)又有右子樹(shù)，處理方法有以下兩種，可以任選其中一種。①用p的直接前驅(qū)結(jié)點(diǎn)（中序遍歷）代替p，即從p的左子樹(shù)中選擇值最大的結(jié)點(diǎn)s放在p的位置（用結(jié)點(diǎn)s的內(nèi)容替換結(jié)點(diǎn)p內(nèi)容），然后刪除結(jié)點(diǎn)s。s是p的左子樹(shù)中最右邊的結(jié)點(diǎn)且沒(méi)有右子樹(shù)，如圖（d）所示。②用p的直接后繼結(jié)點(diǎn)（中序遍歷）代替p，即從p的右子樹(shù)中選擇值最小的結(jié)點(diǎn)s放在p的位置（用結(jié)點(diǎn)s的內(nèi)容替換結(jié)點(diǎn)p的內(nèi)容），然后刪除結(jié)點(diǎn)s。s是p的右子樹(shù)中的最左邊的結(jié)點(diǎn)且沒(méi)有左子樹(shù)。例如，對(duì)圖（a）所示的二叉