1 二叉搜索樹BST
二叉搜索樹(Binary Search Tree，簡寫BST)，又稱為二叉排序樹或二叉查找樹。其定義為：對於樹中的每個節點，其左子樹的所有節點值都小於該節點的值，其右子樹的所有節點值都大於該節點的值。二叉搜索樹的任意一個子樹也是二叉搜索樹。
前驅節點和後繼節點
二叉樹通過某種方式遍歷後會得到一個序列結果，而某個節點的前驅節點就是遍歷序列中該節點的前一個節點，後繼節點就是遍歷序列中該節點的後一個節點。例如中序前驅節點就是中序遍歷二叉樹後該節點的前一個節點。
由於中序遍歷得到的序列是按從小到大排列的，中序前驅節點就是小於該節點的所有節點中最大的那個節點，中序後繼節點就是大於該節點的所有節點中最小的節點。
2.1 創建二叉搜索樹
2.1.1 創建過程
動態創建二叉樹就是將數組變成一個二叉樹，往往動態創建二叉樹都是創建二叉搜索樹。創建二叉搜索樹的過程就是不斷的向二叉樹中插入節點的過程。在插入節點過程中保證二叉搜索樹的特性：任意一節點的左子樹的所有節點都小於該節點，並且其右子樹的所有節點都大於該節點。例如用數組[10, 6, 8, 15, 13, 17, 11, 14]來創建二叉搜索樹。
1> 首先處理數據10，此時二叉樹的根節點為空，那麼直接把10當做根節點。
2> 處理元素6，與根節點比較：6<10，那麼將6作為根節點的左子節點插入。如下圖：
3> 處理元素8，與根節點比較：8<10，向左子樹移動後比較：8>6，將8作為6的右子節點插入。如下圖：
4> 處理元素15，與根節點比較：15>10，將15作為根節點的右子節點插入，如下圖所示：
5> 處理元素13，與根節點比較：13>10，向右子樹移動後比較：13<15，將13作為15的左子節點插入。如下圖所示：
6> 處理元素17，與根節點比較：17>10，向右子樹移動後比較：17>15，將17作為13的右子節點插入。如下圖所示：
7> 處理元素11，與根節點比較：11>10，向右子樹移動後比較：11<15，向左子樹移動後比較：11<13，將11作為13的左子節點插入。如下圖所示：
8> 處理元素14，與根節點比較：14>10，向右子樹移動後比較：14<15，向左子樹移動後比較：14>13，將14作為13的右子節點插入。如下圖所示，就創建了一棵二叉搜索樹：
2.1.2 總結
1> 由上述過程可以總結到，每個節點插入的過程中都會保證二叉樹為二叉搜索樹，二叉每一個節點都是作為二叉樹的葉子節點插入的。
2> 形成的二叉搜索樹中序遍歷順序為：6，8，10，11，13，14，15，17，一個從小到的的有序序列。
2.1.3 程序示例
給定二叉搜索樹的根節點root和帶插入元素i，有如下幾種情況：
1> 如果root為空，那麼直接將root的元素值賦為i；
2> 如果i小於root位置的元素r且root沒有左子節點，那麼直接將其作為root的左子節點插入；
3>如果i小於root位置的元素r且root有左子節點，將root換為root的左子節點從步驟2開始處理；
4>如果i大於root位置的元素r且root沒有右子節點，那麼直接將其作為root的右子節點插入；
5>如果i大於root位置的元素r且root有右子節點，那麼將root換位root的右子節點從步驟2開始處理；
可見這套規則應用了一個遞歸思想去處理插入問題，遞歸界限是帶插入節點總以葉節點的身份插入到已有的二叉搜索樹中。程序實例如下：
由上述可得，根據一個數組動態構建二叉樹的過程如下所示：