JavaScript 二叉查找树（BST）实现详解：从节点定义到增删改查

作者：函数茶馆时间：2026-10-23 10:17:14浏览：344

本文详细介绍 JavaScript 中二叉查找树（BST）的实现原理与代码。涵盖节点定义、插入逻辑、前中后序遍历算法，以及查找最值与复杂节点删除操作的完整实现，帮助开发者掌握非线性数据结构的核心应用。

本文通过具体实例，详细解析 JavaScript 中二叉查找树（Binary Sort Tree）的原理与实现，供读者参考学习。

二叉查找树（Binary Sort Tree）

此前我们学习了列表、栈等线性数据结构，本文将介绍计算机中常用的非线性数据结构——树（Tree）。由于树中的元素具有明显的层次特性，它常用于存储具有层级关系的数据（如文件系统）或有序列表。

在树结构中，每个节点仅有一个前件，称为父结点；没有前件的节点唯一，即树的根结点（root）。每个节点可拥有多个后件，称为子结点；没有后件的节点称为叶子结点。节点拥有的子节点数量称为该节点的度，所有节点中最大的度称为树的度。树的最大层次数称为树的深度。

二叉树

二叉树是一种特殊的树，其子节点数量不超过两个，分别称为左子树（left subtree）和右子树（right subtree）。二叉树常用于构建二叉查找树、二叉堆或二叉排序树（BST）。

二叉查找树（Binary Sort Tree）二叉树

按特定规则和顺序访问二叉树的所有节点，使每个节点仅被访问一次，该操作称为树的遍历，是树最基本的运算。由于二叉树是非线性结构，遍历实质是将节点转换为线性序列表示。

根据根节点的访问顺序，树的遍历分为三种：前序遍历、中序遍历和后序遍历。

前序遍历顺序：根节点 -> 左子树 -> 右子树

二叉查找树（Binary Sort Tree）先序遍历

中序遍历顺序：左子树 -> 根节点 -> 右子树

二叉查找树（Binary Sort Tree）中序遍历

后序遍历顺序：左子树 -> 右子树 -> 根节点

二叉查找树（Binary Sort Tree）后序遍历

基于上述二叉树，其遍历结果如下：前序遍历为 ABDEFGC，中序遍历为 DEBGFAC，后序遍历为 EDGFBCA。

二叉查找树（BST）

在实际应用中，树的每个节点通常关联一个值（键）。构建二叉查找树时，确定子节点位置至关重要：通常将较小的值保存在左节点，较大的值保存在右节点。这种结构使得查找效率极高，因此被广泛应用。

二叉查找树的实现

基于前述知识，二叉树由多个节点组成。首先需定义 Node 类以存放节点，其构造与链表类似。Node 类的定义如下：


//节点定义

function Node (data , left , right) {
  this.data = data;    // 数据
  this.left = left;    // 左节点
  this.right = right;   // 右节点
  this.show = show;    // 显示节点数据
}

function show(){
  return this.data;
}

Node 对象既保存数据，也保存指向左节点和右节点的链接。其中 show 方法用于显示当前节点中保存的数据。

接下来创建表示二叉查找树（BST）的类。初始化时，该类仅包含一个成员：表示 BST 根节点的 Node 对象，初始化为 null，表示创建一个空树。


//二叉查找树（BST）的类

function BST(){
  this.root = null;      // 根节点
  this.insert = insert;    // 插入节点
  this.preOrder = preOrder;  // 先序遍历
  this.inOrder = inOrder;   // 中序遍历
  this.postOrder = postOrder; // 后序遍历
  this.find = find;      // 查找节点
  this.getMin = getMin;    // 查找最小值
  this.getMax = getMax;    // 查找最大值
  this.remove = remove;    // 删除节点
}

随后，我们需要为该类添加具体方法。

首先是 insert 方法，用于向树中添加新节点。让我们详细分析该方法；

insert：向树中添加新节点

添加节点涉及插入位置的选择，必须将其置于正确位置以保证树的正确性，过程较为复杂。我们梳理如下：

首先创建新节点，需创建一个 Node 对象并将数据传入。

其次检查当前 BST 是否有根节点。若无，则该节点即为新树的根节点，插入结束；否则，继续下一步。

