二叉树中的节点最多只能有两个子节点：一个是左侧子节点，另一个是右侧子节点。这些定义有助于我们写出更高效的向/从树中插入、查找和删除节点的算法。二叉树在计算机科学中的应用非常广泛。
二叉搜索树（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后的结果：