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