原理：
叉排序树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉排序树的存储结构。中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索,插入,删除的复杂度等于树高，O(log(n)).
JavaScript实现：
var BinarySearchTree = function(){ this.root = null; } BinarySearchTree.prototype = { insert: function(key){//插入 var newNode = new this.Node(key); if(this.root === null){ this.root = newNode; }else{ this.insertNode(this.root, newNode) } console.log(this.root) }, inOrderTraverse: function(callback){//中序查找 this.inOrderTraverseNode(this.root, callback); }, preOrderTraverse: function(callback){//先序查找 this.preOrderTraverseNode(this.root, callback); }, postOrderTraverse: function(callback){//后序查找 this.postOrderTraverseNode(this.root, callback); }, min: function(){//最小值 return this.minNode(this.root) }, max: function(){//最大值 return this.maxNode(this.root) }, search: function(key){//查找 this.searchNode(this.root, key) }, remove: function(key){//移除树节点 this.removeNode(this.root, key) }, Node: function(key){ this.key = key; this.left = null; this.right = null; }, insertNode: function(node, newNode){ if(newNode.key < node.key){ if(node.left === null){ node.left = newNode; }else{ this.insertNode(node.left, newNode) } }else{ if(node.right === null){ node.right = newNode; }else{ this.insertNode(node.right, newNode) } } }, inOrderTraverseNode: function(node, callback){ if(node !== null){ this.inOrderTraverseNode(node.left, callback); callback(node.key); this.inOrderTraverseNode(node.right, callback); } }, preOrderTraverseNode: function(node, callback){ if(node !== null){ callback(node.key); this.preOrderTraverseNode(node.left, callback); this.preOrderTraverseNode(node.right, callback); } }, postOrderTraverseNode: function(node, callback){ if(node !== null){ this.postOrderTraverseNode(node.left, callback); this.postOrderTraverseNode(node.right, callback); callback(node.key); } }, minNode: function(node){ if(node){ while(node && node.left !== null){ node = node.left; } return node.key; } return null; }, maxNode: function(node){ if(node){ while(node && node.right !== null){ node = node.right; } return node.key; } return null; }, searchNode: function(node, key){ if(node === null) return false; if(key < node.key){ return this.searchNode(node.left, key); }else if(key > node.key){ return this.searchNode(node.right, key); }else{ return true; } }, removeNode(node, key){ if(node === null) return null; if(key < node.key){ node.left = this.removeNode(node.left, key); return node; }else if(key > node.key){ node.right = this.removeNode(node.right, key); return node; }else{ if(node.left === null && node.right === null){ node = null; return node; }else if(node.left === null){ node = node.right; return node; }else if(node.right === null){ node = node.left; return node; } var aux = this.findMinNode(node.right); node.key = aux.key; node.right = this.removeNode(node.right, aux.key); return node; } }, findMinNode: function(node){ if(node){ while(node && node.left !== null){ node = node.left; } return node.key; } return null; } }
