当前位置：首页 > 全部内容 > 正文

JavaScript 实现二叉搜索树：构建、查找与删除详解

作者：青柠

时间：2026-10-25

浏览：540

本文详细讲解如何使用 JavaScript 构建二叉搜索树（BST）。内容涵盖节点定义、插入逻辑、递归与迭代查找实现，以及包含叶子节点、单子节点和双子节点三种情况的删除算法，重点解析前驱与后继节点在删除操作中的应用。

文章目录

前言

在前面的内容中，我们已经探讨了二叉树这一数据结构及其遍历算法。接下来，我们将深入探讨一种具有特殊性质的二叉树——二叉搜索树（BST，Binary Search Tree），它也被称为二叉排序树或二叉查找树。

什么是二叉搜索树

二叉搜索树首先必须是一棵二叉树，同时需满足以下特定属性：

  • 对于任意非空节点，其左子树上所有节点的值均小于该节点的值；
  • 对于任意非空节点，其右子树上所有节点的值均大于该节点的值；
  • 树的每一颗子树都必须满足上述条件。

具体结构如下图所示：

前言

以上图示展示了一棵标准的二叉搜索树。以根节点为例，其值为 71，左子树包含节点 22、35、46、53 和 66，这些值均小于 71；右子树包含节点 78、87 和 98，这些值均大于 71。依此类推，整棵树符合二叉搜索树的定义。

基于二叉搜索树的上述特性，我们可以得出以下结论：

  • 二叉搜索树中任意节点的左子树和右子树本身也是一棵二叉搜索树；
  • 整棵树中最小的节点位于最左下角的叶子节点；
  • 整棵树中最大的节点位于最右下角的叶子节点。

构建一颗二叉搜索树

接下来，我们将使用 JavaScript 来构建一棵二叉搜索树。由于二叉搜索树由节点组成，我们需要通过 class 来定义一个节点类。

示例代码如下：

class BinarySearchTree {
  constructor() {
    // 初始化根节点
    this.root = null
  }

  // 创建一个节点
  Node(val) {
    return {
      left: null, // 左子树
      right: null, // 右子树
      parent: null, // 父节点
      val,
    }
  }
}

在上述代码中，每个节点包含四个部分：指向左子树的指针、指向右子树的指针、指向父节点的指针以及存储当前值的字段。

二叉搜索树的操作

关于二叉树的遍历操作，我们在之前的文章中已有介绍，此处不再赘述。本文将重点介绍以下核心操作：

  • 插入操作
  • 查找操作
  • 删除操作

向二叉搜索树中插入数据

向二叉搜索树插入数据的实现思路如下：

  • 判断 root 是否为空，如果为空则创建 root；
  • 如果 root 非空，则需要判断插入节点的 val 比根节点的 val 是大还是小；
  • 如果比根节点小，说明该节点属于左子树；
  • 如果比根节点大，说明该节点属于右子树；
  • 重复上述两步，直到找到一个位置：若该点小于待插入值且不存在右子树，则将其作为右叶子节点；若该点大于待插入值且不存在左子树，则将其作为左叶子节点。

示例代码如下：

// 创建要给插入节点的方法
insertNode(val) {
  const that = this
  // 允许接受一个数组，批量插入
  if (Object.prototype.toString.call(val) === '[object Array]') {
    val.forEach(function (v) {
      that.insertNode(v)
    })
    return
  }
  if (typeof val !== 'number') throw Error('插入的值不是一个数字')
  const newNode = this.Node(val)
  if (this.root) {
    // 根节点非空
    this.#insertNode(this.root, newNode)
  } else {
    // 根节点是空的，直接创建
    this.root = newNode
  }
}
// 私有方法，插入节点
#insertNode(root, newNode) {
  if (newNode.val < root.val) {
    // 新节点比根节点小，左子树
    if (root.left === null) {
      // 如果左子树上没有内容，则直接插入，如果有，寻找下一个插入位置
      root.left = newNode
      root.left.parent = root
    } else {
      this.#insertNode(root.left, newNode)
    }
  } else {
    // 新节点比根节点大，右子树
    if (root.right === null) {
      // 如果右子树上没有内容，则直接插入，如果有，寻找下一个插入位置
      root.right = newNode
      root.right.parent = root
    } else {
      this.#insertNode(root.right, newNode)
    }
  }
}

在类中定义了 insertNode 方法，该方法接受数值或数值类型的数组，并将其插入二叉搜索树中。插入方法内部定义了一个私有的 #insertNode 方法，专门用于处理节点的插入逻辑。

