Knowledge_Repository

主题

Teeker2026-04-06
1572
6m

BFS 和 DFS 在二叉树及前端开发中的应用 ​

你在了解二叉树后，想搞清楚BFS（广度优先搜索）和DFS（深度优先搜索）的定义、核心逻辑，以及它们和二叉树遍历的关联、在前端开发中的实际应用，核心是希望用前端能理解的方式掌握这两种通用的遍历/搜索思想。

一、BFS/DFS 通俗理解（前端友好版） ​

BFS和DFS是处理层级/树/图结构数据的两种通用算法，不止用于二叉树，前端日常处理DOM、AST、组件树时都在间接使用，先通过生活化例子理解：

  • DFS（深度优先搜索）：「一条路走到黑，走不通再回头」。比如找电脑里的文件，先钻进第一个文件夹，把里面所有子文件夹/文件都翻完，再回到上一级，钻进第二个文件夹，直到找完所有内容。

  • BFS（广度优先搜索）：「先扫平一层，再往下一层」。还是找文件，先把当前文件夹的所有文件/子文件夹列出来（不钻进子文件夹），再依次钻进每个子文件夹，扫平子文件夹的内容，按层推进。

二、核心区别（表格对比，易记） ​

特性DFS（深度优先搜索）BFS（广度优先搜索）
遍历顺序先深度、后广度（纵向优先）先广度、后深度（横向优先）
核心数据结构栈（递归本质是调用栈）队列（先进先出）
空间复杂度最坏 $O(h)$ （h是树高度）最坏 $O(n)$ （n是节点总数）
适用场景找深层节点、遍历所有节点、找路径找浅层节点、最短路径、按层展示
二叉树对应前/中/后序遍历（递归版）层序遍历

三、在二叉树中实现（JS代码，关联你学过的知识） ​

1. DFS（深度优先）—— 对应二叉树前/中/后序遍历 ​

DFS在二叉树中最常用递归实现（底层是JS的调用栈），机试优先写递归版；如果要求非递归，可手动用栈实现。

JavaScript

// 1. 递归版DFS（前序遍历为例，中序/后序仅调整处理节点的顺序）
function dfsRecursion(root) {
    const result = [];
    // 递归核心：处理当前节点 → 递归左子树 → 递归右子树
    const traverse = (node) => {
        if (!node) return; // 终止条件：空节点
        result.push(node.val); // 处理当前节点（前序）
        traverse(node.left);   // 深度遍历左子树（钻到底）
        traverse(node.right);  // 深度遍历右子树
    };
    traverse(root);
    return result;
}

// 2. 非递归版DFS（手动用栈，机试特殊要求时用）
function dfsWithStack(root) {
    if (!root) return [];
    const stack = [root]; // 栈存储待处理节点（后进先出）
    const result = [];
    while (stack.length) {
        const node = stack.pop(); // 栈顶节点出栈（核心）
        result.push(node.val);
        // 先压右子节点（栈后进先出，保证左子节点先处理）
        if (node.right) stack.push(node.right);
        if (node.left) stack.push(node.left);
    }
    return result;
}

// 测试：树结构 1 / 2 3（2下还有4）
const root = new TreeNode(1, new TreeNode(2, new TreeNode(4)), new TreeNode(3));
console.log(dfsRecursion(root)); // [1,2,4,3]（先钻左子树到4，再处理右子树3）
console.log(dfsWithStack(root)); // [1,2,4,3]（和递归版结果一致）

2. BFS（广度优先）—— 对应二叉树层序遍历 ​

BFS必须用队列实现（先进先出），核心是「按层处理节点」，前端按层操作DOM/组件树时高频用到。

JavaScript

function bfs(root) {
    if (!root) return [];
    const queue = [root]; // 队列存储待处理节点（先进先出）
    const result = [];
    while (queue.length) {
        const node = queue.shift(); // 队首节点出队（核心）
        result.push(node.val);
        // 先压左子节点，再压右子节点（保证按层顺序）
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
    return result;
}

// 测试：同上的树，输出 [1,2,3,4]（先处理第一层1，再第二层2、3，最后第三层4）
console.log(bfs(root));

四、前端开发中的实际应用（重点） ​

BFS/DFS不是只用于算法题，前端业务/框架开发中高频落地：

1. DFS的前端场景（深度遍历） ​

  • 深拷贝：遍历嵌套对象/数组（结构像树），递归拷贝每一层属性（DFS核心）：

    JavaScript
    
function deepClone(obj) {
    if (typeof obj !== 'object' || obj === null) return obj;
    const newObj = Array.isArray(obj) ? [] : {};
    // DFS：遍历每个属性（子节点），递归拷贝
    for (let key in obj) {
        newObj[key] = deepClone(obj[key]);
    }
    return newObj;
}

  • AST遍历：Babel/ESLint处理代码生成的AST（抽象语法树）时，用DFS遍历所有节点（比如修改箭头函数节点）；

  • 树形组件递归渲染：Ant Design/Element UI的Tree组件，用DFS递归渲染每一层节点（部门树、权限树）；

  • 嵌套路由匹配：Vue Router/React Router找匹配的嵌套路由时，从根路由递归遍历子路由（DFS）。

2. BFS的前端场景（按层遍历） ​

  • DOM按层操作：比如「查找某个元素的所有同级元素」「按层渲染骨架屏」，用BFS遍历DOM树；

  • 虚拟DOM Diff：React/Vue的Diff算法先按层对比虚拟DOM节点（BFS），避免深度遍历的高开销；

  • 树形控件按层操作：Tree组件的「按层展开」「模糊搜索时按层匹配节点」；

  • 找最短路径：比如嵌套路由中找从根到目标路由的最短路径（BFS天然适合找最短路径）。

五、直观对比：找二叉树中的目标节点 ​

以找值为3的节点为例，看DFS和BFS的执行差异：

Plain

    1   （第一层）
   / \
  2   3 （第二层）
 /
4      （第三层）

  • DFS执行：1 → 2 → 4（没找到，回头）→ 回到2 → 回到1 → 3（找到）；

  • BFS执行：1（没找到）→ 2、3（找到3，直接终止）；

结论：BFS找「层级浅」的节点更快，DFS适合找「层级深」的节点或需要遍历所有节点的场景。

总结 ​

  1. DFS（深度优先）：「纵向遍历」，用栈/递归实现，对应二叉树前/中/后序遍历，前端常用于深拷贝、AST遍历、递归渲染树形组件；

  2. BFS（广度优先）：「横向遍历」，用队列实现，对应二叉树层序遍历，前端常用于DOM按层处理、虚拟DOM Diff、找最短路径；

  3. 选择技巧：需要按层处理/找最短路径选BFS，需要递归遍历所有节点/找深层节点选DFS。

（注：文档部分内容可能由 AI 生成）

最近更新