javascript - 将父子数组转换为树

Question

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

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

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

输出树如下所示:

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

谢谢!

Answer 1

我有一个有效的解决方案。就解决它而言，我可以给你提示。好消息是您的数据不包含对节点的任何前向引用。因此，您只需遍历数组即可创建树。如果注意到，您将需要首先遍历整个数组以构建 ID 到节点的映射。

您的算法将如下所示。

1. 创建一个将 ID 映射到节点的映射。这将使查找节点变得容易。
2. 遍历节点数组。
3. 对于每个元素。
   1. 在 map 中添加条目。
   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 指向整棵树。

Fiddle .

对于元素数组为任意顺序的情况，您必须先初始化idToNodeMap。算法的其余部分或多或少保持不变(除了您在 map 中存储节点的行；不需要那行，因为您已经在第一遍中完成了):

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