javascript

手写二叉搜索树：插入、查找、删除与遍历全解析

By AI-Writer 28 min read

手写二叉搜索树：插入、查找、删除与遍历全解析

二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树，它的每个节点都满足一条核心规则：左子树的所有节点值小于当前节点，右子树的所有节点值大于当前节点。这条规则使得 BST 在查找、插入、删除操作上都能达到平均 O(log n) 的效率。

本文将带你手写完整的 BST 实现，覆盖四种遍历方式，并深入剖析最棘手的删除操作。最后，我们还会简要了解保持树平衡的 AVL 树与红黑树。

BST 的核心性质

一棵合法的 BST 必须满足以下三个条件：

  1. 左子树中所有节点的值 < 当前节点的值
  2. 右子树中所有节点的值 > 当前节点的值
  3. 左右子树本身也必须是 BST（递归定义）

为什么 BST 效率高？

BST 的查找过程类似于二分搜索：每次比较后都能排除一半的子树。理想情况下，一棵包含 n 个节点的 BST 高度约为 log₂n，因此查找、插入、删除的平均时间复杂度均为 O(log n)。

但 BST 的效率高度依赖树的形状。如果数据按顺序插入（如 1, 2, 3, 4, 5），BST 会退化成一条链表，时间复杂度降为 O(n)。这就是平衡二叉树存在的意义。

节点定义与 BST 类

js
class TreeNode {
  constructor(value) {
    this.value = value;   // 节点值
    this.left = null;     // 左子节点
    this.right = null;    // 右子节点
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;     // 根节点
    this.size = 0;        // 节点总数
  }
}

插入操作（Insert）

插入新节点时，从根节点开始比较，沿着正确的路径向下查找，直到找到合适的空位。

js
class BinarySearchTree {
  // ... constructor

  insert(value) {
    this.root = this._insertNode(this.root, value);
    this.size++;
  }

  _insertNode(node, value) {
    // 找到空位，创建新节点
    if (node === null) {
      return new TreeNode(value);
    }

    // 值小于当前节点，插入左子树
    if (value < node.value) {
      node.left = this._insertNode(node.left, value);
    }
    // 值大于当前节点，插入右子树
    else if (value > node.value) {
      node.right = this._insertNode(node.right, value);
    }
    // 值相等，不做处理（或根据业务更新）

    return node;
  }
}

递归的妙处在于：每一层递归都在回答同一个问题——“给定一个子树和值，返回插入后的子树根节点”。基准情况是遇到 null，直接创建新节点。

查找操作（Search）

js
class BinarySearchTree {
  // ... insert

  search(value) {
    return this._searchNode(this.root, value);
  }

  _searchNode(node, value) {
    // 没找到
    if (node === null) {
      return false;
    }

    // 找到了
    if (value === node.value) {
      return true;
    }

    // 在左子树中查找
    if (value < node.value) {
      return this._searchNode(node.left, value);
    }

    // 在右子树中查找
    return this._searchNode(node.right, value);
  }

  // 查找最小值（一直向左走）
  findMin() {
    if (!this.root) return undefined;

    let current = this.root;
    while (current.left) {
      current = current.left;
    }
    return current.value;
  }

  // 查找最大值（一直向右走）
  findMax() {
    if (!this.root) return undefined;

    let current = this.root;
    while (current.right) {
      current = current.right;
    }
    return current.value;
  }
}

遍历操作（Traversal）

遍历是指按照某种顺序访问树中的每一个节点。BST 有四种经典遍历方式。

1. 中序遍历（In-Order）：左 → 根 → 右

中序遍历 BST 的结果是一个升序数组。这是 BST 最重要的性质之一。

js
// 递归实现
inOrderTraversal(callback) {
  this._inOrder(this.root, callback);
}

