JS递归遍历树形结构的实现原理与代码示例

作者:代码拾荒

时间:2026-11-20

浏览:374

深入解析 JavaScript 中递归遍历树形结构的核心原理、调用栈工作机制,并提供前序遍历、后序遍历、条件过滤与路径查找的完整代码示例与生产边界防护方案。

文章目录
JavaScript 进阶算法 深度优先遍历 (DFS) 运行时调用栈模型
在 JavaScript 开发中,无论处理侧边栏多级菜单、组织架构关系、分类目录还是 DOM 节点树,树形数据都是最普遍的结构形态。递归遍历利用函数自调用的机制,天然贴合树形结构自相似的嵌套特征。本文直接拆解递归遍历的核心运行机制、V8 引擎调用栈的行为规律,并给出前序、后序、路径回溯及带层级过滤的完整代码示例与生产边界防护方案。
JS递归遍历树形结构的实现原理与代码示例
全景概览:树形层级数据经由 JavaScript 递归处理引擎转化为线性执行序列的全局流程

一、树形结构在 JavaScript 中的表现形式与递归逻辑基石

在 JavaScript 中,树形结构通常表示为嵌套的对象或对象数组。每个树节点至少包含用于存放业务数据的属性,以及一个用于挂载下一层子节点的数组属性(通常命名为 children)。

// 标准树节点对象结构示例
const orgTree = {
  id: "1",
  name: "研发总部",
  children: [
    {
      id: "2",
      name: "前端组",
      children: [
        { id: "3", name: "Web前端", children: [] },
        { id: "4", name: "移动端", children: [] }
      ]
    },
    {
      id: "5",
      name: "后端组",
      children: []
    }
  ]
};

递归算法之所以能够精准遍历这种嵌套结构,依赖于数学归纳法与分治思想:任何一棵树都可以看作一个根节点与若干棵子树的组合。实现一个可靠的递归遍历函数,必须具备两个最基本的逻辑支柱:

  1. 基准终止条件(Base Case):这是防止程序陷入死循环的安全阀。当某个节点不存在或者该节点不再包含子节点(!node.children || node.children.length === 0)时,当前调用分支必须立即停止下潜并返回上一层。
  2. 规模递减推进步(Recursive Step):当节点存在子节点时,遍历其 children 数组,对每个子节点重新调用遍历函数本身。每一次自调用都在处理规模更小的子树,直到逐步抵达叶子节点触发基准条件。
JS递归遍历树形结构的实现原理与代码示例
图 1:左侧树形结构拓扑与右侧 JavaScript 引擎执行栈(Call Stack)的压栈与上下文隔离机制

从底层来看,如图 1所示,JavaScript 引擎是单线程运行的。每当一个函数被调用,引擎便在内存的调用栈(Call Stack)中为其分配一个新的栈帧(Stack Frame)。栈帧内封闭保存着该层函数的局部变量、入参(如当前节点引用、当前深度等)以及代码执行游标。

当父节点的遍历函数进入 for 循环并调用子节点时,父函数的执行状态会被冻结并保留在栈内;直到子节点及其所有后代节点完全执行完毕并出栈销毁后,父函数的栈帧才会被唤醒,继续执行循环的下一轮。

二、深度优先递归遍历的基础代码与单步执行推导

树的递归遍历属于典型的深度优先遍历(Depth-First Search, DFS)。其策略是“纵向探索优先”:只要眼前还有子节点,就持续顺着层级向下深潜,直到碰触到没有后代的叶子节点,才沿原路回退,继而探索相邻的兄弟节点。

1. 标准 DFS 递归遍历实现

以下是支持多叉树、支持访问回调及层级深度的标准通用递归遍历函数:

/**
 * 通用深度优先递归遍历树结构
 * @param {Object} node - 根节点
 * @param {Function} callback - 针对每个节点的访问回调 (node, parent, depth) => void
 * @param {Object|null} parent - 当前节点的父节点
 * @param {number} depth - 当前节点在树中的深度(根节点为 0)
 */
function traverseDFS(node, callback, parent = null, depth = 0) {
  // 边界防护:节点为空时直接中止
  if (!node) return;

  // 1. 执行当前节点的业务逻辑
  callback(node, parent, depth);

  // 2. 基准条件判定与递推步:若存在 children 则递归遍历
  if (Array.isArray(node.children) && node.children.length > 0) {
    for (let i = 0; i < node.children.length; i++) {
      traverseDFS(node.children[i], callback, node, depth + 1);
    }
  }
}

