树和图深入
探索二叉树、二叉搜索树、AVL 树、图表示和遍历算法。
你将学到
- 二叉树、二叉搜索树和平衡变体(AVL、红黑树)
- 图表示:邻接表与邻接矩阵
- DFS 和 BFS 遍历模式
- 树和图的应用
概念讲解
树和图深入
树是具有根和分支的层次结构;图推广树以允许环和多重连接。两者都是建模关系的基础。
二叉树和二叉搜索树
二叉树每个节点最多两个子节点。二叉搜索树(BST)维护不变量:左子树值 < 节点 < 右子树值。平衡时给出 O(log n) 搜索/插入/删除,但不平衡时退化为 O(n)。
自平衡树
AVL 树在每次插入/删除后通过旋转重新平衡,保证高度 O(log n)。红黑树使用更弱的平衡条件但允许更快插入。两者都保证 O(log n) 操作。
图表示
邻接表:对每个顶点存储邻居列表。O(V + E) 空间,稀疏图高效。邻接矩阵:V*V 布尔矩阵。O(V^2) 空间,O(1) 边查找,稠密图高效。
遍历
DFS(深度优先):先深后宽。使用栈(或递归)。适合连通性、环检测、拓扑排序。BFS(广度优先):先访问所有邻居再深入。使用队列。适合无权图最短路径、层序遍历。
对树,三种 DFS 变体——前序、中序、后序——用途不同。BST 中序遍历产生有序输出。
示例代码
class TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; } }
class BST {
constructor() { this.root = null; }
insert(val) {
const node = new TreeNode(val);
if (!this.root) { this.root = node; return; }
let curr = this.root;
while (true) {
if (val < curr.val) { if (!curr.left) { curr.left = node; return; } curr = curr.left; }
else { if (!curr.right) { curr.right = node; return; } curr = curr.right; }
}
}
inorder() { const r = []; const w = (n) => { if (!n) return; w(n.left); r.push(n.val); w(n.right); }; w(this.root); return r; }
}
function bfs(graph, start) {
const visited = new Set([start]); const queue = [start]; const order = [];
while (queue.length) { const v = queue.shift(); order.push(v); for (const u of graph[v] || []) { if (!visited.has(u)) { visited.add(u); queue.push(u); } } }
return order;
}
const bst = new BST();
[5, 3, 7, 1, 4, 6, 8].forEach(v => bst.insert(v));
console.log('Inorder (sorted):', bst.inorder());
console.log('BFS from 1:', bfs({1:[2,3],2:[4],3:[4,5],4:[],5:[]}, 1));
BST 保持左 < 节点 < 右,因此中序遍历产生有序值。BFS 使用队列在深入前访问当前层的所有邻居。
动手试一试
- JSON Formatter
JSON 是树结构——格式化它是树遍历。
常见错误
错误写法
向不平衡 BST 插入有序数据。
正确做法
有序插入创建退化(类似链表)的树,操作为 O(n)。使用自平衡树。
错误写法
对加权最短路径使用 BFS。
正确做法
BFS 仅在无权图中找最短路径。加权图使用 Dijkstra 或 Bellman-Ford。
查阅不认识的术语
新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。
动手做项目
通过引导式项目应用所学,含起始代码与解决方案。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。