多根嵌套树转换：生成带索引层级结构及代码优化

问题说明 #

需要将包含多个顶级父节点的JavaScript扁平数组，转换为带有层级index字段和children嵌套结构的树形数据。现有实现只能返回单个根节点，无法处理多顶级节点场景，同时不知道如何递归生成层级索引。

现有代码问题 #

当前代码仅能识别单个根节点，且未实现层级索引生成：

const invertHierarchy = (arr) => {
  const map = {};
  let root;
  for (const ele of arr) {
    map[ele.id] = ele;
    ele.topics = [];
  }
  for (const ele of arr) {
    if (map[ele.parentTopic] != null) map[ele.parentTopic].topics.push(ele);
    else root = ele;
  }
  return root;
};

解决方案代码 #

以下代码可实现多顶级节点的树形结构构建，并递归生成层级索引：

function buildHierarchyWithIndex(arr) {
  // 构建节点映射表，避免修改原数据，同时初始化children数组
  const nodeMap = {};
  const topLevelNodes = [];

  arr.forEach(node => {
    nodeMap[node.id] = { ...node, children: [] };
  });

  // 挂载子节点到对应父节点，并收集所有顶级节点
  arr.forEach(node => {
    const currentNode = nodeMap[node.id];
    if (node.parentTopic === undefined) {
      topLevelNodes.push(currentNode);
    } else {
      const parentNode = nodeMap[node.parentTopic];
      parentNode && parentNode.children.push(currentNode);
    }
  });

  // 递归生成层级索引
  function generateIndex(nodes, parentIndex = '') {
    nodes.forEach((node, idx) => {
      // 生成当前节点的层级索引：顶级节点直接用序号，子节点基于父索引拼接
      node.index = parentIndex ? `${parentIndex}.${idx + 1}` : `${idx + 1}`;
      // 递归处理子节点
      node.children.length > 0 && generateIndex(node.children, node.index);
    });
  }

  // 为所有节点生成索引
  generateIndex(topLevelNodes);

  return topLevelNodes;
}

// 测试数据
const flatTopics = [
  { id: 1, name: 'Top Level Topic 1', parentTopic: undefined },
  { id: 2, name: 'Some topic internally', parentTopic: 1 },
  { id: 3, name: 'Another topic', parentTopic: 2 },
  { id: 4, name: 'Just another topic', parentTopic: 2 },
  { id: 5, name: 'Another topic', parentTopic: 1 },
  { id: 6, name: 'Another topic', parentTopic: 5 },
  { id: 7, name: 'Another topic', parentTopic: 5 },
  { id: 8, name: 'Another topic', parentTopic: 1 },
  { id: 9, name: 'Another topic', parentTopic: 8 },
  { id: 10, name: 'Another topic', parentTopic: 9 },
  { id: 11, name: 'Another topic', parentTopic: 10 },
  { id: 12, name: 'Another Top Level Topic', parentTopic: undefined },
  { id: 13, name: 'Another Important Topic', parentTopic: 12 }
];

const treeResult = buildHierarchyWithIndex(flatTopics);
console.log(JSON.stringify(treeResult, null, 2));

代码关键点解释 #

• 节点映射表：通过nodeMap快速查找父节点，提升构建效率，同时复制原节点数据避免修改原始数组。
• 多顶级节点处理：遍历过程中收集所有parentTopic为undefined的节点，作为树形结构的根节点数组返回。
• 层级索引生成：递归函数generateIndex根据父节点的索引和当前子节点的序号（从1开始），拼接出当前节点的层级索引，如1.1.2这种格式。
• 递归遍历：对每个节点的子节点递归调用索引生成函数，确保整个树形结构的索引完整。

内容的提问来源于stack exchange，提问作者JimminyCricket