JavaScript实现二叉搜索树

JavaScript中的搜索二叉树实现，供大家参考，具体内容如下

二叉搜索树（BST，Binary SeArch Tree），也称二叉排序树或二叉查找树

二叉搜索树是一颗二叉树, 可以为空；如果不为空，满足以下性质：

• 非空左子树的所有键值小于其根结点的键值
• 非空右子树的所有键值大于其根结点的键值
• 也就是左结点值想根结点值右节点值
• 左、右子树本身也都是二叉搜索树

二叉搜索树的操作

insert(key)：向树中插入一个新的键

search(key)：在树中查找一个键，如果结点存在，则返回true；如果不存在，则返回false

inOrderTraverse：通过中序遍历方式遍历所有结点

PReOrderTraverse：通过先序遍历方式遍历所有结点

postOrderTraverse：通过后序遍历方式遍历所有结点

min：返回树中最小的值/键

max：返回树中最大的值/键

remove(key)：从树中移除某个键

先序遍历

• ①访问根结点
• ②先序遍历其左子树
• ③先序遍历其右子树
  

中序遍历

①中序遍历其左子树
②访问根结点
③中序遍历其右子树

后序遍历

①后序遍历其左子树
②后序遍历其右子树
③访问根结点

JavaScript 代码实现队列结构

