在上一篇博客中，我們主要介紹了四種查找的方法，包括順序查找、折半查找、插入查找以及Fibonacci查找。上面這幾種查找方式都是基于線性表的查找方式，今天博客中我們來(lái)介紹一下基于二叉樹(shù)結(jié)構(gòu)的查找，也就是我們今天要聊的二叉排序樹(shù)。今天主要聊的是二叉排序樹(shù)的查找、插入與刪除的內(nèi)容，二叉排序的創(chuàng)建過(guò)程其實(shí)就是不斷查找與插入的過(guò)程，也就是說(shuō)當(dāng)我們?cè)趧?chuàng)建二叉排序樹(shù)時(shí)，我們會(huì)先搜索該節(jié)點(diǎn)在二叉排序樹(shù)中的位置，若沒(méi)有找到該節(jié)點(diǎn)則返回該節(jié)點(diǎn)將要插入的父節(jié)點(diǎn)，然后將該結(jié)點(diǎn)插入。而二叉排序樹(shù)結(jié)點(diǎn)的刪除則有些復(fù)雜，分為幾種情況討論，下方會(huì)給出詳細(xì)的介紹。
在本篇博客的開(kāi)頭，我們先聊聊什么是二叉排序樹(shù)。說(shuō)的直白一些，具有左子樹(shù)上的值<根節(jié)點(diǎn)的值<右子樹(shù)上的值的二叉樹(shù)，我們稱(chēng)之為二叉排序樹(shù)?；诙媾判驑?shù)的特點(diǎn)，有結(jié)合著中序遍歷的特點(diǎn)（中序遍歷是先遍歷左子樹(shù)，再遍歷根節(jié)點(diǎn)，然后遍歷右子樹(shù)），我們不難發(fā)現(xiàn)，二叉排序樹(shù)的中序遍歷的結(jié)果是從小到大有序的。下方我們會(huì)先給出二叉排序樹(shù)的創(chuàng)建，然后給出二叉排序樹(shù)的節(jié)點(diǎn)刪除的代碼。廢話少說(shuō)，進(jìn)入今天博客的主題。
一、二叉排序樹(shù)的創(chuàng)建
上面也簡(jiǎn)單的提了一下，二叉排序樹(shù)的創(chuàng)建無(wú)非就是不斷查找和插入的過(guò)程，當(dāng)我們查找某個(gè)值沒(méi)有找到時(shí)，我們就會(huì)將該值插入到二叉排序樹(shù)中。因?yàn)樵俨檎业倪^(guò)程中可以確定該結(jié)點(diǎn)要插入的合適位置，所以插入就顯得比較簡(jiǎn)單了。下方我們會(huì)先給出二叉排序樹(shù)查找與插入的示意圖，然后再給出相應(yīng)的代碼實(shí)現(xiàn)。最后給出中序遍歷的結(jié)果，觀察我們創(chuàng)建的二叉排序樹(shù)的中序遍歷是否是有序的。