若待插入节点非根节点，则必须遍历 BST 以找到合适位置。该过程类似遍历链表，使用变量存储当前节点，逐层遍历 BST，算法如下：

将当前节点设为根节点
若待插入节点的数据小于当前节点，则新节点为原节点的左节点；否则，执行第 4 步
若当前节点的左节点为 null，则将新节点置于该位置，退出循环；否则，继续下一次循环
设置新节点为原节点的右节点
若当前节点的右节点为 null，则将新节点置于该位置，退出循环；否则，继续下一次循环

如此可保证每次添加的新节点均置于正确位置，具体实现如下；


//插入新节点

function insert(data) {
  var n = new Node( data , null , null );
  if( this.root == null ){
    this.root = n;
  }else{
    var current = this.root;
    var parent;
    while( true ){
      parent = current;
      if( data < current.data ){
        current = current.left;
        if( current == null ){
          parent.left = n ;
          break;
        }
      }else{
        current = current.right;
        if( current == null ){
          parent.right = n;
          break;
        }
      }
    }
  }
}

此时 BST 类初步成型，但仅支持插入节点。我们需要具备遍历 BST 的能力，前文已提及三种遍历方式。其中中序遍历最容易实现，需按升序访问所有节点：先访问左子树，再访问根节点，最后访问右子树，此处采用递归实现！

inOrder：中序遍历


 // 中序遍历
 
function inOrder (node) {
  if( !(node == null )){
    inOrder( node.left );
    console.debug( node.show() + ' ');
    inOrder( node.right );
  }
}

理解原理后，实现起来相对简单。

我们用一段代码测试所写中序遍历：


var nums = new BST();
//插入数据
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);

上述插入数据后，将形成如下二叉树

二叉查找树（Binary Sort Tree） BST

中序遍历结果如下：


//中序遍历
console.log("Inorder traversal: ");
inOrder(nums.root);

// Inorder traversal:
// 3 16 22 23 37 45 99

preOrder：先序遍历

有了中序遍历的基础，相信先序遍历的实现已不难想到。结果如何？验证一下；


//先序遍历

function preOrder( node ) {
  if( !(node == null )){
    console.log( node.show() + ' ');
    preOrder( node.left );
    preOrder( node.right );
  } 
}

看起来是否和中序遍历相似？唯一区别在于 if 语句中代码的执行顺序：中序遍历中 show 方法置于两个递归调用之间，而先序遍历则置于递归调用之前。

先序遍历结果如下：


// 先序遍历

console.log("Preorder traversal: ");
preOrder(nums.root);

// Preorder traversal:
// 23 16 3 22 45 37 99

postOrder：后序遍历

后序遍历的实现与前文基本相同，只需将 show 方法置于递归调用之后执行即可


//后序遍历
 
function postOrder ( node ) {
  if( !(node == null ) ){
    postOrder( node.left );
    postOrder( node.right );
    console.log( node.show() + ' ');
  }
}

后序遍历结果如下：


// 后序遍历

console.log("Postorder traversal: ");
postOrder(nums.root);

// Postorder traversal:
// 3 22 16 37 99 45 23

二叉查找树的查找运算

对于 BST，通常有以下三种查找类型：

查找给定值
查找最大值
查找最小值

接下来共同讨论三种查找方式的实现。

查找 BST 中的最小值和最大值非常简单。因为较小值总在左子节点上，查找最小值只需遍历左子树，直到找到最后一个节点。同理，查找最大值只需遍历右子树，直到找到最后一个节点。

getMin：查找最小值

遍历左子树，直到左子树的某个节点的 left 为 null 时，该节点保存的即为最小值


//查找最小值

function getMin( ) {
  var current = this.root;
  while ( !( current.left == null ) ){
    current = current.left;
  }
  return current.show();
}

getMax：查找最大值

遍历右子树，直到右子树的某个节点的 right 为 null 时，该节点保存的即为最大值


//查找最大值
 
function getMax () {
  var current = this.root;
  while ( !( current.right == null ) ) {
    current = current.right;
  }
  return current.show();
}

我们利用前文构建的树进行测试：


// 最小值
console.log('min:' + nums.getMin() );    // min : 3

//最大值
console.log('max:' + nums.getMax() );    // max : 99

在 BST 上查找给定值，需比较给定值与当前节点保存值的大小。通过比较确定给定值是否存在于当前节点，并根据 BST 特点决定向左还是向右遍历；


