1 二叉查找樹(shù)是什么,？

二叉查找樹(shù)是一種數(shù)據(jù)結(jié)構(gòu),，又叫作二叉搜索樹(shù)或二叉排序樹(shù),采用了圖的樹(shù)形結(jié)構(gòu)，數(shù)據(jù)存儲(chǔ)于二叉查找樹(shù)的各個(gè)結(jié)點(diǎn)中,，每個(gè)節(jié)點(diǎn)中最多有兩個(gè)子結(jié)點(diǎn)。

2 二叉查找樹(shù) 的特點(diǎn)

• 每個(gè)結(jié)點(diǎn)的值均大于其左子樹(shù)上任意一個(gè)結(jié)點(diǎn)的值,。比如上圖中的結(jié)點(diǎn)9大于其左子樹(shù)上的3和8

• 每個(gè)結(jié)點(diǎn)的值均小于其右子樹(shù)上任意一個(gè)結(jié)點(diǎn)的值,。比如上圖中的結(jié)點(diǎn)15小于其右子樹(shù)上的23、17和28

所以在二叉查找樹(shù)的中的數(shù)據(jù),，最左邊小數(shù)據(jù),，右邊是大數(shù)據(jù),，在查找數(shù)據(jù)時(shí)，二叉查找樹(shù)的最小結(jié)點(diǎn)要從頂端開(kāi)始,，往其左下的末端尋找,；然后最大結(jié)點(diǎn)要從頂端開(kāi)始，往其右下的末端尋找,。

第二步

第三步

最后得到

比如添加數(shù)據(jù)4,，添加分析邏輯與上述過(guò)程也是一致的：

4 二叉查找樹(shù)中刪除數(shù)據(jù)

如果需要?jiǎng)h除的結(jié)點(diǎn)沒(méi)有子結(jié)點(diǎn),，直接刪掉該結(jié)點(diǎn)即可,，如刪除這里的結(jié)點(diǎn) 28：

如果需要?jiǎng)h除的結(jié)點(diǎn)只有一個(gè)子結(jié)點(diǎn),，那么先刪掉目標(biāo)結(jié)點(diǎn),，然后把子結(jié)點(diǎn)移到被刪除結(jié)點(diǎn)的位置上即可,，如刪除這里的結(jié)點(diǎn)8：

完畢