數(shù)據(jù)結(jié)構(gòu)第九章ppt課件(參考版)
2025-05-03 18:12本頁面
【正文】 .將雙親結(jié)點中剛剛大于 (或小于 ) 該被刪關(guān)鍵碼的關(guān)鍵碼 Ki (1 ? i ? n) 下移；.將右兄弟 (或左兄弟 ) 結(jié)點中的最小 (或最大 )關(guān)鍵碼上移到雙親結(jié)點的 Ki 位置；.將右兄弟 (或左兄弟 ) 結(jié)點中的最左 (或最右 ) 子樹指針平移到被刪關(guān)鍵碼所在結(jié)點中最后 (或最前 ) 子樹指針位置；.在右兄弟 (或左兄弟 ) 結(jié)點中 ,將被移走的關(guān)鍵碼和指針位置用剩余的關(guān)鍵碼和指針填補 ,調(diào)整 .再將結(jié)點中的關(guān)鍵碼個數(shù)減 1.4647484)被刪關(guān)鍵碼所在葉結(jié)點刪除前關(guān)鍵碼個數(shù) n = ?m/2? 1,若這時與該結(jié)點相鄰的右兄弟 (或左兄弟 ) 結(jié)點的關(guān)鍵碼個數(shù) n = ?m/2? 1,則必須按以下步驟合并這兩個結(jié)點 ..將 雙親結(jié)點 p 中相應(yīng)關(guān)鍵碼下移到選定保留的結(jié)點中 ..若要合并 p 中的子樹指針 Pi 與 Pi+1 所指的結(jié)點 ,且保留 Pi 所指結(jié)點 ,則把 p 中的關(guān)鍵碼 Ki+1下移到 Pi 所指的結(jié)點中 .. 把 p 中子樹指針 Pi+1 所指結(jié)點中的全部指針和關(guān)鍵碼都照搬到 Pi 所指結(jié)點的后面 .刪去 Pi+1 所指的結(jié)點 ..在結(jié)點 p中用后面剩余的關(guān)鍵碼和指針填補關(guān)鍵碼 Ki+1 和指針 Pi+1..修改結(jié)點 p和選定保留結(jié)點的關(guān)鍵碼個數(shù) ..在合并結(jié)點的過程中 ,雙親結(jié)點中的關(guān)鍵碼個數(shù)減少了 .49.若雙親結(jié)點是根結(jié)點且結(jié)點關(guān)鍵碼個數(shù)減到 0，則該雙親結(jié)點應(yīng)從樹上刪去 ,合并后保留的結(jié)點成為新的根結(jié)點 。.回憶 :動態(tài)查找表的特點 .. 二叉排序樹 (二叉搜索樹 ) 二叉排序樹 或者是 一棵空樹 ,或者是具有下列性質(zhì)的二叉樹 : ? 每個結(jié)點都有一個作為搜索依據(jù)的關(guān)鍵碼 (key)，所有結(jié)點的關(guān)鍵碼互不相同 . ? 左子樹 (如果存在 )上所有結(jié)點的關(guān)鍵碼都 小于 根結(jié)點的關(guān)鍵碼 . ? 右子樹 (如果存在 )上所有結(jié)點的關(guān)鍵碼都 大于 根結(jié)點的關(guān)鍵碼 . ? 左子樹和右子樹也是二叉排序樹 .的定義15.幾個二叉排序樹的例子.由此 ,可得到二叉排序樹的作用 :查找. 二叉排序樹上的 查找在二叉搜索樹上進行搜索 ,是一個從根結(jié)點開始 ,沿某一個分支逐層向下進行比較判等的過程 .. 二叉排序樹上的 查找 可以是一個 遞歸 過程 ,也可以是一個 迭代 過程 .16.二叉排序樹是的搜索示例.88插入到哪個地方 ?.每次結(jié)點的插入 ,都要從根結(jié)點出發(fā)搜索插入位置 ,然后把新結(jié)點作為 葉結(jié)點插入 . 17. 二叉排序樹上的 插入為了向二叉搜索樹中插入一個新元素 ,必須先檢查這個元素是否在樹中已經(jīng)存在 ..在插入之前 ,先使用 搜索算法 在樹中檢查要插入元素有還是沒有 . 搜索成功 : 樹中已有這個元素 ,不再插入 . 搜索不成功 : 樹中原來沒有關(guān)鍵碼等于給定值的結(jié)點 ,把新元素 加到搜索操作停止 的地方.例 :輸入數(shù)據(jù)序列 {53, 78, 65, 17, 87, 09, 81, 45, 23},寫出建立二叉排序樹的過程 .18. 為了引入二叉排序樹上的刪除 ,先簡單討論下面這個問題 ..同樣 3 個數(shù)據(jù) { 1, 2, 3 },輸入順序不同 ,建立起來的二叉搜索樹的形態(tài)也不同 .這直接影響到二叉搜索樹的搜索性能 . 如果輸入序列選得不好 ,會建立起一棵單支樹,使得二叉搜索樹的高度達到最大 ,這樣必然會降低搜索性能 .12311 1132 223323直觀上 的結(jié)論 ,二叉排序樹的高度不能太高 .19. 二叉排序樹上的 刪除在二叉搜索樹中刪除一個結(jié)點時 ,必須將因刪除結(jié)點而斷開的二叉鏈表重新鏈接起來 ,同時確保二叉搜索樹的性質(zhì)不會失去 ..為保證在執(zhí)行刪除后 ,樹的搜索性能不至于降低 ,還需要防止重新鏈接后樹的 高度增加 .1)刪除葉結(jié)點 ,只需將其雙親結(jié)點指向它的指針清零 ,再釋放它即可 .2)被刪結(jié)點缺右子樹 ,可以拿它的左子女結(jié)點頂替它的位置 ,再釋放它 .3)被刪結(jié)點缺左子樹 ,可以拿它的右子女結(jié)點頂替它的位
教學課件相關(guān)推薦
鄂ICP備17016276號-1