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