大家是否感覺到，樹在數(shù)據(jù)結(jié)構(gòu)中大行其道，什么領(lǐng)域都要沾一沾，碰一碰。

就拿我們前幾天學(xué)過的排序就用到了堆和今天講的”二叉排序樹“，所以偏激的說，掌握的樹你就是牛人了。

今天就聊聊這個(gè)”五大經(jīng)典查找“中的最后一個(gè)”二叉排序樹“。

1. 概念:

<1> 其實(shí)很簡(jiǎn)單，若根節(jié)點(diǎn)有左子樹，則左子樹的所有節(jié)點(diǎn)都比根節(jié)點(diǎn)小。

若根節(jié)點(diǎn)有右子樹，則右子樹的所有節(jié)點(diǎn)都比根節(jié)點(diǎn)大。

<2> 如圖就是一個(gè)”二叉排序樹“，然后對(duì)照概念一比較比較。

2.實(shí)際操作：

我們都知道，對(duì)一個(gè)東西進(jìn)行操作，無非就是增刪查改，接下來我們就聊聊其中的基本操作。

<1> 插入：相信大家對(duì)“排序樹”的概念都清楚了吧，那么插入的原理就很簡(jiǎn)單了。

比如說我們插入一個(gè)20到這棵樹中。

首先：20跟50比，發(fā)現(xiàn)20是老小，不得已，得要?dú)w結(jié)到50的左子樹中去比較。

然后：20跟30比，發(fā)現(xiàn)20還是老小。

再然后：20跟10比，發(fā)現(xiàn)自己是老大，隨即插入到10的右子樹中。

最后： 效果呈現(xiàn)圖如下：

<2>查找：相信懂得了插入，查找就跟容易理解了。

就拿上面一幅圖來說，比如我想找到節(jié)點(diǎn)10.

首先：10跟50比，發(fā)現(xiàn)10是老小，則在50的左子樹中找。

然后：10跟30比，發(fā)現(xiàn)還是老小，則在30的左子樹中找。

再然后: 10跟10比，發(fā)現(xiàn)一樣，然后就返回找到的信號(hào)。

<3>刪除：刪除節(jié)點(diǎn)在樹中還是比較麻煩的，主要有三種情況。

《1》 刪除的是“葉節(jié)點(diǎn)20“，這種情況還是比較簡(jiǎn)單的，刪除20不會(huì)破壞樹的結(jié)構(gòu)。如圖：

《2》刪除”單孩子節(jié)點(diǎn)90“，這個(gè)情況相比第一種要麻煩一點(diǎn)點(diǎn)，需要把他的孩子頂上去。

《3》刪除“左右孩子都有的節(jié)點(diǎn)50”，這個(gè)讓我在代碼編寫上糾結(jié)了好長(zhǎng)時(shí)間，問題很直白，

我把50刪掉了，誰頂上去了問題，是左孩子呢？還是右孩子呢？還是另有蹊蹺？這里我就

坦白吧，不知道大家可否知道“二叉樹”的中序遍歷，不過這個(gè)我會(huì)在后面講的，現(xiàn)在可以當(dāng)

公式記住吧，就是找到右節(jié)點(diǎn)的左子樹最左孩子。

比如：首先 找到50的右孩子70。

然后 找到70的最左孩子，發(fā)現(xiàn)沒有，則返回自己。

最后 原始圖和最終圖如下。

3.說了這么多，上代碼說話。

運(yùn)行結(jié)果：

值的注意的是：二叉排序樹同樣采用“空間換時(shí)間”的做法。

突然發(fā)現(xiàn)，二叉排序樹的中序遍歷同樣可以排序數(shù)組，呵呵，不錯(cuò)！

PS: 插入操作：O(LogN)。

刪除操作：O(LogN)。

查找操作：O(LogN）。