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

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

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

1. 概念:

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

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

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

2.實際操作：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

運行結(jié)果：

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

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

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

刪除操作：O(LogN)。

查找操作：O(LogN）。