将父子数组转换为树

小编典典

将父子数组转换为树

algorithm

任何人都可以帮助转换以下父子对象列表：

[
   {
      “ name”：“ root”，
      “ _id”：“ root_id”，
   }，
   {
      “ name”：“ a1”，
      “ parentAreaRef”：{
         “ id”：“ root_id”，
      }，
      “ _id”：“ a1_id”，
   }，
   {
      “ name”：“ a2”，
      “ parentAreaRef”：{
         “ id”：“ a1_id”，
      }，
      “ _id”：“ a2_id”，
   }，
   {
      “ name”：“ a3”，
      “ parentAreaRef”：{
         “ id”：“ a2_id”，
      }，
      “ _id”：“ a3_id”，
   }，
   {
      “name”：“ b1”，
      “ parentAreaRef”：{
         “ id”：“ root_id”，
      }，
      “ _id”：“ b1_id”，
   }，
   {
      “ name”：“ b2”，
      “ parentAreaRef”：{
         “ id”：“ b1_id”，
      }，
      “ _id”：“ b2_id”，
   }，
   {
      “name”：“ b3”，
      “ parentAreaRef”：{
         “ id”：“ b1_id”，
      }，
      “ _id”：“ b3_id”，
   }
]

变成显示父子关系的树结构：

[
    {
        “ name”：“ root”，
        “ _id”：“ root_id”，
        “children”：[
            {
                “ name”：“ a1”，
                “ _id”：“ a1_id”，
                “children”：[
                    {
                        “ name”：“ a2”，
                        “ _id”：“ a2_id”，
                        “children”：[
                            {
                                “name”：“ a3”
                                “ _id”：“ a3_id”
                            }
                        ]
                    }
                ]
            }， 
            {
                “ name”：“ b1”，
                “ _id”：“ b1_id”，
                “children”：[
                    {
                        “name”：“ b2”
                        “ _id”：“ b2_id”
                    }，
                    {
                        “name”：“ b3”
                        “ _id”：“ b3_id”
                    }
                ]
            }
        ]
    }
]

（输出结构是一个允许有多个根的数组，但是如果我们能得到一个处理单个根的解决方案，那也很好。）

输出树如下所示：

根
  |
  -a1
  | |
  |  -  a2
  | |
  | -a3
  | 
  -b1
      |
      -b2
      -b3

谢谢！

阅读 324

2020-07-28

共1个答案

小编典典

我有一个可行的解决方案。就解决问题，我可以给您一些提示。好消息是您的数据不包含对节点的任何前向引用。因此，您只需一次遍历数组就可以创建树。如果需要注意的话，您首先需要遍历整个数组以建立ID到节点的映射。

您的算法将如下所示。

创建一个将ID映射到节点的映射。这将使查找节点变得容易。
遍历节点数组。
对于每个元素。
1. 在地图中添加一个条目。
2. children向此节点添加属性（数组）。
3. 元素是否有父级？如果不是，它必须是根，因此请将this元素分配给树的根。
4. 该元素有一个父节点，因此请查找父节点，然后将此当前节点添加为父节点的子节点（将其添加到children数组中）。

这应该可以帮助您解决问题。如果您对此算法有特定的问题，我可以指出问题出在哪里以及如何解决，也可以发布解决方案并解释如何解决。

更新

我查看了您拥有的解决方案。实际上，您实际上不需要递归，可以使用我上面描述的算法来迭代地执行此操作。您还需要就地修改结构，这会使算法更加复杂。但是您在正确的道路上。这是我解决的方法：

var idToNodeMap = {}; //Keeps track of nodes using id as key, for fast lookup
var root = null; //Initially set our loop to null

//loop over data
data.forEach(function(datum) {

    //each node will have children, so let's give it a "children" poperty
    datum.children = [];

    //add an entry for this node to the map so that any future children can
    //lookup the parent
    idToNodeMap[datum._id] = datum;

    //Does this node have a parent?
    if(typeof datum.parentAreaRef === "undefined") {
        //Doesn't look like it, so this node is the root of the tree
        root = datum;        
    } else {        
        //This node has a parent, so let's look it up using the id
        parentNode = idToNodeMap[datum.parentAreaRef.id];

        //We don't need this property, so let's delete it.
        delete datum.parentAreaRef;

        //Let's add the current node as a child of the parent node.
        parentNode.children.push(datum);        
    }
});

现在root指向整个树。

小提琴。

对于元素数组为任意顺序的情况，则必须idToNodeMap首先进行初始化。该算法的其余部分大致相同（除了在地图上存储节点的行；这不是必需的，因为您已经在第一遍中完成了该行）：

var idToNodeMap = data.reduce(function(map, node) {
    map[node._id] = node;
    return map;
}, {});

2020-07-28