JavaScript树形结构递归算法如何实现及如何做性能优化

在前端开发中，树形结构数据广泛存在于菜单配置、组织架构、文件目录等多个场景，递归算法是处理这类数据的常用手段，但递归的不当使用会带来性能问题，需要针对性优化。

树形结构递归算法的常见实现

递归遍历树形结构

最基础的递归场景是遍历树形结构，比如打印所有节点的名称，假设树形结构每个节点包含name和children属性，递归实现如下：

// 定义树形结构示例
const treeData = [
  {
    name: '节点1',
    children: [
      { name: '节点1-1', children: [] },
      { name: '节点1-2', children: [{ name: '节点1-2-1', children: [] }] }
    ]
  },
  {
    name: '节点2',
    children: []
  }
];

// 递归遍历函数
function traverseTree(nodeList) {
  if (!Array.isArray(nodeList) || nodeList.length === 0) return;
  nodeList.forEach(node => {
    console.log(node.name);
    // 递归处理子节点
    if (Array.isArray(node.children) && node.children.length > 0) {
      traverseTree(node.children);
    }
  });
}

// 调用遍历函数
traverseTree(treeData);

递归查找目标节点

另一个常见需求是在树形结构中查找指定条件的节点，比如查找名称为指定值的节点，递归实现如下：

/**
 * 递归查找树形结构中的目标节点
 * @param {Array} nodeList 当前层级的节点数组
 * @param {Function} condition 查找条件函数，返回布尔值
 * @returns {Object|null} 找到的节点，未找到返回null
 */
function findTreeNode(nodeList, condition) {
  if (!Array.isArray(nodeList) || nodeList.length === 0) return null;
  for (let i = 0; i < nodeList.length; i++) {
    const node = nodeList[i];
    // 判断当前节点是否满足条件
    if (condition(node)) {
      return node;
    }
    // 递归查找子节点
    if (Array.isArray(node.children) && node.children.length > 0) {
      const result = findTreeNode(node.children, condition);
      if (result) {
        return result;
      }
    }
  }
  return null;
}

// 查找名称为节点1-2-1的节点
const targetNode = findTreeNode(treeData, node => node.name === '节点1-2-1');
console.log(targetNode);

递归算法的性能问题与优化方案

避免栈溢出问题

递归的最大深度受JavaScript调用栈大小限制，如果树形结构层级过深，容易出现栈溢出错误。可以通过尾递归优化或者改为迭代方式解决。

尾递归优化需要保证递归调用是函数的最后一步，且返回值不包含其他运算，部分JavaScript引擎支持尾递归优化，实现如下：

// 尾递归方式遍历树形结构
function traverseTreeTail(nodeList, result = []) {
  if (!Array.isArray(nodeList) || nodeList.length === 0) return result;
  const currentNode = nodeList[0];
  result.push(currentNode.name);
  // 递归调用是最后一步，且返回值仅包含递归结果
  return traverseTreeTail(
    nodeList.slice(1).concat(Array.isArray(currentNode.children) ? currentNode.children : []),
    result
  );
}

const traverseResult = traverseTreeTail(treeData);
console.log(traverseResult);

如果引擎不支持尾递归优化，可改用栈模拟递归的迭代方式，避免调用栈过深：

// 迭代方式遍历树形结构，使用栈模拟递归
function traverseTreeIterate(nodeList) {
  if (!Array.isArray(nodeList) || nodeList.length === 0) return [];
  const result = [];
  const stack = [...nodeList]; // 初始栈为根节点数组
  while (stack.length > 0) {
    const node = stack.pop();
    result.push(node.name);
    // 将子节点压入栈中，注意顺序如果需要和递归一致可以调整压栈顺序
    if (Array.isArray(node.children) && node.children.length > 0) {
      stack.push(...node.children);
    }
  }
  return result;
}

const iterateResult = traverseTreeIterate(treeData);
console.log(iterateResult);

减少重复计算

如果递归过程中存在重复的子树处理，可以用缓存机制存储已经处理过的结果，避免重复递归。比如统计树形结构的总节点数，可缓存已计算过的子树节点数：

// 带缓存的递归统计树形结构总节点数
function countTreeNodes(nodeList, cache = new Map()) {
  if (!Array.isArray(nodeList) || nodeList.length === 0) return 0;
  // 用节点唯一标识作为缓存key，这里假设name唯一，实际场景可用其他唯一id
  const cacheKey = nodeList.map(node => node.name).join('_');
  if (cache.has(cacheKey)) {
    return cache.get(cacheKey);
  }
  let total = 0;
  nodeList.forEach(node => {
    total += 1; // 当前节点计数
    if (Array.isArray(node.children) && node.children.length > 0) {
      total += countTreeNodes(node.children, cache);
    }
  });
  cache.set(cacheKey, total);
  return total;
}

const totalNodes = countTreeNodes(treeData);
console.log(totalNodes);

减少不必要的递归调用

递归前先判断是否有子节点，避免无意义的递归调用。比如前面的遍历函数中，只有children存在且长度大于0时才递归，而不是默认调用递归函数再判断空数组，减少函数调用开销。

扁平化树形结构减少递归次数

如果多次需要对同一树形结构做不同操作，可以先将其扁平化为一维数组，后续操作直接遍历一维数组，避免多次递归。扁平化也可以用递归实现，但扁平化后后续操作无需递归：

// 递归扁平化树形结构
function flattenTree(nodeList) {
  if (!Array.isArray(nodeList) || nodeList.length === 0) return [];
  let result = [];
  nodeList.forEach(node => {
    // 复制节点，避免修改原数据
    const flatNode = { ...node };
    delete flatNode.children; // 扁平化后不需要children属性
    result.push(flatNode);
    if (Array.isArray(node.children) && node.children.length > 0) {
      result = result.concat(flattenTree(node.children));
    }
  });
  return result;
}

const flatTree = flattenTree(treeData);
console.log(flatTree);
// 后续操作直接遍历flatTree即可，无需递归
flatTree.forEach(node => console.log(node.name));

总结

递归是处理JavaScript树形结构的便捷方式，但需要根据实际场景选择合适的实现方式，针对层级过深的树形结构可采用迭代替代递归，对重复处理逻辑可加入缓存，对高频操作的树形结构可先扁平化，从而提升代码的性能和健壮性，避免常见的递归相关问题。

JavaScript树形结构递归算法性能优化修改时间：2026-06-10 07:42:17