在树中，有三种经常执行的搜索类型：
搜索最小值
搜索最大值
搜索特定的值
我们依次来看。
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中返回了节点。下图展现了移除有两个子节点的节点的过程：