二叉搜索树就是左侧子节点值比根节点值小，右侧子节点值比根节点值大的二叉树。
照着书敲了一遍。
function BinarySearchTree(){ var Node = function(key){ this.key = key this.left = null this.right = null } var root = null this.insert = function(key){ //插入节点 var newNode = new Node(key) if(root === null){ //树为空 root = newNode }else{ insertNode(root,newNode) } } //插入的辅助函数 var insertNode = function(node,newNode){ if(newNode.key < node.key){ //如果新节点值比当前节点小 //则当前节点作为根节点，在当前节点左侧子节点寻找合适的位置 if(node.left === null){ node.left = newNode }else{ insertNode(node.left,newNode) } }else{ //新节点值比当前节点大 //当前节点作为根节点，在当前节点右侧子节点寻找合适的位置 if(node.right === null){ node.right = newNode }else{ insertNode(node.right,newNode) } } } this.search = function(key){ return searchNode(root,key) } var searchNode = function(node,key){ if(node === null){ return false } if(key < node.key){ return searchNode(node.left,key) }else if(key > node.key){ return searchNode(node.right,key) }else{ return true } } //callback,调用遍历时作为参数传入 function printNode(value){ //打印节点值 console.log(value) } this.inOrderTraverse = function(callback){ //中序遍历 inOrderTraverseNode(root,callback) } //中序遍历辅助函数 var inOrderTraverseNode = function(node,callback){ if(node != null){ inOrderTraverseNode(node.left,callback) callback(node.key) inOrderTraverseNode(node.right,callback) } } this.preOrderTraverse = function(callback){ //前序遍历 preOrderTraverseNode(root,callback) } //前序遍历辅助函数 var preOrderTraverseNode = function(node,callback){ if(node != null){ callback(node.key) preOrderTraverseNode(node.left,callback) preOrderTraverseNode(node.right,callback) } } this.postOrderTraverse = function(){ //后序遍历 postOrderTraverseNode(root,callback) } //后序遍历辅助函数 var postOrderTraverseNode = function(node,callback){ if(node != null){ postOrderTraverseNode(node.left,callback) postOrderTraverseNode(node.right,callback) callback(node.key) } } this.min = function(){ //寻找最小值 //最小值往二叉搜索树最左侧寻找 return minNode(root) } var minNode = function(node){ if(node){ while(node && node.left!=null){ node = node.left } return node.key }else{ return null } } this.max = function(){ //寻找最大值 //最大值往二叉搜索树最右侧寻找 return maxNode(root) } var maxNode = function(node){ if(node){ while(node && node.right!=null){ node = node.right } return node.key }else{ return null } } //remove这个方法，我一开始没有搞懂为什么要令root = removeNode(root,key) //反复研究了几遍代码之后我才看明白了是为了更新节点 //包括之后的removeNode方法 //每一次递归更新子节点，最后还有return node更新父节点 //因为此时父节点node的子节点已经不一样了，所以需要更新 this.remove = function(key){ root = removeNode(root,key) } var removeNode = function(node,key){ if(node === null){ return null } if(key < node.key){ node.left = removeNode(node.left,key) return node }else if(key > node.key){ node.right = removeNode(node.right,key) return node }else{ //key === node.key if(node.left === null && node.right === null){ //删除节点为叶子结点 node = null return node } //删除的节点只有一个子节点 if(node.left === null){ node = node.right return node }else if(node.right === null){ node = node.left return node } //删除的节点有两个子节点 //从右侧子节点里寻找出最小的节点来继承当前节点 //然后删除那个最小的右侧子节点 var aux = findMinNode(node.right) node.key = aux.key node.right = removeNode(node.right,aux.key) return node } } var findMinNode = function(node){ if(node){ while(node && node.left!=null){ node = node.left } return node }else{ return null } }}
原标题：javascript数据结构——写一个二叉搜索树
关键词：JavaScript
我知道了 