_inOrder(node, callback) {
  if (node !== null) {
    this._inOrder(node.left, callback);   // 遍历左子树
    callback(node.value);                  // 访问根节点
    this._inOrder(node.right, callback);  // 遍历右子树
  }
}
js
// 非递归实现（使用栈）
inOrderTraversalIterative(callback) {
  const stack = [];
  let current = this.root;

  while (current !== null || stack.length > 0) {
    // 一路向左，将节点压入栈
    while (current !== null) {
      stack.push(current);
      current = current.left;
    }

    // 弹出栈顶，访问它
    current = stack.pop();
    callback(current.value);

    // 转向右子树
    current = current.right;
  }
}

2. 前序遍历（Pre-Order）：根 → 左 → 右

前序遍历先访问根节点，再访问子树。常用于复制树结构或序列化。

js
preOrderTraversal(callback) {
  this._preOrder(this.root, callback);
}

_preOrder(node, callback) {
  if (node !== null) {
    callback(node.value);                   // 访问根节点
    this._preOrder(node.left, callback);   // 遍历左子树
    this._preOrder(node.right, callback);  // 遍历右子树
  }
}

3. 后序遍历（Post-Order）：左 → 右 → 根

后序遍历先访问子树，最后访问根。常用于释放树内存（确保子节点先于父节点被释放）或计算目录大小。

js
postOrderTraversal(callback) {
  this._postOrder(this.root, callback);
}

_postOrder(node, callback) {
  if (node !== null) {
    this._postOrder(node.left, callback);   // 遍历左子树
    this._postOrder(node.right, callback);  // 遍历右子树
    callback(node.value);                    // 访问根节点
  }
}

4. 层序遍历（Level-Order）：按层级从上到下

层序遍历按树的层级逐层访问，需要借助队列实现。

