二叉搜索树
中等 约 40 分钟
你将构建什么
一个 BinarySearchTree 类,左子节点更小、右子节点更大,支持 insert、search 和中序遍历(输出有序结果)。
学习目标
- 将树节点建模为含 left 和 right 子节点的对象
- 插入值时保持 BST 性质
- 利用分治性质进行搜索
- 中序遍历产生有序输出
前置要求
- 递归(基线情况 + 递归调用)
- 对象与属性访问
- 比较运算符
步骤
- 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
递归实现 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
实现 search
搜索使用相同比较逻辑:在每个节点处,目标更小走左,更大走右,相等返回 true,到达 null 返回 false。
提示
搜索路径最多为树高——平衡树为 O(log n)。
- 4
实现中序遍历
中序遍历依次访问左子树、节点、右子树。对 BST 而言这会产出有序值。用递归实现。
提示
基线情况是 null 节点——直接返回即可。
- 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 返回有序数组。
自己动手试试
起始代码
class TreeNode { constructor(v) { this.value = v; this.left = null; this.right = null; } }
class BinarySearchTree {
constructor() { this.root = null; }
// TODO: insert, search, inOrder
}解决方案代码
class TreeNode { constructor(v) { this.value=v; this.left=null; this.right=null; } }
class BinarySearchTree {
constructor() { this.root = null; }
insert(v) { const n = new TreeNode(v); if (!this.root) { this.root = n; return this; } const r = (c) => { if (v < c.value) { if (!c.left) c.left = n; else r(c.left); } else { if (!c.right) c.right = n; else r(c.right); } }; r(this.root); return this; }
search(v) { const r = (c) => { if (!c) return false; if (v === c.value) return true; return v < c.value ? r(c.left) : r(c.right); }; return r(this.root); }
inOrder() { const r = []; const v = (c) => { if (!c) return; v(c.left); r.push(c.value); v(c.right); }; v(this.root); return r; }
}你学到了什么
你构建了一棵树并用递归维持其有序不变量——BST 是数据库索引、set/map 实现及许多分治算法的基础。
相关资源
查阅不认识的术语
新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。