为了验证效果，我们定义了一个静态方法，用于中序遍历（因为中序遍历的顺序是左根右，在二叉搜索树中使用中序遍历，最终结果将是从小到大依次排序的数组），并返回该数组。

示例代码如下：

// 中序遍历这个树
static inorder(root) {
  if (!root) return
  const result = []
  const stack = []
  // 定义一个指针
  let p = root
  // 如果栈中有数据或者p不是null，则继续遍历
  while (stack.length || p) {
    // 如果p存在则一致将p入栈并移动指针
    while (p) {
      // 将 p 入栈，并以移动指针
      stack.push(p)
      p = p.left
    }
    const node = stack.pop()
    result.push(node.val)
    p = node.right
  }
  return result
}

测试代码如下：

const tree = new BinarySearchTree() tree.insertNode([71, 35, 87, 22, 53, 46, 66, 78, 98]) const arr = BinarySearchTree.inorder(tree.root) console.log(arr) // [ 22, 35, 46, 53, 66,71, 78, 87, 98 ]

最终的树结构如下：

前言

查找二叉搜索树中的数据

现在我们封装一个 find 方法，用于在二叉搜索树中查找特定数据。假设我们要查找值为 66 的节点，利用上述构建的树进行查找。

其查找思路如下图所示：

前言

递归方式实现如下：

/**
 * 根据 val 查找节点
 * @param {number} val 需要查找的数值
 * @returns 如果找到返回当前节点的引用，如果未找到返回 undefined
 */
find(val) {
  if (typeof val !== 'number') throw Error('插入的值不是一个数字')
  function r(node, val) {
    // console.log(node)
    if (!node) return
    if (node.val < val) {
      return r(node.right, val)
    } else if (node.val > val) {
      return r(node.left, val)
    } else {
      return node
    }
  }
  return r(this.root, val)
}

迭代方式实现如下：

/**
 * 根据 val 查找节点
 * @param {number} val 需要查找的数值
 * @returns 如果找到返回当前节点的引用，如果未找到返回 undefined
 */
find(val) {
  if (typeof val !== 'number') throw Error('插入的值不是一个数字')
  let node = this.root
  while (node) {
    if (node.val < val) {
      // 进入右子树
      node = node.right
    } else if (node.val > val) {
      // 进入左子树
      node = node.left
    } else {
      return node
    }
  }
  return
}

相比之下，使用迭代的方式通常更优，因为它避免了递归调用栈的开销。

删除二叉搜索树的某个节点

前驱后继节点

在开始删除二叉搜索树中的节点之前，我们需要先了解什么是前驱节点和后继节点。

  • 前驱节点是指在中序遍历当前二叉搜索树时，当前节点的前一个节点。换句话说，在二叉搜索树中，当前节点左子树的最大值即为该节点的前驱节点；
  • 后继节点是指在中序遍历当前二叉搜索树时，当前节点的下一个节点。换句话说，在二叉搜索树中，当前节点右子树的最小值即为该节点的后继节点；

具体示意如下图所示：

前言

了解了前驱和后继节点的概念后，我们现在开始探讨如何删除节点。

删除一个节点的三种情况

当删除的节点是叶子节点时，只需将指向它的指针修改为 null 即可，具体如下图所示：

前言

当需要删除的节点存在一个子节点时，需要将要删除节点的子节点的 parent 指针指向要删除节点的父节点，然后将当前要删除节点的父节点指向子节点即可。

具体如下图所示：

前言

当需要删除的节点存在两个子节点时，删除步骤如下：

  • 找到当前节点的前驱或者后继节点，这里选择后继；
  • 然后将后继节点的值赋值给当前节点；
  • 删除后继节点。

具体如下图所示：

前言

现在我们已经分析了所有情况，接下来通过代码来实现。

实现代码

实现代码如下：

