數(shù)據(jù)結(jié)構(gòu)是計算機(jī)考研的重要內(nèi)容之一，數(shù)據(jù)結(jié)構(gòu)的核心考點較多，復(fù)習(xí)較困難。為了幫助大家更好的了解和復(fù)習(xí)備考，小編為大家整理了2024計算機(jī)考研數(shù)據(jù)結(jié)構(gòu)高頻考點：二叉排序樹的詳細(xì)內(nèi)容，一起來看看吧。
2024計算機(jī)考研數(shù)據(jù)結(jié)構(gòu)高頻考點：二叉排序樹
　　一、定義
　　二叉排序樹，又稱“二叉查找樹”，一棵二叉樹或者是空二叉樹，或者是具有如下性質(zhì)的二叉樹：左子樹結(jié)點值<根節(jié)點值<右子樹根節(jié)點值。
　　左子樹上所有結(jié)點的關(guān)鍵字小于根結(jié)點，右子樹上所有結(jié)點的關(guān)鍵字大于根結(jié)點，左右子樹又各是一顆二叉排序樹，中序遍歷可得到遞增有序數(shù)列。
　　二、查找操作
　　非遞歸實現(xiàn)，遞歸簡單但效率低。
　　1.非遞歸形式：
　　1.若樹非空，目標(biāo)值與根節(jié)點的值進(jìn)行比較：
　　若相等，則查找成功。
　　若小于根節(jié)點，則在左子樹上查找，否則在右子樹上查找。
　　查找成功，則返回結(jié)點指針。
　　如果最后一個結(jié)點也是錯誤的，那么就會執(zhí)行：否則指向右子樹查找，明知右子樹為null，所以返回的就是null。
　　2.遞歸形式實現(xiàn)查找：
　　由于二叉排序樹的遞歸特性，我們也可以用遞歸方式來實現(xiàn)查找。
　　三、插入
　　插入的新結(jié)點一定是某個葉結(jié)點(只有樹為空的時候才會插入)。
　　四、構(gòu)造
　　即使插入元素相同,順序不同時,構(gòu)造的BST也不同。
　　五、刪除
　　葉子結(jié)點:直接刪除，不會破壞二叉排序樹的性質(zhì)。
　　i只有一棵左/右子樹:讓i的子樹成為i父結(jié)點的子樹,替代i位置
　　i有左右兩棵子樹:令i的中序直接后繼/前驅(qū)代替i,再刪去直接后繼/前驅(qū),轉(zhuǎn)換為1,2情況
　　六、查找效率分析
　　查找長度：在查找運算中，需要對比關(guān)鍵字的次數(shù)稱為查找長度，反映了查找操作時間復(fù)雜度。
　　平均查找長度ASL=(每層個數(shù)*對應(yīng)層數(shù))/總個數(shù)
　　較壞情況:類似有序單鏈表O(n)
　　較好情況:平衡二叉樹O(㏒?n)
　　查找過程:與二分查找類似,但二分查找的判定樹唯一。
　　以上內(nèi)容整理于網(wǎng)絡(luò)，僅供參考。
　　以上就是學(xué)姐為大家整理的【2024計算機(jī)考研數(shù)據(jù)結(jié)構(gòu)高頻考點：二叉排序樹】的全部內(nèi)容！想了解更多關(guān)于考研的相關(guān)信息，請關(guān)注高頓考研官網(wǎng)查詢，祝大家考研成功。另外，小編為2024考研的小伙伴們準(zhǔn)備了豐富的學(xué)習(xí)資料，點擊下方藍(lán)色小卡片即可獲取哦~