// 示例调用:打印树形节点与层级缩进
traverseDFS(orgTree, (node, parent, depth) => {
  const indent = "  ".repeat(depth);
  console.log(`${indent}├─ [${node.id}] ${node.name} (父级: ${parent ? parent.name : '无'})`);
});

示例输出:

├─ [1] 研发总部 (父级: 无)
  ├─ [2] 前端组 (父级: 研发总部)
    ├─ [3] Web前端 (父级: 前端组)
    ├─ [4] 移动端 (父级: 前端组)
  ├─ [5] 后端组 (父级: 研发总部)
JS递归遍历树形结构的实现原理与代码示例
图 2:深度优先递归遍历六步生命周期推导图(入栈探索、叶子触底、栈帧弹出与兄弟分支切换)

2. 单步执行推导解析

结合图 2的六个阶段,我们可以清晰跟踪 JavaScript 引擎在执行该代码时的状态演变:

  • Step 01:传入根节点 Node 1,在栈底创建 Frame 1。执行 callback(Node 1)。检查发现其包含两个子节点 [Node 2, Node 5]。循环启动,对第一个子节点发起自调用。
  • Step 02:traverseDFS(Node 2) 执行,在调用栈推入 Frame 2。Frame 1 的循环在 i=0 处挂起等待。执行 callback(Node 2),随后发现其有子节点 [Node 3, Node 4],继续深入调用 Node 3。
  • Step 03:traverseDFS(Node 3) 压入 Frame 3。执行 callback(Node 3)。检查 Node 3.children 为空数组,不满足 children.length > 0,触发 Base Case。函数代码到底自然结束。
  • Step 04:Node 3 栈帧销毁并从调用栈弹出。执行权限退回到 Frame 2(Node 2),Frame 2 从挂起点恢复,i 自增为 1,准备处理下一个子节点 Node 4。
  • Step 05:traverseDFS(Node 4) 压入栈执行,随后同样触发叶子条件立即返回弹出。此时 Node 2 的子节点全部遍历完毕,Frame 2 结束并出栈。
  • Step 06:栈深度回退到 1,Frame 1(根节点)恢复执行,其内部循环 i 推进到 1,转入 Node 5(后端组)。整个右子树重复同样逻辑,最后整棵树遍历结束,调用栈恢复初始空闲状态。

三、前序遍历与后序遍历:时机差异与业务场景选型

在多叉树中,根据执行节点访问回调(业务逻辑)相对于子节点递归调用的先后顺序,可划分为前序遍历和后序遍历。理解这一先后顺序,是决定数据在树中是“自顶向下流动”还是“自底向上汇聚”的核心前提。

JS递归遍历树形结构的实现原理与代码示例
图 3:前序遍历(先处理再递归)与后序遍历(先递归再汇聚)的时机、数据流向及应用场景对比

1. 前序遍历(Pre-order):自顶向下派发

核心时机:先执行当前节点的操作,再深入子节点递归。

由于父节点先于子节点得到处理,前序遍历允许父节点把计算出的属性(例如层级序号、上级菜单路径、全局配置)自顶向下透传给每个子节点。如果任务是搜索某个特定的节点,前序遍历还可以在命中目标后立即打断后续子树遍历,避免多余开销。

2. 后序遍历(Post-order):自底向上汇聚

核心时机:先完整执行完所有子树的递归并拿到返回值,最后才处理当前节点。

在许多现实业务中,父节点的数据依赖于所有子节点的统计结果。例如:计算一个目录占用的总磁盘空间(必须先算出每个子文件和子目录的大小,再求和赋给父目录);或者在权限树复选框中,父节点的“全选/半选/未选”状态完全由其子节点的勾选状况决定。

/**
 * 后序遍历应用示例:自底向上计算树形目录的节点总数与累积尺寸
 * 每个节点具有 size 属性,父节点的 totalSize 等于其自身 size 加上所有子树的 totalSize
 */
