扁平化数组转换成tree array

在 JavaScript 中，将扁平化数组转换为树形数组（Tree Array）是一个常见的需求，通常用于处理具有层级关系的数据，例如组织结构、文件目录等。以下是实现这一功能的步骤和代码示例。

数据结构说明

假设我们有一个扁平化的数组，每个对象包含以下字段：

id：唯一标识符。
parentId：父级的 id，如果没有父级，则为 null 或特定值。
其他字段（如 name、children 等）。
目标是将这个扁平化数组转换为一个树形结构，其中每个节点包含一个 children 数组，用于存储子节点。

实现步骤

创建一个映射表：将每个节点的 id 映射到其对应的对象，便于快速查找。
构建树形结构：遍历每个节点，根据其 parentId 将其添加到父节点的 children 数组中。
提取根节点：所有没有父节点（parentId 为 null 或特定值）的节点作为树的根节点。

示例代码

以下是一个完整的实现示例：

输入数据

const flatArray = [
  { id: 1, parentId: null, name: 'Root' },
  { id: 2, parentId: 1, name: 'Child 1' },
  { id: 3, parentId: 1, name: 'Child 2' },
  { id: 4, parentId: 2, name: 'Grandchild 1' },
  { id: 5, parentId: 2, name: 'Grandchild 2' },
  { id: 6, parentId: null, name: 'Another Root' },
  { id: 7, parentId: 6, name: 'Child of Another Root' },
];

转换代码

function flatArrayToTree(flatArray) {
  // 创建一个映射表，将 id 映射到对应的对象
  const map = new Map(flatArray.map(item => [item.id, { ...item, children: [] }]));
  // 创建一个数组，用于存储根节点
  const tree = [];
  for (const item of flatArray) {
    const node = map.get(item.id); // 获取当前节点
    if (item.parentId === null) {
      // 如果没有父节点，则为根节点
      tree.push(node);
    } else {
      // 如果有父节点，则将当前节点添加到父节点的 children 数组中
      const parentNode = map.get(item.parentId);
      if (parentNode) {
        parentNode.children.push(node);
      }
    }
  }
  return tree;
}
// 调用函数并打印结果
const treeArray = flatArrayToTree(flatArray);
console.log(treeArray);

输出结果

[
  {
    id: 1,
    parentId: null,
    name: 'Root',
    children: [
      { id: 2, parentId: 1, name: 'Child 1', children: [
        { id: 4, parentId: 2, name: 'Grandchild 1', children: [] },
        { id: 5, parentId: 2, name: 'Grandchild 2', children: [] }
      ] },
      { id: 3, parentId: 1, name: 'Child 2', children: [] }
    ]
  },
  {
    id: 6,
    parentId: null,
    name: 'Another Root',
    children: [
      { id: 7, parentId: 6, name: 'Child of Another Root', children: [] }
    ]
  }
]

代码解析

映射表的创建：
1
const map = new Map(flatArray.map(item => [item.id, { ...item, children: [] }]));
- 使用 Map 创建一个映射表，将每个节点的 id 映射到其对应的对象，并初始化 children 数组。

遍历数组并构建树形结构：

for (const item of flatArray) {
  const node = map.get(item.id); // 获取当前节点
  if (item.parentId === null) {
    tree.push(node); // 如果没有父节点，则为根节点
  } else {
    const parentNode = map.get(item.parentId); // 获取父节点
    if (parentNode) {
      parentNode.children.push(node); // 将当前节点添加到父节点的 children 数组中
    }
  }
}

遍历扁平化数组，根据 parentId 判断当前节点是否为根节点。
如果是根节点，直接加入 tree 数组。
如果不是根节点，找到其父节点，并将当前节点加入父节点的 children 数组。

返回树形结构：
1
return tree;
- 最终返回构建好的树形数组。

注意事项

数据完整性：
- 确保每个节点的 parentId 是有效的，否则可能会导致某些节点无法正确加入树形结构。
- 如果数据中存在无效的 parentId，可以在代码中添加额外的检查逻辑。
性能优化：
- 使用 Map 来存储节点，可以快速通过 id 查找节点，避免了多次遍历数组，提高了性能。
扩展性：
- 如果需要支持更复杂的层级关系（如多级嵌套），当前的实现已经足够支持。只需要确保数据结构正确即可。
  通过上述方法，可以将扁平化数组高效地转换为树形数组，适用于各种需要层级结构的场景。