二叉搜尋樹（又：二叉查找樹，二叉排序樹）是以一顆二叉樹來組織的，在代碼實作上，二叉搜尋樹可以用連結清單來表示，将二叉樹的節點看作連結清單的Node對象，每個Node對象包含left、right、parent屬性，它們分别代表節點的左孩子、右孩子、父節點（雙親節點），如果某個孩子或父節點不存在，則用null值表示。
二叉搜尋樹是指具有下面定義的二叉樹（下面1、2點必須背下來）：
1、任何父節點的值均大于等于（>=）左孩子節點值以及左孩子下的所有孩子節點值
2、任何父節點的值均小于（<）右孩子節點值以及右孩子下的所有孩子節點值
3、樹最根節點是唯一父節點值為null的節點
二叉搜尋樹本質上就是一顆二叉樹，二叉樹邏輯上一般有以下類型和形态：
1、空二叉樹
2、隻有一個根節點的二叉樹
3、左斜樹
4、右斜樹
5、完全二叉樹
6、滿二叉樹
二叉搜尋樹一般具有以下動态集合操作API：
1、查找（search）
2、插入（insert）
3、删除（delete）
4、最大值（maxVal）
5、最小值（minVal）
6、前驅（pre）
7、後繼（post）
前驅：給定任意節點，如果該節點是整顆樹的最小值（絕對不存在左孩子的），它的前驅是null；否則如果該節點存在左孩子，它的前驅是以這個左孩子為根下的左邊整顆子樹中最大值的那個節點；如果不存在左孩子且不是最小值，它的前驅是根節點。
後繼：給定任意節點，如果該節點是整顆樹的最大值（絕對不存在右孩子的），它的後繼是null；否則如果該節點存在右孩子，它的後繼是以這個右孩子為根下的右邊整顆子樹中最小值的那個節點；如果不存在右孩子且不是最大值，它的後繼是根節點
二叉搜尋樹基本動态集合操作API的時間複雜度均為O（h）,其中h為二叉樹的高度。
當調用插入接口時（insert）就開始建構了二叉搜尋樹了，是以，研究如何建構二叉樹實際上就是研究如何實作插入方法。根據如下定義，我們來看下如何實作插入接口的代碼：
根據定義，我們還快能夠想到，插入元素一些基本邏輯如下：
1、每個元素值必須是能夠進行大小比較的，至少有定義好比較規則
2、第一次插入元素可以直接作為根。這裡注意，如果第一次插入的值是整棵樹最大值或最小值，那麼這種情況這個二叉樹通過會成為斜樹，就是隻有（首次插入的是最大值）左孩子或（首次插入的是最小值）右孩子的，那麼這棵樹的高度會很高，我們知道，二叉搜尋樹的大部分操作API時間複雜度是0（h）高度h越高，時間複雜度越大，實際使用時可以使用随機方式避免這種情況的發生。
3、後面每次插入元素時，從根開始進行比對，如果小于等于根，循環判斷左孩子下的所有孩子節點直到葉子節點（孩子節點為null值）；如果大于根，循環判斷右孩子下的所有孩子節點直到葉子節點（孩子節點為null值）；
代碼如下：
從根往下查找一個給定的值，我們隻需要判斷這個值是根節點的左孩子還是右孩子，如果是左孩子，那麼将左孩子和這個值比較看是否相等，如果相等就傳回，否則将這個左孩子作為子根按上面邏輯遞歸查找，代碼如下：
給定任意節點的最大值節點：基于這個給定節點循環或遞歸往右查找，直到葉子節點為止，該葉子節點便是整棵樹的最大值節點，代碼如下：
給定任意節點的最小值節點：基于這個給定節點循環或遞歸往左查找，直到葉子節點為止，該葉子節點便是整棵樹的最小值節點，代碼如下：
前驅：給定任意節點，如果該節點是整顆樹的最小值（絕對不存在左孩子的），它的前驅是null；否則如果該節點存在左孩子，它的前驅是以這個左孩子為根下的左邊整顆子樹中最大值的那個節點；如果不存在左孩子且不是最小值，它的前驅是根節點，代碼如下：
後繼：給定任意節點，如果該節點是整顆樹的最大值（絕對不存在右孩子的），它的後繼是null；否則如果該節點存在右孩子，它的後繼是以這個右孩子為根下的右邊整顆子樹中最小值的那個節點；如果不存在右孩子且不是最大值，它的後繼是根節點，代碼如下：
删除API是二叉搜尋樹所有API中最複雜之一，下面我們把它分解多種情況來講解。
1、如果節點隻有一個元素且删除的節點是根節點，那麼直接把根節點置為null即可
2、删除給定任意一個節點，如果該節點隻存在左節點，那麼很簡單，隻需要把左節點替換到該節點上，給定的這個節點就被删除了
3、删除給定任意一個節點，如果該節點隻存在右節點，那麼很簡單，隻需要把右節點替換到該節點上，給定的這個節點就被删除了
4、删除給定任意一個節點，如果該節點存在左右節點，這種情況就比較複雜些，我們知道，删除某個節點一定是要改變二叉樹的結構的，而改變結構可能會破壞二叉搜尋樹的定義。是以複雜之處就是要保證删除後的二叉搜尋樹依然滿足定義，下面直接給出删除的處理邏輯。
4.1、找出被删除節點的後繼節點
4.2、判斷這個後繼節點是否是被删除節點的直接孩子節點（後繼節點不可能是左孩子節點）
4.3、如果後繼節點是被删除節點的直接孩子節點，直接将後繼節點替換到被删除節點的位置
4.4、如果後繼節點不是被删除節點的直接孩子節點，需要先将後繼節點的右孩子節點（根據定義這個後繼節點不可能有左孩子節點的隻有右孩子節點）替換到這個後繼節點位置，最後再把後繼節點替換到被删除節點位置
圖解後繼節點是被删除節點的直接孩子節點的删除前後情況：
圖解後繼節點不是被删除節點的直接孩子節點的删除前後情況：
我們發現，删除API需要替換節點位置能力，我們可以先把這個能力提取出來作為一個獨立的方法，代碼如下：
删除節點代碼如下：
輸出：
建構完成後的二叉樹 [8,12,15,16,17,19,23]
根節點值 16
值為16的節點值 16
值為15的前驅值 12
值為8的前驅值 null
值為16的前驅值 15
值為16的後繼值 17
值為8的後繼值 12
值為23的後繼值 null
值為17的後繼值 19
删除根前根值是 16
删除根後根值是 17
删除根節點後二叉樹正序輸出
8 12 15 17 19 23
删除後值為16的節點值 null
删除後值為17的前驅值 15
删除後值為15的後繼值 17
二叉搜尋樹是二叉樹的一種，顧名思義，二叉搜尋樹一般就是做路徑搜尋用的，如何定義好父節點很重要，調優二叉搜尋樹，實際上就是如何找到集合的中間值作為父節點，因為隻有父節點值處于較中間位置，那麼二叉樹的高度就比較低，查找速度就比較快。如果已知集合是可能有序的或者第一個插入值是最大或小值時，最好通過随機的方式從集合擷取一個值進行插入，避免出現斜樹的情況。