數(shù)據(jù)結(jié)構(gòu)-查找ds_chap(編輯修改稿)
2025-07-01 21:08 本頁面
【文章內(nèi)容簡介】 結(jié)點的左孩子或右孩子結(jié)點。 ?插入前必須要查找，以確定要插入的位置，因此必須修改二叉排序樹的查找算法 ?查找不成功時必須 返回插入的位置 南昌航空大學(xué)計算機學(xué)院 /軟件學(xué)院 第 8章 查找 動態(tài)查找表 —— 二叉排序樹 ? 二叉排序樹查找的遞歸算法 （ 查找不成功時返回插入的位置 ） ? Status SearchBST(BiTree T， KeyType key， BiTree f， BiTree amp。p){ //在根指針 T所指二叉排序樹中遞歸地查找其關(guān)鍵字等于 key的數(shù)據(jù)元素， //若查找成功，則指針 p指向該數(shù)據(jù)元素結(jié)點，并返回 TRUE， //否則指針 p指向查找路徑上訪問的最后一個結(jié)點并返回 FALSE， //指針 f指向 T的雙親，其初始調(diào)用值為 NULL if (!T) { p=f； return FALSE； } //查找不成功 else if EQ(key, T) { p=T； return TRUE； } //查找成功 else if LT(key,T) SearchBST(Tlchild,key,T,p)； //在左子樹中繼續(xù)查找 else SearchBST(Trchild,key,T,p)； //在右子樹中繼續(xù)查找 }//SearchBST 南昌航空大學(xué)計算機學(xué)院 /軟件學(xué)院 第 8章 查找 動態(tài)查找表 —— 二叉排序樹 ?二叉排序樹的插入算法 ? Status InsertBST(BiTree amp。T， ElemType e){ //當二叉排序樹 T中不存在關(guān)鍵字等于 ,插入 e并返回 TRUE，否則返回 FALSE if (!SearchBST(T， ， NULL， p){ //查找不成功 s=(BiTree)malloc(sizeof(BiTNode))； sdata=e； slchild =srchild=NULL； if (!p) T = s； //被插結(jié)點 *s為新的根結(jié)點，原樹為空 else if LT(， p) plchild=s； //被插結(jié)點 *s為左孩子 else prchild=s //被插結(jié)點 *s為右孩子 return TRUE； } else return FALSE。 //樹中已有關(guān)鍵字相同的結(jié)點，不再插入 }// InsertBST 南昌航空大學(xué)計算機學(xué)院 /軟件學(xué)院 第 8章 查找 動態(tài)查找表 —— 二叉排序樹 ?二叉排序樹的建立 ? 依次輸入數(shù)據(jù) { 53,78,65,17,87,09,81,15}， 建立二叉排序樹 53 53 78 53 78 65 53 78 65 17 53 78 65 87 17 53 78 65 09 17 87 53 78 65 81 17 87 09 53 78 65 15 17 87 09 81 南昌航空大學(xué)計算機學(xué)院 /軟件學(xué)院 第 8章 查找 動態(tài)查找表 —— 二叉排序樹 ?二叉排序樹的建立 ?重復(fù)插入 ?中序遍歷二叉排序樹，得到升序序列 ?建立的過程即為對無序序列進行排序的過程 ?二叉排序樹既擁有類似于折半查找的特性，又采用了鏈表作存儲結(jié)構(gòu)，因此是動態(tài)查找表的一種適宜表示 ?同樣 n3 個數(shù)據(jù)，如果輸入順序不同，建立起來的二叉排序樹的形態(tài)也不同，這直接影響到二叉排序樹的查找性能。 南昌航空大學(xué)計算機學(xué)院 /軟件學(xué)院 第 8章 查找 動態(tài)查找表 —— 二叉排序樹 ?二叉排序樹的建立算法 ?void CreateBST(BSTree bst) /*從鍵盤輸入元素的值，創(chuàng)建相應(yīng)的二叉排序樹 */ { KeyType key。 bst=NULL。 scanf(%d, amp。key)。 while (key!=ENDKEY) /*ENDKEY為自定義常數(shù) */ { InsertBST(bst, key)。 scanf(%d, amp。key)。 } } 南昌航空大學(xué)計算機學(xué)院 /軟件學(xué)院 第 8章 查找 動態(tài)查找表 —— 二叉排序樹 ?二叉排序樹的刪除 ?在二叉搜索樹中刪除一個結(jié)點時，必須將因刪除結(jié)點而斷開的二叉鏈表重新鏈接起來，同時確保二叉搜索樹的性質(zhì)不會失去。 ?為保證在刪除后樹的搜索性能不至于降低，還需要防止重新鏈接后樹的高度增加。 ?分四種情況進行討論 ?刪除 葉結(jié)點 ?被刪結(jié)點缺右子樹 ?被刪結(jié)點缺左子樹 ?被刪結(jié)點左、右子樹都存在 單分支結(jié)點 雙分支結(jié)點 南昌航空大學(xué)計算機學(xué)院 /軟件學(xué)院 第 8章 查找 動態(tài)查找表 —— 二叉排序樹 ?二叉排序樹的刪除 ?刪除葉結(jié)點，只需將其雙親結(jié)點指向它的指針清零，再釋放它即可。 53 78 65 17 87 09 23 45 刪除 65 雙親結(jié)點指針清零 53 78 17 87 09 23 45 南昌航空大學(xué)計算機學(xué)院 /軟件學(xué)院 第 8章 查找 動態(tài)查找表 —— 二叉排序樹 ?二叉排序樹的刪除 ?被刪結(jié)點缺右子樹，可以拿它的左子女結(jié)點頂替它的位置，再釋放它。 53 78 65 17 87 09 23 45 刪除 45 缺右子樹 , 用左子女頂替 53 78 65 17 87 09 23 南昌航空大學(xué)計
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1