从平面阵列构建树

Question

我得到一个数组，links:

  const links = [
      {parent: "flare", children: "analytics"} ,
      {parent: "analytics", children: "cluster"} ,
      {parent: "flare", children: "scale"} ,
      {parent: "analytics", children: "graph"} ,
  ];

我想把它做成树，像这样：

const tree = {
 "name": "flare",
 "children": [
  {
   "name": "analytics",
   "children": [
    {
     "name": "cluster",
    },
    {
     "name": "graph",
    }
   ]
  }
 ]
};

这是我的尝试：

function buildTree(links) {

    const map = { }

    const findNodeInChildren = (name, obj) => {
      if (obj[name]) {
        return obj
      } else if (!obj.children) {
        return null
      }

      for (let i = 0; i < obj.children.length; i++) {
        const found = findNodeInChildren(name, obj.children[i])
        if (found) return found
      }

      return null
    }
    
    links.forEach(link => {
      const foundNode = findNodeInChildren(link.parent, map)
      
      if (!foundNode) {
        const newNode = {
          name: link.parent,
          children: []
        }
        map[newNode.name] = newNode
      } else {
          foundNode[link.parent].children.push({
          name: link.children,
          children: []
        })
      }
    })

   return map
}

  const links = [
      {parent: "flare", children: "analytics"} ,
      {parent: "analytics", children: "cluster"} ,
      {parent: "flare", children: "scale"} ,
      {parent: "analytics", children: "graph"} ,
  ];  
  
  const tree = buildTree(links)
  const json = JSON.stringify(tree)
  console.log(json)

这是美化后的 JSON - 它没有按预期工作：

{
  "flare": {
    "name": "flare",
    "children": [
      {
        "name": "scale",
        "children": []
      }
    ]
  },
  "analytics": {
    "name": "analytics",
    "children": [
      {
        "name": "graph",
        "children": []
      }
    ]
  }
}

出了什么问题？

Answer 1

您的代码中的一个问题是当 !foundNode 为真时，您没有将（第一个）child 添加到它的 children 数组中。

其次，object 你的代码 returns 是地图本身，显然在顶层有一个带有命名键的普通 object，而不是 [=41 的数组=]s 与“名称”键。代码应将 map-structure（确实是嵌套的）转换为所需的嵌套结构。

同样奇怪的是，findNodeInChildren returns整个map（即obj）找到节点的时候。如果返回 obj[name] 会更有意义，并且代码的其余部分也相应地进行了调整。

您还可以进一步压缩代码。

以下是我建议的做法：

const links = [
    {parent: "flare", children: "analytics"} ,
    {parent: "analytics", children: "cluster"} ,
    {parent: "flare", children: "scale"} ,
    {parent: "analytics", children: "graph"} ,
];  

// Create a Map keyed by parent, so that for each parent there is a 
// corresponding object, with (so far) empty children property.
// This uses the argument that can be passed to the Map constructor:
let map = new Map(links.map(({parent}) => [parent, { name: parent, children: [] }]));
// Iterate the input again, and look up each parent-related object, 
//  and insert there the child object, if found in the map, or otherwise
//  create an object for it without a children property (it has none).
for (let {parent, children} of links) map.get(parent).children.push(map.get(children) ?? { name: children });
// Delete from the map all nodes that have a parent
for (let {children} of links) map.delete(children);
// What remains are the nodes at the top level (roots). Extract these
//  objects from the map and store them as array
let result = [...map.values()];

console.log(result);

这段代码returns一个数组，因为输入结构不保证只有一个根。它可以代表一片森林。如果您确定它是一棵树（因此只有一个根），那么您可以将单个元素从数组中弹出。

从平面阵列构建树

Building a tree from a flat array

javascript

tree