//查找给定值

function find ( data ) {
  var current = this.root;
  while ( current != null ){
    if( current.data == data ){
      return current;
    }else if( current.data < data ){
      current = current.right;
    }else{
      current = current.left;
    }
  }
  return null;
}

若找到给定值，该方法返回保存该值的节点；反之返回 null；


//查找不存在的值
console.log('find:' + nums.find(66));    // find : null

//查找存在的值
console.log('find:' + nums.find(99) );   // find : [object Object]

二叉查找树的删除运算

从 BST 中删除节点的操作最为复杂，其复杂程度取决于待删除节点的位置。若待删除节点无子节点，则非常简单。若删除包含左子节点或右子节点的节点，则稍显复杂。若删除包含两个子节点的节点，则最为复杂。

我们采用递归方法完成复杂的删除操作，定义 remove() 和 removeNode() 两个方法；算法思想如下：

首先判断当前节点是否包含待删除数据。若包含，则删除该节点；若不包含，则比较当前节点数据与待删除数据的大小关系。若待删除数据小于当前节点数据，则移至当前节点的左子节点继续比较；若大于，则移至当前节点的右子节点继续比较。
若待删除节点是叶子节点（无子节点），只需将父节点指向它的链接变为 null；
若待删除节点含有一个子节点，需调整原本指向它的节点，使其指向它的子节点；
最后，若待删除节点包含两个子节点，可选择查找待删除节点左子树上的最大值或右子树上的最小值，此处选择后者。

因此，我们需要一个查找树上最小值的方法，后续将用它找到最小值并创建临时节点，将临时节点上的值复制到待删除节点，再删除临时节点；

前文提及的两个方法中，remove 方法仅接收待删除数据并调用 removeNode 执行删除，主要工作在 removeNode 中完成，定义如下：


//删除操作

function remove( data ) {
  removeNode( this.root , data);
}

//查找最小值

function getSmallest(node) {
  if (node.left == null) {
    return node;
  }
  else {
    return getSmallest(node.left);
  }
}

//删除节点
function removeNode( node , data ) {
  if( node == null ) {
    return null;
  }
  if(data == node.data) {
    // 没有子节点的节点
    if(node.left == null && node.right == null) {
      return null;
    }
    // 没有左子节点的节点
    if(node.left == null) {
      return node.right;
    }
    // 没有右子节点的节点
    if(node.right == null) {
      return node.left;
    }
    // 有2个子节点的节点
    var tempNode = getSmallest(node.right);
    node.data = tempNode.data;
    node.right = removeNode(node.right,tempNode.data);
    return node;

  }else if(data < node.data) {
    node.left = removeNode( node.left,data);
    return node;
  }else {
    node.right = removeNode( node.right,data);
    return node;
  }
}

现在我们来尝试删除节点。


//删除根节点
nums.remove(23);

inOrder(nums.root);

// 3 16 22 37 45 99

操作成功！至此，我们的 BST 已完整。

目前我们已能利用 JS 实现简单的 BST。实际应用中树的使用非常广泛，希望大家多了解树的数据结构并动手实践，相信会有不少收获！

感兴趣的朋友可使用在线 HTML/CSS/JavaScript 代码运行工具：http://tools.jb51.net/code/HtmlJsRun 测试上述代码运行效果。

更多关于 JavaScript 相关内容感兴趣的读者可查看本站专题：《JavaScript 数学运算用法总结》、《JavaScript 数据结构与算法技巧总结》、《JavaScript 数组操作技巧总结》、《JavaScript 排序算法总结》、《JavaScript 遍历算法与技巧总结》、《JavaScript 查找算法技巧总结》及《JavaScript 错误与调试技巧总结》

希望本文所述对大家 JavaScript 程序设计有所帮助。

作者最新文章

JS大数值转字符串出现科学计数法怎么办

2026-11-05 17:09:21

JS split切割后出现空字符串怎么过滤

2026-11-05 16:00:30

在 React 或 Vue 项目中封装使用 JS 节流防抖

2026-11-05 15:27:29

JavaScript中怎么将带小数的字符串转为整数？

2026-11-05 14:32:38

怎么用JavaScript策略模式重构电商促销计算逻辑？

2026-11-05 14:01:09