目錄
簡介
BST的基本性質
BST的建構
BST的搜尋
BST的插入
BST的删除
樹是類似于連結清單的資料結構，和連結清單的線性結構不同的是，樹是具有層次結構的非線性的資料結構。
樹是由很多個節點組成的，每個節點可以指向很多個節點。
如果一個樹中的每個節點都隻有0，1，2個子節點的話，這顆樹就被稱為二叉樹，如果我們對二叉樹進行一定的排序。
比如，對于二叉樹中的每個節點，如果左子樹節點的元素都小于根節點，而右子樹的節點的元素都大于根節點，那麼這樣的樹被叫做二叉搜尋樹（Binary Search Tree）簡稱BST。
今天我們來探讨一下BST的性質和對BST的基本操作。
剛剛我們已經講過BST的基本特征了，現在我們再來總結一下：
BST中任意節點的左子樹一定要比該節點的值要小
BST中任意節點的右子樹一定要比該節點的值要大
BST中任意節點的左右子樹一定要是一個BST。
看一張圖直覺的感受一下BST：
怎麼用代碼來建構一個BST呢？
首先，BST是由一個一個的節點Node組成的，Node節點除了儲存節點的資料之外，還需要指向左右兩個子節點，這樣我們的BST完全可以由Node連接配接而成。
另外我們還需要一個root節點來表示BST的根節點。
相應的代碼如下：
先看下BST的搜尋，如果是上面的BST，我們想搜尋32這個節點應該是什麼樣的步驟呢？
先上圖：
搜尋的基本步驟是：
從根節點41出發，比較根節點和搜尋值的大小
如果搜尋值小于節點值，那麼遞歸搜尋左側樹
如果搜尋值大于節點值，那麼遞歸搜尋右側樹
如果節點比對，則直接傳回即可。
相應的java代碼如下：
搜尋講完了，我們再講BST的插入。
先看一個動畫：
上的例子中，我們向BST中插入兩個節點30和55。
插入的邏輯是這樣的：
從根節點出發，比較節點資料和要插入的資料
如果要插入的資料小于節點資料，則遞歸左子樹插入
如果要插入的資料大于節點資料，則遞歸右子樹插入
如果根節點為空，則插入目前資料作為根節點
BST的删除要比插入複雜一點，因為插入總是插入到葉子節點，而删除可能删除的是非葉子節點。
我們先看一個删除葉子節點的例子：
上面的例子中，我們删除了30和55這兩個節點。
可以看到，删除葉子節點是相對簡單的，找到之後删除即可。
我們再來看一個比較複雜的例子，比如我們要删除65這個節點：
可以看到需要找到65這個節點的右子樹中最小的那個，替換掉65這個節點即可（當然也可以找到左子樹中最大的那個）。
是以删除邏輯是這樣的：
從根節點開始，比較要删除節點和根節點的大小
如果要删除節點比根節點小，則遞歸删除左子樹
如果要删除節點比根節點大，則遞歸删除右子樹
如果節點比對，又有兩種情況
如果是單邊節點，直接傳回節點的另外一邊
如果是雙邊節點，則先找出右邊最小的值，作為根節點，然後将删除最小值過後的右邊的節點，作為根節點的右節點
看下代碼的實作：
這裡我們使用遞歸來實作的删除雙邊節點，大家可以考慮一下有沒有其他的方式來删除呢？
本文的代碼位址：
learn-algorithm
本文收錄于 www.flydean.com 最通俗的解讀，最深刻的幹貨，最簡潔的教程，衆多你不知道的小技巧等你來發現！ 歡迎關注我的公衆号:「程式那些事」,懂技術，更懂你！