function computeDirectorySizes(node) {
  let childrenTotal = 0;

  // 1. 先递归子节点,获取子节点汇聚后的数据
  if (Array.isArray(node.children) && node.children.length > 0) {
    for (const child of node.children) {
      childrenTotal += computeDirectorySizes(child);
    }
  }

  // 2. 子节点全部计算完毕后,后序处理当前节点
  node.totalSize = (node.size || 0) + childrenTotal;

  // 3. 将计算结果回传给父级
  return node.totalSize;
}
对比维度 前序遍历 (Pre-order) 后序遍历 (Post-order)
执行顺序 当前节点 → 递归子节点 1 → 递归子节点 2 递归子节点 1 → 递归子节点 2 → 当前节点
数据流动方式 自顶向下(从根向叶)传递状态、路径与深度 自底向上(从叶向根)聚合统计、计算汇总指标
典型使用场景 层级缩进渲染、树形结构深拷贝、路径快速搜索 目录大小统计、UI复选框半选级联联动、自底向上销毁节点
短路能力 支持(在父级命中时可提前放弃探索子分支) 不支持(必须等待所有子节点完全遍历回传)

四、高频实战场景:路径查找、结构过滤与树拍平

在掌握了递归的核心原理后,针对前端常见业务场景,以下提供三个高频功能的高质量代码实现。

1. 查找目标节点并提取祖先路径链路(回溯法)

在面包屑导航、树形下拉定位等功能中,经常需要根据目标节点的 id,反向查出从根节点到该节点的所有祖先节点列表。利用递归配合回溯(Backtracking)可以优雅解决这一需求:

/**
 * 根据 ID 查找节点及其完整祖先路径
 * @param {Object} node - 根节点
 * @param {string|number} targetId - 待查找的目标节点 ID
 * @param {Array} currentPath - 当前递归链路上的节点栈
 * @returns {Array|null} 包含路径节点的数组;若未找到则返回 null
 */
function findNodePath(node, targetId, currentPath = []) {
  if (!node) return null;

  // 1. 将当前节点压入路径栈
  currentPath.push(node);

  // 2. 如果当前节点正是目标,直接返回当前路径副本
  if (node.id === targetId) {
    return [...currentPath];
  }

  // 3. 若有子节点,继续向下深搜
  if (Array.isArray(node.children)) {
    for (const child of node.children) {
      const found = findNodePath(child, targetId, currentPath);
      if (found) return found; // 命中目标,逐层短路返回
    }
  }

  // 4. 回溯步骤(Backtrack):子树均未找到目标,将当前节点移出路径栈
  currentPath.pop();
  return null;
}

// 示例验证:查找 ID 为 "3"(Web前端)的完整链路
const path = findNodePath(orgTree, "3");
console.log(path.map(n => n.name).join(" > "));
// 示例输出: "研发总部 > 前端组 > Web前端"

2. 保留父级骨架的条件过滤(搜索过滤树)

当用户在搜索框输入关键词过滤树形组件时,若某个子节点匹配了关键词,则其所有直系父节点必须保留在树中以维持层级视觉完整;而未匹配且没有匹配后代的分支应当被裁剪掉:

/**
 * 递归过滤树形结构,保留包含匹配节点的完整父子分支
 * @param {Object} node - 根节点
 * @param {Function} predicate - 过滤条件谓词函数 (node) => boolean
 * @returns {Object|null} 返回修剪后的新树副本,若全部分支不满足则返回 null
 */
function filterTree(node, predicate) {
  if (!node) return null;

  const isSelfMatch = predicate(node);
  const validChildren = [];

  // 递归过滤子节点
  if (Array.isArray(node.children)) {
    for (const child of node.children) {
      const filteredChild = filterTree(child, predicate);
      if (filteredChild) {
        validChildren.push(filteredChild);
      }
    }
  }

  // 保留条件:自身命中 OR 至少有一个子节点命中
  if (isSelfMatch || validChildren.length > 0) {
    return {
      ...node,
      children: validChildren
    };
  }

  // 都不命中,整枝裁剪
  return null;
}

// 示例调用:搜索名称包含 "Web" 的分支
const searchResult = filterTree(orgTree, item => item.name.includes("Web"));
// 结果:研发总部 保留,前端组 保留,Web前端 保留;移动端 与 后端组 被剪除

3. 多叉树展平为一维扁平列表(Flatten Tree)

在将树形数据批量持久化到关系数据库表、或者在表格组件中做虚拟滚动渲染时,往往需要将嵌套对象数组展平为一维列表,并自动补充 parentId 与 depth 字段:

/**
 * 将多叉树展平为扁平一维数组
 * @param {Object|Array} treeData - 树根节点或根节点数组
 * @returns {Array} 展平后的节点数组
 */
