javascript - 将相关元素嵌套在一起父/子

Question

假设我有一个包含对象的数组:

[
  {
    "id": "5a97e047f826a0111b754beb",
    "name": "Hogwarts",
    "parentId": "5c7bf2191d41c810b2ad6186",
    "childrenIds": []
  },
  {
    "id": "5c7bf2191d41c810b2ad6186",
    "name": "Defense Against The Dark Arts",
    "parentId": null,
    "childrenIds": [
      "5a97e047f826a0111b754beb"
    ]
  }
]

我想做的是一个返回另一个数组的函数，但这次只有没有parentID作为根元素的项目，并且有一个包含其子元素的子数组，因此到达叶子谁有一个空的childrenIDs数组。 (同时删除父/子 ID 属性)

对于之前的输入，我会返回类似这样的内容

[
  {
    "id": "5c7bf2191d41c810b2ad6186",
    "name": "Defense Against The Dark Arts",
    "children": [
      {
        "id": "5a97e047f826a0111b754beb",
        "name": "Hogwarts"
      }
    ]
  }
]

我似乎想不出任何有效的代码来完成这项任务，有人可以帮忙吗？

Answer 1

您可以通过对象中的 ID 保留对每个节点的引用，并在执行过程中构建树。由于我们可能会遇到对尚未看到的条目的引用，因此我们将同时创建 stub (仅包含子数组)并稍后添加其其余字段。

这样我们就只有一个循环。

看起来你有一种垂直双链表，将父级 ID 保存在子级中，并将子级 ID 保存在父级中，但我们只需要其中之一来构建树。我们将使用存储在每个子项中的父项 ID。 (请注意，这假设您的结构是一致的，没有不平衡的关系或悬空引用。)

为了简单起见，我们创建一个根节点，我们将在最后返回其子节点，这样我们就不必以任何不同的方式处理没有父节点的节点。

然后你可以编写这样的代码:

function makeTree (rows) {
  // Use a symbol to denote the root ID to avoid clashes with any real IDs
  const ROOT = Symbol('ROOT')

  // Node index, by ID
  // Add a root node from the start
  const nodes = { [ROOT]: { children: [] } }

  // Helper function to return an existing node or create a stub if not existing
  const getNodeOrCreateStub = id => nodes[id] || (nodes[id] = { children: [] })

  for (const row of rows) {
    // Add current row to index, merging data with existing stub, if any.
    // This keeps any existing references in other nodes' children arrays intact
    // because Object.assign mutates the first object passed to it and returns the
    // same object.
    const node = Object.assign(getNodeOrCreateStub(row.id), row)

    // Remove unwanted properties.
    delete node.parentId
    delete node.childrenIds

    // Get parent or create parent stub if parent node not already existing
    const parent = getNodeOrCreateStub(row.parentId || ROOT)

    // Add current node as child to parent
    parent.children.push(node)
  }

  // Return children of root node
  return nodes[ROOT].children
}

请注意，此代码当前还在叶节点中创建空的 children 数组，这与上面的示例不同。但是我认为这使代码更简单，因为它不必处理任何不同的叶节点，无论是在创建树还是在稍后读取它时! (您不必执行 children && Children.length 来检查子项，您始终可以直接访问 children。)

要更改它并获得与示例中完全相同的结果，您可以按如下方式更改代码:

// Change this...
const getNodeOrCreateStub = id => nodes[id] || (nodes[id] = { children: [] })
// ...to this:
const getNodeOrCreateStub = id => nodes[id] || (nodes[id] = {})

// Also change this...
parent.children.push(node)
// ...to this:
if (!parent.children) parent.children = []
parent.children.push(node)
// ...or to this:
parent.children = [...parent.children || [], node]