Skip to content

二叉搜索树

中等 约 40 分钟

你将构建什么

一个 BinarySearchTree 类,左子节点更小、右子节点更大,支持 insert、search 和中序遍历(输出有序结果)。

学习目标

  • 将树节点建模为含 left 和 right 子节点的对象
  • 插入值时保持 BST 性质
  • 利用分治性质进行搜索
  • 中序遍历产生有序输出

前置要求

  • 递归(基线情况 + 递归调用)
  • 对象与属性访问
  • 比较运算符

步骤

  1. 1

    定义节点与树

    BST 节点持有值和 left/right 子指针。树本身以 null root 起始。

    代码
    class TreeNode {
      constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
      }
    }
    
    class BinarySearchTree {
      constructor() { this.root = null; }
    }

    预期结果

    一个空 BST,root === null。

  2. 2

    递归实现 insert

    插入时将值与当前节点比较:更小走左,更大走右。到达 null 时放置新节点。编写递归辅助函数。

    代码
    insert(value) {
      const node = new TreeNode(value);
      if (!this.root) { this.root = node; return this; }
      const recurse = (current) => {
        if (value < current.value) {
          if (!current.left) current.left = node;
          else recurse(current.left);
        } else {
          if (!current.right) current.right = node;
          else recurse(current.right);
        }
      };
      recurse(this.root);
      return this;
    }

    预期结果

    insert(5).insert(3).insert(7) 构建出 5 为根、3 左、7 右的树。

  3. 3

    实现 search

    搜索使用相同比较逻辑:在每个节点处,目标更小走左,更大走右,相等返回 true,到达 null 返回 false。

  4. 4

    实现中序遍历

    中序遍历依次访问左子树、节点、右子树。对 BST 而言这会产出有序值。用递归实现。

  5. 5

    测试 BST

    插入若干值,搜索存在和不存在的值,确认中序遍历给出有序输出。

    代码
    const bst = new BinarySearchTree();
    [5, 3, 7, 1, 4, 6, 8].forEach(v => bst.insert(v));
    console.log(bst.search(4)); // true
    console.log(bst.search(9)); // false
    console.log(bst.inOrder()); // [1, 3, 4, 5, 6, 7, 8]

    预期结果

    search(4) 返回 true,search(9) 返回 false,inOrder 返回有序数组。

自己动手试试

你学到了什么

你构建了一棵树并用递归维持其有序不变量——BST 是数据库索引、set/map 实现及许多分治算法的基础。

相关资源

相关课程

  • 递归

    插入、搜索和遍历都是递归的。

  • 对象

    每个节点都是含值和子节点的对象。

查阅不认识的术语

新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。

查看术语表

解读错误信息

用大白话解释常见错误——什么意思、为什么发生、如何修复。

查看错误

← 返回主题