js list to tree

在JavaScript中，将列表转换为树结构是一种常见的操作，尤其是在处理需要层级展示的数据，如菜单、分类等。这通常涉及到递归函数和对象的引用。以下是一个简单的例子，展示了如何将一个扁平化的列表转换为多层级树结构。
假设我们有以下这样的列表，每个节点有一个 `id` 和一个 `parentId`，表示它的父节点的ID：

const list = [
  { id: 1, parentId: null },
  { id: 2, parentId: 1 },
  { id: 3, parentId: 1 },
  { id: 4, parentId: 2 },
  { id: 5, parentId: 2 },
  { id: 6, parentId: 3 },
];

我们的目标是将这个列表转换成如下所示的树结构：

const tree = [
  {
    id: 1,
    parentId: null,
    children: [
      {
        id: 2,
        parentId: 1,
        children: [
          { id: 4, parentId: 2 },
          { id: 5, parentId: 2 }
        ]
      },
      {
        id: 3,
        parentId: 1,
        children: [
          { id: 6, parentId: 3 }
        ]
      }
    ]
  }
];

以下是将列表转换为树的JavaScript函数：

function listToTree(items) {
  const rootItems = [];
  const lookup = {};
  for (const item of items) {
    const itemId = item['id'];
    const parentId = item['parentId'];
    if (!lookup[itemId]) lookup[itemId] = { ['children']: [] };
    lookup[itemId] = { ...item, children: lookup[itemId]['children'] };
    if (parentId === null) {
      rootItems.push(lookup[itemId]);
    } else {
      if (!lookup[parentId]) lookup[parentId] = { ['children']: [] };
      lookup[parentId]['children'].push(lookup[itemId]);
    }
  }
  return rootItems;
}
const tree = listToTree(list);
console.log(JSON.stringify(tree, null, 2));

这个函数首先创建一个空的对象 `lookup` 来存储列表中每个元素的引用，并最终用它来构建树。然后，它遍历列表，对于每个元素，将其添加到 `lookup` 对象中，并根据其 `parentId` 将其作为子元素添加到相应的父元素中。最后，函数返回根元素数组 `rootItems`，它包含了整个树结构。