代码之家 › 专栏 › 技术社区 › InspectorDanno

从平面阵列构建树

tree javascript

InspectorDanno · 技术社区 · 4 年前

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": []
      }
    ]
  }
}

出了什么问题?

1 回复 | 直到 4 年前

trincot 4 年前

代码中的一个问题是 !foundNode 如果为true,则不将(第一个)子项添加到 children 大堆

同样奇怪的是 findNodeInChildren 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);

大堆 ,因为输入结构不能保证只有一个根。它可以代表 . 如果您确定它是一棵树(因此只有一个根),那么您可以从数组中弹出单个元素。