js
levelOrderTraversal(callback) {
  if (!this.root) return;

  const queue = [this.root];

  while (queue.length > 0) {
    const node = queue.shift();
    callback(node.value);

    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
}

遍历方式对比

js
const bst = new BinarySearchTree();
[50, 30, 70, 20, 40, 60, 80].forEach(v => bst.insert(v));

//       50
//      /  \
//    30    70
//   / \    / \
// 20  40 60  80

const result = [];
const collect = v => result.push(v);

bst.preOrderTraversal(collect);
console.log('前序:', result); // [50, 30, 20, 40, 70, 60, 80]

result.length = 0;
bst.inOrderTraversal(collect);
console.log('中序:', result); // [20, 30, 40, 50, 60, 70, 80]

result.length = 0;
bst.postOrderTraversal(collect);
console.log('后序:', result); // [20, 40, 30, 60, 80, 70, 50]

result.length = 0;
bst.levelOrderTraversal(collect);
console.log('层序:', result); // [50, 30, 70, 20, 40, 60, 80]

删除操作（Delete）

删除是 BST 最复杂的操作，需要根据被删除节点的子节点数量分三种情况处理。

三种情况

情况描述处理方式
叶子节点没有子节点直接删除
只有一个子节点只有左或右子节点用子节点替代自己
有两个子节点左右子节点都存在用后继节点（右子树最小值）替代自己
js
class BinarySearchTree {
  // ... 前面的方法

  delete(value) {
    if (!this.search(value)) return; // 节点不存在，不操作
    this.root = this._deleteNode(this.root, value);
    this.size--;
  }

  _deleteNode(node, value) {
    if (node === null) {
      return null; // 没找到
    }

    // 在左子树中查找
    if (value < node.value) {
      node.left = this._deleteNode(node.left, value);
      return node;
    }

    // 在右子树中查找
    if (value > node.value) {
      node.right = this._deleteNode(node.right, value);
      return node;
    }

    // 找到要删除的节点

    // 情况 1：叶子节点
    if (node.left === null && node.right === null) {
      return null;
    }

    // 情况 2：只有一个子节点
    if (node.left === null) {
      return node.right;
    }
    if (node.right === null) {
      return node.left;
    }

    // 情况 3：有两个子节点
    // 找到右子树中的最小值（后继节点）
    const successor = this._findMin(node.right);
    node.value = successor.value;

    // 删除后继节点
    node.right = this._deleteNode(node.right, successor.value);
    return node;
  }

  _findMin(node) {
    while (node.left !== null) {
      node = node.left;
    }
    return node;
  }
}

删除两个子节点的图解

plaintext
删除 50：

      50           60           60
     /  \    →    /  \    →    /  \
   30    70      30    70     30    70
  / \    / \     / \    / \    / \    \
20  40 60  80   20  40  X  80  20  40   80

步骤 1：找到右子树的最小值 60
步骤 2：用 60 替代 50 的值
步骤 3：在右子树中删除原来的 60

平衡二叉树：AVL 树与红黑树

普通 BST 在极端情况下会退化为链表。平衡二叉树通过旋转操作自动维持树的平衡，保证操作始终为 O(log n)。

AVL 树

AVL 树是最严格的平衡二叉树，要求任意节点的左右子树高度差不超过 1。当插入或删除破坏平衡时，通过旋转恢复：

失衡情况旋转方式
左-左（LL）右旋
右-右（RR）左旋
左-右（LR）先左旋再右旋
右-左（RL）先右旋再左旋
js
// 右旋示意
//     y            x
//    / \    →     / \
//   x   C        A   y
//  / \              / \
// A   B            B   C

function rotateRight(y) {
  const x = y.left;
  const B = x.right;

  x.right = y;
  y.left = B;

  return x; // 新的子树根节点
}

AVL 树查找效率最高，但插入和删除时的旋转操作较多，适合读多写少的场景。

红黑树

红黑树是一种弱平衡的二叉搜索树，通过五条颜色规则保证最长路径不超过最短路径的两倍：

  1. 节点是红色或黑色
  2. 根节点是黑色
  3. 所有叶子（NIL）是黑色
  4. 红色节点的子节点必须是黑色（无连续红节点）
  5. 从任一节点到其每个叶子的路径包含相同数量的黑色节点

红黑树的旋转次数比 AVL 树少，插入和删除效率更高，适合读写均衡的场景。JavaScript 引擎的 Map 和 Set 底层就是用类似红黑树的结构实现的。

完整测试

js
const bst = new BinarySearchTree();

// 构建树
[50, 30, 70, 20, 40, 60, 80, 10, 25].forEach(v => bst.insert(v));

console.log('树大小:', bst.size);           // 9
console.log('最小值:', bst.findMin());      // 10
console.log('最大值:', bst.findMax());      // 80
console.log('查找 40:', bst.search(40));    // true
console.log('查找 100:', bst.search(100));  // false

// 中序遍历（升序）
const sorted = [];
bst.inOrderTraversal(v => sorted.push(v));
console.log('升序排列:', sorted); // [10, 20, 25, 30, 40, 50, 60, 70, 80]

// 删除叶子节点
bst.delete(10);
console.log('删除 10 后查找:', bst.search(10)); // false

// 删除有两个子节点的节点
bst.delete(30);
console.log('删除 30 后查找:', bst.search(30)); // false

// 验证中序仍有序
sorted.length = 0;
bst.inOrderTraversal(v => sorted.push(v));
console.log('删除后升序:', sorted); // [20, 25, 40, 50, 60, 70, 80]

总结

操作平均时间复杂度最坏时间复杂度
插入O(log n)O(n)
查找O(log n)O(n)
删除O(log n)O(n)
遍历O(n)O(n)

BST 是理解更复杂树结构的基础。掌握 BST 后，你可以继续学习：

  • AVL 树和红黑树：自平衡 BST
  • B 树和B+ 树：数据库索引的核心
  • 线段树和树状数组：区间查询与修改
  • Trie（前缀树）：字符串高效存储与检索

树的递归思维模式（“解决根节点，递归解决子树”）也是许多算法题的核心解法。

#javascript #data-structure #algorithm #tree #bst

评论

A

Written by

AI-Writer

Related Articles

javascript
#7

Promise 与 async/await

深入理解 JavaScript 异步编程核心——Promise 状态机、组合 API 与 async/await 语法糖，掌握错误处理与事件循环的协作关系。

Read More
javascript
#18

迭代器与生成器

深入可迭代协议与迭代器协议，掌握生成器函数（function*）、yield 表达式与异步生成器，手写自定义可迭代对象。

Read More
Back to All Articles