引言：
上次我們結束了類和對象的收尾，之后我們就要學習一些高級的數據結構，今天我們先來看一個數據結構-- 二叉搜索樹。
一： 二叉搜索樹的概念(性質)
二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質的二叉樹:
- 若它的左子樹不為空，則左子樹上所有結點的值都小于等于根結點的值。
- 若它的右子樹不為空，則右子樹上所有結點的值都大于等于根結點的值。
- 它的左右子樹也分別為二叉搜索樹。
- 二叉搜索樹中可以支持插入相等的值，也可以不支持插入相等的值，具體看使用場景定義，后續我們學習
map/set/multimap/multiset系列容器底層就是二叉搜索樹，其中map/set不支持插入相等值，multimap/multiset支持插入相等值。
左圖就是map，不支持插入相同的數據。
右圖就是multimap，支持插入相同的數據。
二：二叉搜索樹的性能分析：
最優情況下，二叉搜索樹為完全二叉樹(或者接近完全二叉樹)，其高度為： log2N。
最差情況下，二叉搜索樹退化為單支樹(或者類似單支)，其高度為：N。
所以綜合而言二叉搜索樹增刪查改時間復雜度為：O(N)。
那么這樣的效率顯然是無法滿足我們需求的，我們后續會接著學習二叉搜索樹的變形，平衡二叉搜索樹（AVL樹）和紅黑樹，才能適用于我們在內存中存儲和搜索數據。
另外需要說明的是，二分查找也可以實現o(log2N)級別的查找效率，但是二分查找有兩大缺陷：
- 需要存儲在支持下標隨機訪問的結構中，并且有序。
- 插入和刪除數據效率很低，因為存儲在下標隨機訪問的結構中，插入和刪除數據一般需要挪動數據。
因此這里也就體現出了平衡二叉搜索樹的價值。
三：模擬實現二叉搜索樹
1. 基本框架：
因為二叉搜索樹是二叉樹衍生而來的，因此其基本結構和二叉樹差不多，因此這里我們就不細講：
2. 插入數據：
（1）插入原則：
插入的具體過程如下：
- 樹為空，則直接新增結點，賦值給
root指針。 - 樹不空，按二叉搜索樹性質，插入值比當前結點大往右走，插入值比當前結點小往左走，找到空位置，插入新結點。
- 如果支持插入相等的值，插入值跟當前結點相等的值可以往右走，也可以往左走，找到空位置，插入新結點。（要注意的是要保持邏輯一致性，插入相等的值不要一會往右走，一會往左走，但是這里我們實現的是不支持插入相同數據的）
（2）思路分析：
（3）補充：
注：由于插入數據的時候牽扯到數據的申請，因此這里的節點結構要提供對于的構造函數來生成節點。
（4）代碼實現：
（5）測試：
注：這里為了測試插入數據，因此我們再實現一個中序遍歷。
中序遍歷實現：
可以看到測試結果沒有問題。
3. 查找數據：
（1）查找原則：
從根開始比較，查找x，x比根的值大則往右邊走查找，x比根值小則往左邊走查找。
2. 最多查找高度次，走到空，還沒找到，這個值不存在。
3. 如果不支持插入相等的值，找到x即可返回。
4. 如果支持插入相等的值，意味著有多個x存在，一般要求查找中序的第一個x。如下圖，查找3，要找到1的右孩子的那個3返回。
（2）思路分析：
查找的邏輯和插入的邏輯基本上一樣，就不再具體分析。
（3） 代碼實現：
（4）測試:
測試沒問題。
4. 刪除數據：
相較于插入數據，刪除數據就比較復雜了，需要考慮各種情況，下面我們來一點點分析：
首先查找元素是否在二叉搜索樹中，如果不存在，則返回false。
如果查找元素存在則分以下四種情況分別處理：（假設要刪除的結點為N）
- 要刪除結點N左右孩子均為空。
- 要刪除的結點N左孩子位空，右孩子結點不為空。
- 要刪除的結點N右孩子位空，左孩子結點不為空。
- 要刪除的結點N左右孩子結點均不為空。
對應以上四種情況的解決方案： - 把N結點的父親對應孩子指針指向空，直接刪除N結點（情況1可以當成2或者3處理，效果是一樣的）
- 把N結點的父親對應孩子指針指向N的右孩子，直接刪除N結點。
- 把N結點的父親對應孩子指針指向N的左孩子，直接刪除N結點。
- 無法直接刪除N結點，因為N的兩個孩子無處安放，只能用替換法刪除。找N左子樹的值最大結點R(最右結點)或者N右子樹的值最小結點R(最左結點)替代N，因為這兩個結點中任意一個，放到N的位置，都滿足二叉搜索樹的規則。替代N的意思就是N和R的兩個結點的值交換，轉而變成刪除R結點，R結點符合情況2或情況3，可以直接刪除。
（1） 思路分析：
（2）代碼實現：
(3) 測試:
5. 銷毀
（1）思路分析：
跟之前我們的二叉樹銷毀一樣，只需要后序遍歷來銷毀即可。
（2） 代碼實現：
6. 拷貝構造函數
這里跟之前二叉樹的構建一樣，只需要一邊遍歷一邊構建即可。
（2）代碼實現：
（3）測試：
7. 賦值運算符重載：
（1）思路分析：
這里的賦值運算符重載和之前差不多，還是復用拷貝構造函數。
（2）代碼實現：
（3）測試：
