二叉樹中的節點最多只能有兩個子節點：一個是左側子節點，另一個是右側子節點。這些定義有助於我們寫出更高效的向/從樹中插入、查找和刪除節點的算法。二叉樹在計算機科學中的應用非常廣泛。
二叉搜索樹（BST）是二叉樹的一種，但是它只允許你在左側節點存儲（比父節點）小的值，在右側節點存儲（比父節點）大（或者等於）的值。上一節的圖中就展現了一棵二叉搜索樹。
二叉搜索樹將是我們在本章中要研究的數據結構。
8.3.1 創建BinarySearchTree類
讓我們開始創建自己的BinarySearchTree類。首先，聲明它的結構：
function BinarySearchTree {
var Node = function(key){ //{1}
this.key = key;
this.left = null;
this.right = null;
};
var root = null; //{2}
}
下圖展現了二叉搜索樹數據結構的組織方式：
和鏈表一樣，將通過指針來表示節點之間的關係（術語稱其為邊）。在雙向鏈表中，每個節點包含兩個指針，一個指向下一個節點，另一個指向上一個節點。對於樹，使用同樣的方式（也使用兩個指針）。但是，一個指向左側子節點，另一個指向右側子節點。因此，將聲明一個Node類來表示樹中的每個節點（行{1}）。值得注意的一個小細節是，不同於在之前的章節中將節點本身稱作節點或項，我們將會稱其為鍵。鍵是樹相關的術語中對節點的稱呼。
我們將會遵循和LinkedList類中相同的模式（第5章），這表示也將聲明一個變量以控制此數據結構的第一個節點。在樹中，它不再是頭節點，而是根元素（行{2}）。
然後，我們需要實現一些方法。下面是將要在樹類中實現的方法。
insert(key)：向樹中插入一個新的鍵。search(key)：在樹中查找一個鍵，如果節點存在，則返回true；如果不存在，則返回false。inOrderTraverse：通過中序遍歷方式遍歷所有節點。preOrderTraverse：通過先序遍歷方式遍歷所有節點。postOrderTraverse：通過後序遍歷方式遍歷所有節點。min：返回樹中最小的值/鍵。max：返回樹中最大的值/鍵。remove(key)：從樹中移除某個鍵。
我們將在後面的小節中實現每個方法。
8.3.2 向樹中插入一個鍵
本章要實現的方法會比前幾章實現的方法稍微複雜一些。我們將會在方法中使用很多遞歸。如果你對遞歸還不熟悉的話，請先參考11.1節。
下面的代碼是用來向樹插入一個新鍵的算法的第一部分：
this.insert = function(key){
var newNode = new Node(key); //{1}
if (root === null){ //{2}
root = newNode;
} else {
insertNode(root,newNode); //{3}
}
};
要向樹中插入一個新的節點（或項），要經歷三個步驟。
第一步是創建用來表示新節點的Node類實例（行{1}）。只需要向構造函數傳遞我們想用來插入樹的節點值，它的左指針和右指針的值會由構造函數自動設置為null。
第二步要驗證這個插入操作是否為一種特殊情況。這個特殊情況就是我們要插入的節點是樹的第一個節點（行{2}）。如果是，就將根節點指向新節點。
第三步是將節點加在非根節點的其他位置。這種情況下，需要一個私有的輔助函數（行{3}），函數定義如下：
var insertNode = function(node, newNode){
if (newNode.key < node.key){ //{4}
if (node.left === null){ //{5}
node.left = newNode; //{6}
} else {
insertNode(node.left, newNode); //{7}
}
} else {
if (node.right === null){ //{8}
node.right = newNode; //{9}
} else {
insertNode(node.right, newNode); //{10}
}
}
};
insertNode函數會幫助我們找到新節點應該插入的正確位置。下面是這個函數實現的步驟。
如果樹非空，需要找到插入新節點的位置。因此，在調用
insertNode方法時要通過參數傳入樹的根節點和要插入的節點。如果新節點的鍵小於當前節點的鍵（現在，當前節點就是根節點）（行
{4}），那麼需要檢查當前節點的左側子節點。如果它沒有左側子節點（行{5}），就在那裡插入新的節點。如果有左側子節點，需要通過遞歸調用insertNode方法（行{7}）繼續找到樹的下一層。在這裡，下次將要比較的節點將會是當前節點的左側子節點。如果節點的鍵比當前節點的鍵大，同時當前節點沒有右側子節點（行
{8}），就在那裡插入新的節點（行{9}）。如果有右側子節點，同樣需要遞歸調用insertNode方法，但是要用來和新節點比較的節點將會是右側子節點。
讓我們通過一個例子來更好地理解這個過程。
考慮下面的情景：我們有一個新的樹，並且想要向它插入第一個值。
var tree = new BinarySearchTree;
tree.insert(11);
這種情況下，樹中有一個單獨的節點，根指針將會指向它。源代碼的行{2}將會執行。
現在，來考慮下圖所示樹結構的情況：
創建上圖所示的樹的代碼如下，它們接著上面一段代碼（插入了鍵為11的節點）之後輸入執行：
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
tree.insert(25);
同時我們想要插入一個值為6的鍵，執行下面的代碼：
tree.insert(6);
下面的步驟將會被執行。
(1) 樹不是空的，行{3}的代碼將會執行。insertNode方法將會被調用（root, key[6]）。
(2) 算法將會檢測行{4}（key[6] < root[11]為真），並繼續檢測行{5}（node.left[7]不是null），然後將到達行{7}並調用insertNode（node.left[7], key[6]）。
(3) 將再次進入insertNode方法內部，但是使用了不同的參數。它會再次檢測行{4}（key[6] < node[7]為真），然後再檢測行{5}（node.left[5]不是null），接著到達行{7}，調用insertNode（node.left[5], key[6]）。
(4) 將再一次進入insertNode方法內部。它會再次檢測行{4}（key[6] < node[5]為假），然後到達行{8}（node.right是null——節點5沒有任何右側的子節點），然後將會執行行{9}，在節點5的右側子節點位置插入鍵6。
(5) 然後，方法調用會依次出棧，代碼執行過程結束。
這是插入鍵6後的結果：
