1. 先区分处理顺序
深度优先是 DFS / Depth First Search,广度优先是 BFS / Breadth First Search。前者先沿一个分支深入,后者按离起点的边数分层。旧文曾将英文名称颠倒,并在递归时重复传入当前节点;本篇改用可独立测试的普通树对象。
输入为有限、无环且无共享节点的多叉树,节点有 value 和数组 children,空树为 null。这同样适用于菜单树;真实 DOM 有不同字段和实时集合,使用前须明确转换与遍历期间是否允许修改。
2. 显式栈的深度优先
栈后进先出。若希望孩子从左到右访问,就按从右到左的顺序入栈。
js
function depthFirst(root) {
if (root === null) return [];
const stack = [root];
const result = [];
while (stack.length) {
const node = stack.pop();
result.push(node.value);
for (let i = node.children.length - 1; i >= 0; i--) stack.push(node.children[i]);
}
return result;
}时间为 O(n),输出为 O(n);显式栈最多可能存多个尚未展开的兄弟,在一般多叉树上辅助空间最坏为 O(n),不要一概写成树高。
3. 队列的广度优先
js
function breadthFirst(root) {
if (root === null) return [];
const queue = [root];
const result = [];
for (let head = 0; head < queue.length; head++) {
const node = queue[head];
result.push(node.value);
for (const child of node.children) queue.push(child);
}
return result;
}时间为 O(n),本数组队列保留全部已读引用,辅助空间为 O(n),输出也为 O(n)。两者不修改输入。
4. 从树走向图
树中每个节点只有一个父节点,合法输入无需防止从另一条边再次到达。图可能有环和多条路径,必须维护访问标记。广度优先通常在入队时标记,避免同一顶点被不同父节点反复加入。
| 任务 | 优先考虑 | 理由 |
|---|---|---|
| 子树汇总、回溯路径 | 深度优先 | 便于沿分支维护状态和返回 |
| 无权最短步数、逐层处理 | 广度优先 | 第一次到达对应最少边数 |
| 带权最短路 | 根据权重选算法 | 普通广度优先不比较总权重 |
5. 手推与验收
根 A 的孩子为 B、C,B 的孩子为 D:深度顺序为 A B D C,广度顺序为 A B C D。自己在每一步写出栈或队列内容;检查空树、长链和多个孩子。
sh
node --test tests/algorithm-tree-graph-examples.test.mjs
评论
正在加载评论…