remove(val) {
  // 1. 删除节点
  const cur = this.find(val)
  if (!val) return false // 未找到需要删除的节点
  if (!cur.left && !cur.right) {
    // 1. 当前节点是叶子节点的情况
    this.#removeLeaf(cur)
  } else if (cur.left && cur.right) {
    // 2. 当前节点存在两个子节点
    // 2.1 找到当前节点的后继节点
    const successorNode = this.#minNode(cur.right)
    // 2.2 将后继节点的值赋值给当前值
    cur.val = successorNode.val
    if (!successorNode.left && !successorNode.right) {
      // 2.3 后继节点是叶子节点，直接删除
      this.#removeLeaf(successorNode)
    } else {
      // 2.4 后继节点不是叶子节点
      // 2.4.1记录该节点的子节点，
      let child =
        successorNode.left !== null ? successorNode.left : successorNode.right
      // 2.4.2 记录该节点的父节点
      let parent = successorNode.parent
      // 2.4.3 如果当前父节点的left是后继结点，则把后继结点的父节点的left指向后继结点的子节点
      if (parent.left === successorNode) {
        parent.left = child
      } else {
        // 2.4.4 如果不是，则让父节点的right指向后继结点的子节点
        parent.right = child
      }
      // 2.4.5 修改子节点的parent指针
      child.parent = parent
    }

    // 2.3 删除后继节点
  } else {
    // 记录当前节点的是否是父节点的左子树
    const isLeft = cur.val < cur.parent.val
    // 3. 仅存在一个子节点
    if (cur.left) {
      // 3.1 当前节点存在左子树
      cur.parent[isLeft ? 'left' : 'right'] = cur.left
      cur.left.parent = cur.parent
    } else if (cur.right) {
      // 3.2 当前节点存在右子树
      cur.parent[isLeft ? 'left' : 'right'] = cur.right
      cur.right.parent = cur.parent
    }
  }
}
// 删除叶子节点
#removeLeaf(node) {
  if (!node) return
  const parent = node.parent
  if (node.val < parent.val) {
    // 当前要删除的叶子节点是左节点
    parent.left = null
  } else {
    // 当前要删除的叶子节点是右节点
    parent.right = null
  }
}
// 查找最小值
#minNode(node) {
  if (!node) return
  if (!node.left) return node
  let p = node.left
  while (p.left) {
    p = p.left
  }
  return p
}

完整代码

本篇文章中的完整代码如下：

class BinarySearchTree {
  constructor() {
    // 初始化根节点
    this.root = null
  }

  // 创建一个节点
  Node(val) {
    return {
      left: null, // 左子树
      right: null, // 右子树
      parent: null, // 父节点
      val,
    }
  }
  /**
   * 创建要给插入节点的方法
   * @param {number | array[number]} val
   * @returns
   */
  insertNode(val) {
    const that = this
    // 允许接受一个数组，批量插入
    if (Object.prototype.toString.call(val) === '[object Array]') {
      val.forEach(function (v) {
        that.insertNode(v)
      })
      return
    }

    if (typeof val !== 'number') throw Error('插入的值不是一个数字')

    const newNode = this.Node(val)
    if (this.root) {
      // 根节点非空
      this.#insertNode(this.root, newNode)
    } else {
      // 根节点是空的，直接创建
      this.root = newNode
    }
  }

