树结构遍历

下面是 JavaScript 树菜单遍历的详细示例，包含深度优先遍历（DFS） 和广度优先遍历（BFS） 两种核心方式，并附具体应用场景说明。

1. 树菜单数据结构定义

先定义一个典型的多级菜单树结构（包含 id、name、children 等核心字段）：

// 树菜单数据（多级 menu tree）
const menuTree = [
  {
    id: "1",
    name: "首页",
    icon: "home",
    children: [], // 叶子节点（无子菜单）
  },
  {
    id: "2",
    name: "用户管理",
    icon: "user",
    children: [
      {
        id: "2-1",
        name: "用户列表",
        icon: "list",
        children: [
          { id: "2-1-1", name: "添加用户", icon: "add" },
          { id: "2-1-2", name: "编辑用户", icon: "edit" },
        ],
      },
      { id: "2-2", name: "角色权限", icon: "lock", children: [] },
    ],
  },
  {
    id: "3",
    name: "系统设置",
    icon: "setting",
    children: [{ id: "3-1", name: "基础配置", icon: "config", children: [] }],
  },
];

2. 深度优先遍历（DFS）

特点：从根节点出发，优先遍历完所有子节点（先深入，再回溯），适合层级嵌套展示（如递归渲染菜单组件）。

（1）递归实现（最常用）

/**
 * 深度优先遍历（递归版）
 * @param {Array} tree - 树菜单数组
 * @param {Function} callback - 节点处理函数（接收当前节点和层级）
 * @param {number} level - 当前层级（默认从 1 开始）
 */
function dfsRecursive(tree, callback, level = 1) {
  // 遍历当前层级的节点
  tree.forEach((node) => {
    // 处理当前节点（传入节点和层级）
    callback(node, level);

    // 若有子节点，递归遍历下一级（层级 +1）
    if (node.children && node.children.length > 0) {
      dfsRecursive(node.children, callback, level + 1);
    }
  });
}

// 使用示例：打印所有节点的名称和层级
console.log("DFS 递归遍历结果：");
dfsRecursive(menuTree, (node, level) => {
  // 用缩进表示层级（level 越大，缩进越多）
  const indent = "  ".repeat(level - 1);
  console.log(`${indent}${level}级 - ${node.name}（id: ${node.id}）`);
});

输出结果（层级清晰，先深入到最子节点再回溯）：

DFS 递归遍历结果：
1级 - 首页（id: 1）
1级 - 用户管理（id: 2）
  2级 - 用户列表（id: 2-1）
    3级 - 添加用户（id: 2-1-1）
    3级 - 编辑用户（id: 2-1-2）
  2级 - 角色权限（id: 2-2）
1级 - 系统设置（id: 3）
  2级 - 基础配置（id: 3-1）

（2）非递归实现（用栈模拟递归）

适合处理超大型树（避免递归栈溢出）：

/**
 * 深度优先遍历（非递归版，用栈实现）
 * @param {Array} tree - 树菜单数组
 * @param {Function} callback - 节点处理函数
 */
function dfsStack(tree, callback) {
  // 初始化栈（存储 [节点, 层级]）
  const stack = [];
  // 根节点入栈（层级为 1）
  tree.forEach((node) => stack.push([node, 1]));

  // 栈不为空则继续遍历
  while (stack.length > 0) {
    // 弹出栈顶节点（LIFO 后进先出）
    const [node, level] = stack.pop();

    // 处理当前节点
    callback(node, level);

    // 子节点入栈（注意：反序入栈，保证遍历顺序正确）
    if (node.children && node.children.length > 0) {
      // 从最后一个子节点开始入栈（因栈是后进先出）
      for (let i = node.children.length - 1; i >= 0; i--) {
        stack.push([node.children[i], level + 1]);
      }
    }
  }
}

// 使用示例：收集所有节点的 id
const allIds = [];
dfsStack(menuTree, (node) => {
  allIds.push(node.id);
});
console.log("DFS 非递归收集的 id：", allIds);
// 输出：['1', '2', '2-1', '2-1-1', '2-1-2', '2-2', '3', '3-1']

3. 广度优先遍历（BFS）

特点：按层级顺序遍历（先遍历完同一层级，再进入下一层），适合层级统计（如计算菜单总层数、查找某层级的所有节点）。

实现（用队列）

/**
 * 广度优先遍历（用队列实现）
 * @param {Array} tree - 树菜单数组
 * @param {Function} callback - 节点处理函数（接收当前节点和层级）
 */
function bfs(tree, callback) {
  // 初始化队列（存储 [节点, 层级]）
  const queue = [];
  // 根节点入队（层级为 1）
  tree.forEach((node) => queue.push([node, 1]));

  // 队列不为空则继续遍历
  while (queue.length > 0) {
    // 出队首节点（FIFO 先进先出）
    const [node, level] = queue.shift();

    // 处理当前节点
    callback(node, level);

    // 子节点入队（按顺序入队，保证层级顺序）
    if (node.children && node.children.length > 0) {
      node.children.forEach((child) => {
        queue.push([child, level + 1]);
      });
    }
  }
}

// 使用示例：按层级分组统计节点
const levelGroups = {};
bfs(menuTree, (node, level) => {
  // 按层级分组
  if (!levelGroups[level]) {
    levelGroups[level] = [];
  }
  levelGroups[level].push(node.name);
});
console.log("BFS 层级分组结果：", levelGroups);

输出结果（按层级分组，先处理完上层再处理下层）：

BFS 层级分组结果：
{
  '1': ['首页', '用户管理', '系统设置'],
  '2': ['用户列表', '角色权限', '基础配置'],
  '3': ['添加用户', '编辑用户']
}

4. 实际应用场景

（1）渲染多级菜单（DFS 递归渲染）

在前端框架（如 Vue/React）中，用 DFS 递归渲染嵌套菜单：

// 模拟 React 组件递归渲染菜单
function renderMenu(tree) {
  return tree.map((node) => (
    <div key={node.id} className={`menu-item level-${level}`}>
      <span>{node.name}</span>
      {/* 递归渲染子菜单 */}
      {node.children && node.children.length > 0 && renderMenu(node.children)}
    </div>
  ));
}

（2）查找最深层级的节点（BFS 应用）

// 查找菜单树的最大深度（最深层级）
function getMaxDepth(tree) {
  let maxDepth = 0;
  bfs(tree, (node, level) => {
    if (level > maxDepth) {
      maxDepth = level;
    }
  });
  return maxDepth;
}
console.log("菜单最大深度：", getMaxDepth(menuTree)); // 输出：3

（3）筛选包含特定关键词的菜单（结合 DFS）

// 查找名称包含「用户」的所有菜单节点
function findMenusByKeyword(tree, keyword) {
  const result = [];
  dfsRecursive(tree, (node) => {
    if (node.name.includes(keyword)) {
      result.push(node);
    }
  });
  return result;
}
const userMenus = findMenusByKeyword(menuTree, "用户");
console.log(
  "包含「用户」的菜单：",
  userMenus.map((m) => m.name)
);
// 输出：['用户管理', '用户列表', '添加用户', '编辑用户', '角色权限']

总结

遍历方式	核心思想	适用场景	实现方式
DFS	先深入子节点再回溯	递归渲染菜单、查找路径、深度相关操作	递归/栈
BFS	按层级顺序遍历	层级统计、广度相关操作、最短路径	队列

实际开发中，根据需求选择遍历方式：展示嵌套结构用 DFS，层级统计用 BFS；小型树用递归更简洁，大型树用非递归（栈/队列）更安全。