// 创建BinarySearchTreefunction BinarySerachTree() {
  // 创建节点构造函数  function Node(key) {
    this.key = key    this.left = null    this.right = null  }
  // 保存根的属性  this.root = null  // 二叉搜索树相关的操作方法  // 向树中插入数据  BinarySerachTree.prototyPE.insert = function (key) {
    // 1.根据key创建对应的node    VAR newNode = new Node(key)    // 2.判断根节点是否有值    if (this.root === null) {
      this.root = newNode    }
 else {
      this.insertNode(this.root, newNode)    }
  }
  BinarySerachTree.prototype.insertNode = function (node, newNode) {
    if (newNode.key  node.key) {
 // 1.准备向左子树插入数据      if (node.left === null) {
 // 1.1.node的左子树上没有内容        node.left = newNode      }
 else {
 // 1.2.node的左子树上已经有了内容        this.insertNode(node.left, newNode)      }
    }
 else {
 // 2.准备向右子树插入数据      if (node.right === null) {
 // 2.1.node的右子树上没有内容        node.right = newNode      }
 else {
 // 2.2.node的右子树上有内容        this.insertNode(node.right, newNode)      }
    }
  }
  // 获取最大值和最小值  BinarySerachTree.prototype.min = function () {
    var node = this.root    while (node.left !== null) {
      node = node.left    }
    return node.key  }
  BinarySerachTree.prototype.max = function () {
    var node = this.root    while (node.right !== null) {
      node = node.right    }
    return node.key  }
  // 搜搜特定的值  /*  BinarySerachTree.prototype.search = function (key) {
    return this.searchNode(this.root, key)  }
  BinarySerachTree.prototype.searchNode = function (node, key) {
    // 1.如果传入的node为null那么, 那么就退出递归    if (node === null) {
      return false    }
        // 2.判断node节点的值和传入的key大小    if (node.key >
 key) {
 // 2.1.传入的key较小, 向左边继续查找      return this.searchNode(node.left, key)    }
 else if (node.key  key) {
 // 2.2.传入的key较大, 向右边继续查找      return this.searchNode(node.right, key)    }
 else {
 // 2.3.相同, 说明找到了key      return true    }
  }
  */  BinarySerachTree.prototype.search = function (key) {
    var node = this.root    while (node !== null) {
          if (node.key >
 key) {
        node = node.left      }
 else if (node.key  key) {
        node = node.right      }
 else {
        return true      }
    }
    return false  }
  // 删除节点  BinarySerachTree.prototype.remove = function (key) {
    // 1.获取当前的node    var node = this.root    var parent = null    // 2.循环遍历node    while (node) {
          if (node.key >
 key) {
        parent = node        node = node.left      }
 else if (node.key  key) {
        parent = node        node = node.right      }
 else {
            if (node.left == null &
    &
 node.right == null) {
        }
      }
    }
  }
  BinarySerachTree.prototype.removeNode = function (node, key) {
        // 1.如果传入的node为null, 直接退出递归.    if (node === null) return null    // 2.判断key和对应node.key的大小    if (node.key >
 key) {
      node.left = this.removeNode(node.left, key)    }
  }
  // 删除结点  BinarySerachTree.prototype.remove = function (key) {
    // 1.定义临时保存的变量    var current = this.root    var parent = this.root    var isLeftChild = true    // 2.开始查找节点    while (current.key !== key) {
      parent = current      if (key  current.key) {
        isLeftChild = true        current = current.left      }
 else {
        isLeftChild = false        current = current.right      }
      // 如果发现current已经指向null, 那么说明没有找到要删除的数据      if (current === null) return false    }
        // 3.删除的结点是叶结点    if (current.left === null &
    &
 current.right === null) {
      if (current == this.root) {
        this.root == null      }
 else if (isLeftChild) {
        parent.left = null      }
 else {
        parent.right = null      }
    }
    // 4.删除有一个子节点的节点    else if (current.right === null) {
      if (current == this.root) {
        this.root = current.left      }
 else if (isLeftChild) {
        parent.left = current.left      }
 else {
        parent.right = current.left      }
    }
 else if (current.left === null) {
      if (current == this.root) {
        this.root = current.right      }
 else if (isLeftChild) {
        parent.left = current.right      }
 else {
        parent.right = current.right      }
    }
    // 5.删除有两个节点的节点    else {
      // 1.获取后继节点      var successor = this.getSuccessor(current)      // 2.判断是否是根节点      if (current == this.root) {
        this.root = successor      }
 else if (isLeftChild) {
        parent.left = successor      }
 else {
        parent.right = successor      }
      // 3.将删除节点的左子树赋值给successor      successor.left = current.left    }
    return true  }
  // 找后继的方法  BinarySerachTree.prototype.getSuccessor = function (delNode) {
    // 1.使用变量保存临时的节点    var successorParent = delNode    var successor = delNode    var current = delNode.right // 要从右子树开始找    // 2.寻找节点    while (current != null) {
      successorParent = successor      successor = current      current = current.left    }
    // 3.如果是删除图中15的情况, 还需要如下代码    if (successor != delNode.right) {
      successorParent.left = successor.right      successor.right = delNode.right    }
  }
  // 遍历方法  //handler为回调函数  // 先序遍历  BinarySerachTree.prototype.preOrderTraversal = function (handler) {
    this.preOrderTranversalNode(this.root, handler)  }
  BinarySerachTree.prototype.preOrderTranversalNode = function (node, handler) {
    if (node !== null) {
      handler(node.key)      this.preOrderTranversalNode(node.left, handler)      this.preOrderTranversalNode(node.right, handler)    }
  }
  // 中序遍历  BinarySerachTree.prototype.inOrderTraversal = function (handler) {
    this.inOrderTraversalNode(this.root, handler)  }
  BinarySerachTree.prototype.inOrderTraversalNode = function (node, handler) {
    if (node !== null) {
      this.inOrderTraversalNode(node.left, handler)      handler(node.key)      this.inOrderTraversalNode(node.right, handler)    }
  }
  // 后续遍历  BinarySerachTree.prototype.postOrderTraversal = function (handler) {
    this.postOrderTraversalNode(this.root, handler)  }
  BinarySerachTree.prototype.postOrderTraversalNode = function (node, handler) {
    if (node !== null) {
      this.postOrderTraversalNode(node.left, handler)      this.postOrderTraversalNode(node.right, handler)      handler(node.key)    }
  }
    /*  // 测试遍历结果(inOrderTraversal可以替换成别的遍历方式)    resultString = ""    bst.inOrderTraversal(function (key) {
      resultString += key + " "    }
)    alert(resultString) // 3 5 6 7 8 9 10 11 12 13 14 15 18 20 25    */}
    

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。

• javascript数据结构之二叉搜索树实现方法
• Javascript实现从小到大的数组转换成二叉搜索树
• javascript算法之二叉搜索树的示例代码
• 如何利用JavaScript实现二叉搜索树
• 面向JavaScript入门初学者的二叉搜索树算法教程

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！