从具有子 ID 的平面数组创建层次结构

Question

我有一个平面数组，其中每个节点都有一个 ID 及其子节点的 ID 数组：

[
  {id: 1, children: [2, 3]}, 
  {id: 2, children: []}, 
  {id: 3, children: [4]}, 
  {id: 4, children: []}, 
  {id: 5, children: []},
]

我如何（最好是在 Javascript 中）创建一个层次结构，将实际对象作为嵌套子对象而不只是它们的 ID？

[
  {id: 1, children: [
    {id: 2, children: []}, 
    {id: 3, children: [
      {id: 4, children: []}
     ]}
  ]},
  {id: 5, children: []},
]

我尝试了以下方法，但它仅适用于第一层：

function getHierarchyFromFlatArray(nodes) {
    const nodeById = new Map(nodes.map(el => [el.id, el]))
    for (const node of nodes) {
        node.children = node.children.map(id => { 
            let val = nodeById.get(id)
            let idx = nodes.findIndex(item => item.id=== id)
            nodes.splice(idx, 1)
            return val
        })
    }
    return nodes
}

Answer 1

步骤：

创建每个节点到其父节点的映射（undefined 用于根节点）。
清除子数组并开始将每个节点附加到其父节点的子数组。
最后 return 在我们的映射中父键为 undefined 的节点。

const getHierarchyFromFlatArray = (nodes) => {
    const nodeById = {}
    const parent = {}

    nodes.forEach((node) => {
        nodeById[node.id] = node
        node.children.forEach((child) => {
            parent[child] = node.id
        })
        node.children = []
    })

    nodes.forEach((node) => {
        const parentId = parent[node.id]
        // ? If current node is the child of some other node
        if (parentId && nodeById[parentId]) {
            nodeById[parentId].children.push(node)
        }
    })

    return nodes.filter((node) => parent[node.id] === undefined)
}

const input = [
  {id: 1, children: [2, 3]}, 
  {id: 2, children: []}, 
  {id: 3, children: [4]}, 
  {id: 4, children: []}, 
  {id: 5, children: []},
]

const output = getHierarchyFromFlatArray(input)
console.log(output)

/*
output = [
  {id: 1, children: [
    {id: 2, children: []}, 
    {id: 3, children: [
      {id: 4, children: []}
     ]}
  ]},
  {id: 5, children: []},
]
*/

Answer 2

这是解决问题的一种方法。首先构建一个 Map 将 id 值引用到 node 值。然后处理列表中的每个节点（递归地用树替换子列表，同时从 Map 中删除这些节点）如果其 id 值存在于 Map 中。

const nodes = [
  {id: 1, children: [2, 3]}, 
  {id: 2, children: []}, 
  {id: 3, children: [4]}, 
  {id: 4, children: []}, 
  {id: 5, children: []},
]

const nodemap = new Map(nodes.map(n => [n.id, n]));

const tree = (node) => {
  nodemap.delete(node.id);
  return node.children.length ? {
    id : node.id, 
    children : node.children.map(c => tree(nodemap.get(c)))
  } 
  : node
}
  
result = []

nodes.forEach(node => {
  if (nodemap.has(node.id)) result.push(tree(node))
})

console.log(result)

从具有子 ID 的平面数组创建层次结构

Create hierarchy from flat array with children IDs

javascript

arrays

hierarchy