Skip to content

树和图深入

探索二叉树、二叉搜索树、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 使用队列在深入前访问当前层的所有邻居。

动手试一试

常见错误

错误写法

向不平衡 BST 插入有序数据。

正确做法

有序插入创建退化(类似链表)的树,操作为 O(n)。使用自平衡树。

错误写法

对加权最短路径使用 BFS。

正确做法

BFS 仅在无权图中找最短路径。加权图使用 Dijkstra 或 Bellman-Ford。

查阅不认识的术语

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

查看术语表

动手做项目

通过引导式项目应用所学,含起始代码与解决方案。

查看项目

解读错误信息

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

查看错误