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