在樹中，有三種經常執行的搜索類型：
搜索最小值
搜索最大值
搜索特定的值
我們依次來看。
8.5.1 搜索最小值和最大值
我們使用下面的樹作為示例：
只用眼睛看這張圖，你能一下找到樹中的最小值和最大值嗎？
如果你看一眼樹最後一層最左側的節點，會發現它的值為3，這是這棵樹中最小的鍵。如果你再看一眼樹最右端的節點（同樣是樹的最後一層），會發現它的值為25，這是這棵樹中最大的鍵。這條信息在我們實現搜索樹節點的最小值和最大值的方法時能給予我們很大的幫助。
首先，我們來看尋找樹的最小鍵的方法：
this.min = function {
return minNode(root); //{1}
};
min方法將會暴露給用戶。這個方法調用了minNode方法（行{1}）：
var minNode = function (node) {
if (node){
while (node && node.left !== null) { //{2}
node = node.left; //{3}
}
return node.key;
}
return null; //{4}
};
minNode方法允許我們從樹中任意一個節點開始尋找最小的鍵。我們可以使用它來找到一棵樹或它的子樹中最小的鍵。因此，我們在調用minNode方法的時候傳入樹的根節點（行{1}），因為我們想要找到整棵樹的最小鍵。
在minNode內部，我們會遍歷樹的左邊（行{2}和行{3}）直到找到樹的最下層（最左端）。
以相似的方式，可以實現max方法：
this.max = function {
return maxNode(root);
};
var maxNode = function (node) {
if (node){
while (node && node.right !== null) { //{5}
node = node.right;
}
return node.key;
}
return null;
};
要找到最大的鍵，我們要沿著樹的右邊進行遍歷（行{5}）直到找到最右端的節點。
因此，對於尋找最小值，總是沿著樹的左邊；而對於尋找最大值，總是沿著樹的右邊。
8.5.2 搜索一個特定的值
在之前的章節中，我們同樣實現了find、search或get方法來查找數據結構中的一個特定的值（和之前章節中實現的has方法相似）。我們將同樣在BST中實現搜索的方法，來看它的實現：
this.search = function(key){
return searchNode(root, key); //{1}
};
var searchNode = function(node, key){
if (node === null){ //{2}
return false;
}
if (key < node.key){ //{3}
return searchNode(node.left, key); //{4}
} else if (key > node.key){ //{5}
return searchNode(node.right, key); //{6}
} else {
return true; //{7}
}
};
我們要做的第一件事，是聲明search方法。和BST中聲明的其他方法的模式相同，我們將會使用一個輔助函數（行{1}）。
searchNode方法可以用來尋找一棵樹或它的任意子樹中的一個特定的值。這也是為什麼在行{1}中調用它的時候傳入樹的根節點作為參數。
在開始算法之前，先要驗證作為參數傳入的node是否合法（不是null）。如果是null的話，說明要找的鍵沒有找到，返回false。
如果傳入的節點不是null，需要繼續驗證。如果要找的鍵比當前的節點小（行{3}），那麼繼續在左側的子樹上搜索（行{4}）。如果要找的鍵比當前的節點大，那麼就從右側子節點開始繼續搜索（行{6}），否則就說明要找的鍵和當前節點的鍵相等，就返回true來表示找到了這個鍵（行{7}）。
可以通過下面的代碼來測試這個方法：
console.log(tree.search(1) ? \'Key 1 found.\' : \'Key 1 not found.\');
console.log(tree.search(8) ? \'Key 8 found.\' : \'Key 8 not found.\');
輸出結果如下：
Value 1 not found.
Value 8 found.
讓我們詳細展示查找1這個鍵的時候方法是如何執行的。
(1) 調用searchNode方法，傳入根節點作為參數（行{1}）。（node[root[11]]）不是null（行{2}），因此我們執行到行{3}。
(2) （key[1] < node[11]）為ture（行{3}），因此來到行{4}並再次調用searchNode方法，傳入（node[7], key[1]）作為參數。
(3) （node[7]）不是null（ {2}），因此繼續執行行{3}。
(4) （key[1] < node[7]）為ture（行{3}），因此來到行{4}並再次調用searchNode方法，傳入（node[5], key[1]）作為參數。
(5) （node[5]）不是null（行{2}），因此繼續執行行{3}。
(6) （key[1] < node[5]）為ture（行{3}），因此來到行{4}並再次調用searchNode方法，傳入（node[3], key[1]）作為參數。
(7) （node[3]）不是null（行{2}），因此來到行{3}。
(8) （key[1] < node[3]）為真（行{3}），因此來到行{4}並再次調用searchNode方法，傳入（null, key[1]）作為參數。null被作為參數傳入是因為node[3]是一個葉節點（它沒有子節點，所以它的左側子節點的值為null）。
(9) 節點（null）的值為null（行{2}，這時要搜索的節點為null），因此返回false。
(10) 然後，方法調用會依次出棧，代碼執行過程結束。
讓我們再來查找值為8的節點。
(1) 調用searchNode方法，傳入root作為參數（行{1}）。（node[root[11]]）不是null（行{2}），因此我們來到行{3}。
(2) （key[8] < node[11]）為真（行{3}），因此執行到行{4}並再次調用searchNode方法，傳入（node[7], key[8]）作為參數。
(3) （node[7]）不是null，因此來到行{3}。
(4) （key[8] < node[7]）為假（行{3}），因此來到行{5}。
(5) （key[8] > node[7]）為真（行{5}），因此來到行{6}並再次調用searchNode方法，傳入（node[9], key[8]）作為參數。
(6) （node[9]）不是null（行{2}），因此來到行{3}。
(7) （key[8] < node[9]）為真（行{3}），因此來到行{4}並再次調用searchNode方法，傳入（node[8], key[8]）作為參數。
(8) （node[8]）不是null（行{2}），因此來到行{3}。
(9) （key[8] < node[8]）為假（行{3}），因此來到行{5}。
(10)（key[8] > node[8]）為假（行{5}），因此來到行{7}並返回true，因為node[8]就是要找的鍵。
(11) 然後，方法調用會依次出棧，代碼執行過程結束。
8.5.3 移除一個節點
我們要為BST實現的下一個、也是最後一個方法是remove方法。這是我們在本書中要實現的最複雜的方法。我們先創建這個方法，使它能夠在樹的實例上被調用：
this.remove = function(key){ root = removeNode(root, key); //{1} };
這個方法接收要移除的鍵並且它調用了removeNode方法，傳入root和要移除的鍵作為參數（行{1}）。我要提醒大家的一件非常重要的事情是，root被賦值為removeNode方法的返回值。我們稍後會明白其中的原因。
removeNode方法的複雜之處在於我們要處理不同的運行場景，當然也包括它同樣是通過遞歸來實現的。
我們來看removeNode方法的實現：
var removeNode = function(node, key){
if (node === null){ //{2}
return null;
}
if (key < node.key){ //{3}
node.left = removeNode(node.left, key); //{4}
return node; //{5}
} else if (key > node.key){ //{6}
node.right = removeNode(node.right, key); //{7}
return node; //{8}
} else { //鍵等於node.key
//第一種情況——一個葉節點
if (node.left === null && node.right === null){ //{9}
node = null; //{10}
return node; //{11}
}
//第二種情況——一個只有一個子節點的節點
if (node.left === null){ //{12}
node = node.right; //{13}
return node; //{14}
} else if (node.right === null){ //{15}
node = node.left; //{16}
return node; //{17}
}
//第三種情況——一個有兩個子節點的節點
var aux = findMinNode(node.right); //{18}
node.key = aux.key; //{19}
node.right = removeNode(node.right, aux.key); //{20}
return node; //{21}
}
};
我們來看行{2}，如果正在檢測的節點是null，那麼說明鍵不存在於樹中，所以返回null。
然後，我們要做的第一件事，就是在樹中找到要移除的節點。因此，如果要找的鍵比當前節點的值小（行{3}），就沿著樹的左邊找到下一個節點（行{4}）。如果要找的鍵比當前節點的值大（行{6}），那麼就沿著樹的右邊找到下一個節點（行{7}）。
如果我們找到了要找的鍵（鍵和node.key相等），就需要處理三種不同的情況。
findMinNode方法如下：
var findMinNode = function(node){
while (node && node.left !== null) {
node = node.left;
}
return node;
};
移除一個葉節點
第一種情況是該節點是一個沒有左側或右側子節點的葉節點——行
{9}。在這種情況下，我們要做的就是給這個節點賦予null值來移除它（行{9}）。但是當學習了鏈表的實現之後，我們知道僅僅賦一個null值是不夠的，還需要處理指針。在這裡，這個節點沒有任何子節點，但是它有一個父節點，需要通過返回null來將對應的父節點指針賦予null值（行{11}）。現在節點的值已經是
null了，父節點指向它的指針也會接收到這個值，這也是我們要在函數中返回節點的值的原因。父節點總是會接收到函數的返回值。另一種可行的辦法是將父節點和節點本身都作為參數傳入方法內部。如果回頭來看方法的第一行代碼，會發現我們在行
{4}和行{7}更新了節點左右指針的值，同樣也在行{5}和行{8}返回了更新後的節點。下圖展現了移除一個葉節點的過程：
移除有一個左側或右側子節點的節點
現在我們來看第二種情況，移除有一個左側子節點或右側子節點的節點。這種情況下，需要跳過這個節點，直接將父節點指向它的指針指向子節點。
如果這個節點沒有左側子節點（行
{12}），也就是說它有一個右側子節點。因此我們把對它的引用改為對它右側子節點的引用（行{13}）並返回更新後的節點（行{14}）。如果這個節點沒有右側子節點，也是一樣——把對它的引用改為對它左側子節點的引用（行{16}）並返回更新後的值（行{17}）。下圖展現了移除只有一個左側子節點或右側子節點的節點的過程：
移除有兩個子節點的節點
現在是第三種情況，也是最複雜的情況，那就是要移除的節點有兩個子節點——左側子節點和右側子節點。要移除有兩個子節點的節點，需要執行四個步驟。
(1) 當找到了需要移除的節點後，需要找到它右邊子樹中最小的節點（它的繼承者——行
{18}）。(2) 然後，用它右側子樹中最小節點的鍵去更新這個節點的值（行
{19}）。通過這一步，我們改變了這個節點的鍵，也就是說它被移除了。(3) 但是，這樣在樹中就有兩個擁有相同鍵的節點了，這是不行的。要繼續把右側子樹中的最小節點移除，畢竟它已經被移至要移除的節點的位置了（行
{20}）。(4) 最後，向它的父節點返回更新後節點的引用（行
{21}）。findMinNode方法的實現和min方法的實現方式是一樣的。唯一不同之處在於，在min方法中只返回鍵，而在findMinNode中返回了節點。下圖展現了移除有兩個子節點的節點的過程：