function flattenTree(treeData) {
  const result = [];
  const nodes = Array.isArray(treeData) ? treeData : [treeData];

  function walk(node, parentId = null, depth = 0) {
    if (!node) return;
    const { children, ...nodeProps } = node;
    
    // 压入带有父级关联和层级元数据的扁平对象
    result.push({
      ...nodeProps,
      parentId,
      depth
    });

    if (Array.isArray(children)) {
      for (const child of children) {
        walk(child, node.id, depth + 1);
      }
    }
  }

  nodes.forEach(root => walk(root));
  return result;
}

五、边界防御与工程化考量:调用栈溢出与循环引用

递归写法直观优美,但在生产环境中若处理不受控的外部数据,必须认真应对两类致命隐患:循环引用死循环与调用栈溢出。

陷阱 1:数据循环引用造成无限递归

当树形数据由后端或复杂业务生成时,某些节点可能会意外建立环状引用(例如子节点的 node.parent 再次指向父级,或者双向链表化)。在未经防护的递归中,这会导致函数在环路中无限入栈,瞬时崩溃。

防御标准:使用 JavaScript 的 WeakSet 记录已经访问过的节点对象内存引用。由于 WeakSet 保存的是弱引用,不会阻碍垃圾回收(GC),遍历结束后临时集合自动被清理,零内存泄漏。

/**
 * 带环路检测的安全树遍历函数
 */
function safeTraverseTree(node, callback, visited = new WeakSet()) {
  if (!node || typeof node !== "object") return;

  // 环路拦截:若当前节点在此前调用链路中已经访问过,立即跳过以防死循环
  if (visited.has(node)) {
    console.warn("检测到循环引用节点,已终止深潜:", node.id);
    return;
  }
  visited.add(node);

  callback(node);

  if (Array.isArray(node.children)) {
    for (const child of node.children) {
      safeTraverseTree(child, callback, visited);
    }
  }
}
陷阱 2:极端树深触发 Maximum call stack size exceeded

V8 引擎对调用栈的最大帧数有着严格物理上限(在 Node.js / Chrome 中通常约为 10,000 帧左右)。如果树结构退化成链表,或者层级深度超过此上限,代码将无情抛出 RangeError: Maximum call stack size exceeded。

架构选型建议:

  • 在一般前端场景(菜单通常在 3~8 层,组织架构在数十层以内),递归是绝对的最佳选择,代码清晰度与维护性远优于循环。
  • 在可能出现数千层以上嵌套的极端场景(如超大型语法 AST 树、深层依赖图),应改用显式栈(Explicit Stack Array)的迭代式 DFS。由于数组存放在堆内存(Heap)而非受限的调用栈(Call Stack),其可承受深度受限于物理内存,可安全处理数十万层数据。
/**
 * 迭代式深度优先遍历(基于显式堆内存数组模拟栈,规避调用栈溢出风险)
 */
function traverseDFSIterative(root, callback) {
  if (!root) return;
  const stack = [root];

  while (stack.length > 0) {
    const current = stack.pop();
    callback(current);

    // 为保证与递归相同的先左后右顺序,需逆序将子节点压入栈
    if (Array.isArray(current.children)) {
      for (let i = current.children.length - 1; i >= 0; i--) {
        stack.push(current.children[i]);
      }
    }
  }
}
JS递归遍历树形结构的实现原理与代码示例
图 4:JavaScript 递归遍历设计范式与工程防御全景总结(核心逻辑、状态收集、环路防御与技术选型)

六、总结

在 JavaScript 中,递归遍历树形结构的本质是将树的层级嵌套关系映射为运行时的函数调用栈推入与回溯。编写稳健的树算法时,始终牢记以下准则:

  • 终止条件先行:始终明确 Base Case 的退出边界,防止无限递推。
  • 看准执行时机:需要自顶向下传递属性或短路查找用前序遍历;需要自底向上累加统计或级联联动用后序遍历。
  • 关注边界防御:面对不可信数据源,使用 WeakSet 筑起环路防火墙;在万级以上极端深度场景下,主动选用显式栈迭代解法。

实用工具推荐

电子包浆

绿化、压缩、噪点和虚拟水印,自由调节做旧程度。

使用 ›
图片压缩

选择画质和输出格式,预览压缩前后的大小。

使用 ›
相关文章