你的位置:首页 > Java教程

[Java教程]javascript数据结构——写一个二叉搜索树


二叉搜索树就是左侧子节点值比根节点值小,右侧子节点值比根节点值大的二叉树。

照着书敲了一遍。

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    }  }}