如何基于parent ID将Elm类型集合转换为NodeTree类型无限层级树结构

实现方案 #

我们可以通过两次遍历完成数组到树结构的转换，时间复杂度为O(n)，效率很高：

1. 先把所有Elm元素统一转换成带空children数组的NodeTree节点，用id作为键存在Map中，后续查找父节点的耗时为O(1)
2. 再次遍历所有节点，如果当前节点存在parent属性，就把它挂到对应父节点的children数组里；没有parent或者parent指向不存在id的节点，直接作为根节点返回

完整代码 #

interface Elm {
  id: number;
  name: string;
  parent?: number;
}

interface NodeTree {
  id: number;
  name: string;
  children: NodeTree[];
  parent?: number;
}

function buildTree(elements: Elm[]): NodeTree[] {
  const nodeMap = new Map<number, NodeTree>();
  const rootNodes: NodeTree[] = [];

  // 第一次遍历：初始化所有节点存入映射表
  elements.forEach(elm => {
    nodeMap.set(elm.id, {
      ...elm,
      children: []
    });
  });

  // 第二次遍历：关联父子节点关系
  elements.forEach(elm => {
    const currentNode = nodeMap.get(elm.id)!;
    if (elm.parent !== undefined && nodeMap.has(elm.parent)) {
      const parentNode = nodeMap.get(elm.parent)!;
      parentNode.children.push(currentNode);
    } else {
      rootNodes.push(currentNode);
    }
  });

  return rootNodes;
}

调用方式 #

直接传入你提供的elements数组即可得到符合要求的NodeTree数组：

const resultTree: NodeTree[] = buildTree(elements);

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