//插入新节点 function insert(data) { var n = new Node( data , null , null ); if( this.root == null ){ this.root = n; }else{ var current = this.root; var parent; while( true ){ parent = current; if( data < current.data ){ current = current.left; if( current == null ){ parent.left = n ; break; } }else{ current = current.right; if( current == null ){ parent.right = n; break; } } } } }
现在BST类已初步成型，但操作还仅仅限于插入节点，我们需要有遍历BST的能力，上面我们也提到了是三种遍历方式。其中中序遍历是最容易实现的，我们需要升序的方法访问树中的所有节点，先访问左子树，在访问根节点，最后是右子树，我们采用递归来实现！
inOrder：中序遍历
// 中序遍历 function inOrder (node) { if( !(node == null )){ inOrder( node.left ); console.debug( node.show() + ' '); inOrder( node.right ); } }
怎么样，了解了原理，实现起来还是蛮简单的~
我们用一段代码来测试一下我们所写的中序遍历：
var nums = new BST(); //插入数据 nums.insert(23); nums.insert(45); nums.insert(16); nums.insert(37); nums.insert(3); nums.insert(99); nums.insert(22);
上述插入数据后，会形成如下的二叉树
BST
中序遍历结果如下：
//中序遍历 console.log("Inorder traversal: "); inOrder(nums.root); // Inorder traversal: // 3 16 22 23 37 45 99
preOrder：先序遍历
有了中序遍历的基础，相信先序遍历的实现你已经想出来，怎么样？看看对吗？
//先序遍历 function preOrder( node ) { if( !(node == null )){ console.log( node.show() + ' '); preOrder( node.left ); preOrder( node.right ); } }
怎么样，看起来是不是和中序遍历差不多，唯一的区别就是 if 语句中代码的执行顺序，中序遍历中 show 方法放在两个递归调用之间，先序遍历则放在递归调用之前。
先序遍历结果如下：
// 先序遍历 console.log("Preorder traversal: "); preOrder(nums.root); // Preorder traversal: // 23 16 3 22 45 37 99
postOrder：后序遍历
后序遍历的实现和前面的基本相同，将 show 方法放在递归调用之后执行即可
//后序遍历 function postOrder ( node ) { if( !(node == null ) ){ postOrder( node.left ); postOrder( node.right ); console.log( node.show() + ' '); } }
后序遍历结果如下：
// 后序遍历 console.log("Postorder traversal: "); postOrder(nums.root); // Postorder traversal: // 3 22 16 37 99 45 23
二叉查找树的查找运算对于BST通常有一下三种的查找类型：
查找给定值
查找最大值
查找最小值
我们接下来一起来讨论三种查找的方式的实现。
要查找BST中的最小值和最大值是非常简单的。因为较小的值总是在左子节点上，要想查找BST中的最小值，只需遍历左子树，直到找到最后一个节点即可。同理，查找最大值，只需遍历右子树，直到找到最后一个节点即可。
getMin：查找最小值
遍历左子树，直到左子树的某个节点的 left 为 null 时，该节点保存的即为最小值
//查找最小值 function getMin( ) { var current = this.root; while ( !( current.left == null ) ){ current = current.left; } return current.show(); }
getMax：查找最大值
遍历右子树，直到右子树的某个节点的 right 为 null 时，该节点保存的即为最大值
//查找最大值 function getMax () { var current = this.root; while ( !( current.right == null ) ) { current = current.right; } return current.show(); }
我们还是利用前面构建的树来测试：
// 最小值 console.log('min:' + nums.getMin() ); // min : 3 //最大值 console.log('max:' + nums.getMax() ); // max : 99