  /**
   * 私有方法，插入节点
   * @param {Object{Node}} root
   * @param {Object{Node}} newNode
   */
  #insertNode(root, newNode) {
    if (newNode.val < root.val) {
      // 新节点比根节点小，左子树
      if (root.left === null) {
        // 如果左子树上没有内容，则直接插入，如果有，寻找下一个插入位置
        root.left = newNode
        root.left.parent = root
      } else {
        this.#insertNode(root.left, newNode)
      }
    } else {
      // 新节点比根节点大，右子树
      if (root.right === null) {
        root.right = newNode
        root.right.parent = root
      } else {
        this.#insertNode(root.right, newNode)
      }
    }
  }
  /**
   * 根据 val 查找节点
   * @param {number} val 需要查找的数值
   * @returns 如果找到返回当前节点的引用，如果未找到返回 undefined
   */
  find(val) {
    if (typeof val !== 'number') throw Error('插入的值不是一个数字')
    let node = this.root
    while (node) {
      if (node.val < val) {
        // 进入右子树
        node = node.right
      } else if (node.val > val) {
        // 进入左子树
        node = node.left
      } else {
        return node
      }
    }
    return
  }
  // /**
  //  * 根据 val 查找节点 递归版
  //  * @param {number} val 需要查找的数值
  //  * @returns 如果找到返回当前节点的引用，如果未找到返回 undefined
  //  */
  // find(val) {
  //   if (typeof val !== 'number') throw Error('插入的值不是一个数字')
  //   function r(node, val) {
  //     // console.log(node)
  //     if (!node) return
  //     if (node.val < val) {
  //       return r(node.right, val)
  //     } else if (node.val > val) {
  //       return r(node.left, val)
  //     } else {
  //       return node
  //     }
  //   }
  //   return r(this.root, val)
  // }
  remove(val) {
    // 1. 删除节点
    const cur = this.find(val)
    if (!val) return false // 未找到需要删除的节点

    if (!cur.left && !cur.right) {
      // 1. 当前节点是叶子节点的情况
      this.#removeLeaf(cur)
    } else if (cur.left && cur.right) {
      // 2. 当前节点存在两个子节点
      // 2.1 找到当前节点的后继节点
      const successorNode = this.#minNode(cur.right)
      // 2.2 将后继节点的值赋值给当前值
      cur.val = successorNode.val
      if (!successorNode.left && !successorNode.right) {
        // 2.3 后继节点是叶子节点，直接删除
        this.#removeLeaf(successorNode)
      } else {
        // 2.4 后继节点不是叶子节点
        // 2.4.1记录该节点的子节点，
        let child =
          successorNode.left !== null ? successorNode.left : successorNode.right
        // 2.4.2 记录该节点的父节点
        let parent = successorNode.parent
        // 2.4.3 如果当前父节点的left是后继结点，则把后继结点的父节点的left指向后继结点的子节点
        if (parent.left === successorNode) {
          parent.left = child
        } else {
          // 2.4.4 如果不是，则让父节点的right指向后继结点的子节点
          parent.right = child
        }
        // 2.4.5 修改子节点的parent指针
        child.parent = parent
      }

      // 2.3 删除后继节点
    } else {
      // 记录当前节点的是否是父节点的左子树
      const isLeft = cur.val < cur.parent.val
      // 3. 仅存在一个子节点
      if (cur.left) {
        // 3.1 当前节点存在左子树
        cur.parent[isLeft ? 'left' : 'right'] = cur.left
        cur.left.parent = cur.parent
      } else if (cur.right) {
        // 3.2 当前节点存在右子树
        cur.parent[isLeft ? 'left' : 'right'] = cur.right
        cur.right.parent = cur.parent
      }
    }
  }
  // 删除叶子节点
  #removeLeaf(node) {
    if (!node) return
    const parent = node.parent
    if (node.val < parent.val) {
      // 当前要删除的叶子节点是左节点
      parent.left = null
    } else {
      // 当前要删除的叶子节点是右节点
      parent.right = null
    }
  }
  // 查找最小值
  #minNode(node) {
    if (!node) return
    if (!node.left) return node
    let p = node.left
    while (p.left) {
      p = p.left
    }
    return p
  }
  // 中序遍历这个树
  static inorder(root) {
    if (!root) return
    const result = []
    const stack = []
    // 定义一个指针
    let p = root
    // 如果栈中有数据或者p不是null，则继续遍历
    while (stack.length || p) {
      // 如果p存在则一致将p入栈并移动指针
      while (p) {
        // 将 p 入栈，并以移动指针
        stack.push(p)
        p = p.left
      }

      const node = stack.pop()
      result.push(node.val)
      p = node.right
    }
    return result
  }
}
const tree = new BinarySearchTree()
tree.insertNode([71, 35, 84, 22, 53, 46, 66, 81, 83, 82, 88, 98])
console.log(BinarySearchTree.inorder(tree.root)) // [ 22, 35, 46, 53, 66, 71, 81, 82, 83, 84, 88, 98 ]
tree.remove(71
console.log(BinarySearchTree.inorder(tree.root)) // [ 22, 35, 46, 53, 66, 81, 82, 83, 84, 88, 98 ]

总结

本文介绍了二叉搜索树的性质，以及二叉搜索树的构建、查找和删除操作。

到此这篇关于 JavaScript 二叉搜索树构建操作详解的文章就介绍到这了，更多相关 JS 二叉搜索树内容请搜索本站以前的文章或继续浏览下面的相关文章，希望大家以后多多支持本站！

实用工具推荐

电子包浆

绿化、压缩、噪点和虚拟水印，自由调节做旧程度。

使用 ›
图片压缩

选择画质和输出格式，预览压缩前后的大小。

使用 ›
作者最新文章

JS读取本地文件时报错或无响应的常见原因

let、const与var的区别：JavaScript变量声明最佳实践

JS中直接定义静态二维数组的字面量写法

JS 怎么查找字符串中所有匹配项的位置

JavaScript新手常犯的编码错误与最佳实践指南

相关文章
热门文章
更多
CSS text-transform与JS修改首字母大写的适用场景区别
JS中constructor属性判断数组存在哪些风险
JS正则替换中$1捕获组引用与字符串重组技巧
全栈开发中JavaScript与Java怎么协作？前后端技术栈配合解析
Node.js后端生成高强度随机字符串的方法
怎么在本地运行JavaScript脚本：Node.js下载安装与环境配置教程
JS正则表达式基础：字面量与RegExp构造函数的区别及常用元字符
JS 解压出现乱码或报错怎么解决？
JavaScript常见SyntaxError语法错误排查与修复方法
JS动态构建复杂嵌套JSON对象的方法