javascript 将父子数组转换为树

Convert parent-child array to tree

提问by Mark Pope

Can anyone help converting the following list of parent-child objects:

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

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

into a tree structure showing the parent-child relationship:

成树状结构显示父子关系：

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

(The output structure is an array to allow for multiple roots but if we can get a solution that handles a single root that's great too.)

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

The output tree looks like this:

输出树如下所示：

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

Thanks!

谢谢！

回答by Vivin Paliath

I have a solution that works. I can give you hints as far as solving it. The good thing is that your data doesn't contain any forward references to nodes. So you can create your tree with just one pass through the array. If note, you will need to make a pass through the entire array first to build up a map of ids to nodes.

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

Your algorithm will look like this.

您的算法将如下所示。

1. Create a map that maps id's to nodes. This will make it easy to look up nodes.
2. Loop through the array of nodes.
3. For each element.
   1. Add an entry into the map.
   2. Add a childrenproperty (an array) to this node.
   3. Does the element have a parent? If not it must be the root, so assign the this element to the root of the tree.
   4. This element has a parent, so look up the parent node, and then add this current node as a child of the parent node (add it to the childrenarray).

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

This should help you solve the problem. If you're having specific issues with this algorithm I can point out where the problems are and how to solve it or post the solution and explain how I solved it.

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

UPDATE

更新

I looked at the solution that you have. You actually don't need recursion for this and you can do this iteratively using the algorithm I described above. You are also modifying the structure in-place, which makes the algorithm more complicated. But you're somewhat on the right track. Here is how I solved it:

我查看了您提供的解决方案。您实际上不需要为此递归，您可以使用我上面描述的算法迭代地执行此操作。您也在就地修改结构，这使得算法更加复杂。但你有点走在正确的轨道上。这是我解决它的方法：

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);        
    }
});

Now rootpoints to the entire tree.

现在root指向整个树。

Fiddle.

小提琴。

For the case where the array of elements is in arbitrary order, you will have to initialize idToNodeMapfirst. The rest of the algorithm remains more-or-less the same (except for the line where you store the node in the map; that's not needed because you did it already in the first pass):

对于元素数组按任意顺序排列的情况，您必须先进行初始化idToNodeMap。算法的其余部分或多或少保持不变（除了您在地图中存储节点的行；这不是必需的，因为您已经在第一遍中完成了）：

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

回答by AkerbeltZ

I know it's late, but I just finished this algorithm and maybe it can help some other people looking to solve the same problem: http://jsfiddle.net/akerbeltz/9dQcn/

我知道这是晚了，但我只是完成这个算法，也许它可以帮助一些人寻找解决同样的问题：http://jsfiddle.net/ akerbeltz/ 9dQcn /

A good thing about it is that it doesn't requires any special sort on the original object.

它的一个好处是它不需要对原始对象进行任何特殊排序。

If you need to adapt it to your needs change the following lines:

如果您需要使其适应您的需求，请更改以下几行：

1. Change the _id and the parentAreaRef.id depending on your structure.

   if (String(tree[i]._id) === String(item.parentAreaRef.id)) {

2. Change the parentAreaRef depending on your structure.

   if (tree[idx].parentAreaRef) buildTree(tree, tree.splice(idx, 1)[0])

1. 根据您的结构更改 _id 和 parentAreaRef.id。

   if (String(tree[i]._id) === String(item.parentAreaRef.id)) {

2. 根据您的结构更改 parentAreaRef。

   if (tree[idx].parentAreaRef) buildTree(tree, tree.splice(idx, 1)[0])

Hope it helps!

希望能帮助到你！

UPDATE

更新

Adding code here based on @Gerfried comment:

根据@Gerfried 评论在此处添加代码：

var buildTree = function(tree, item) {
    if (item) { // if item then have parent
        for (var i=0; i<tree.length; i++) { // parses the entire tree in order to find the parent
            if (String(tree[i]._id) === String(item.parentAreaRef.id)) { // bingo!
                tree[i].childs.push(item); // add the child to his parent
                break;
            }
            else buildTree(tree[i].childs, item); // if item doesn't match but tree have childs then parses childs again to find item parent
        }
    }
    else { // if no item then is a root item, multiple root items are supported
        var idx = 0;
        while (idx < tree.length)
            if (tree[idx].parentAreaRef) buildTree(tree, tree.splice(idx, 1)[0]) // if have parent then remove it from the array to relocate it to the right place
            else idx++; // if doesn't have parent then is root and move it to the next object
    }
}

for (var i=0; i<data.length; i++) { // add childs to every item
    data[i].childs = [];
}
buildTree(data);
console.log(data);

Thanks!

谢谢！

回答by Lasse Christiansen

I know I'm too late, but since I just finished my contribution to a sample implementation of how this can be done I thought I would share it, since it might be found useful / or give inspiration to an alternative solution.

我知道我为时已晚，但由于我刚刚完成了对如何做到这一点的示例实现的贡献，我想我会分享它，因为它可能会被发现有用/或为替代解决方案提供灵感。

The implementation can be found here: http://jsfiddle.net/sw_lasse/9wpHa/

实现可以在这里找到：http: //jsfiddle.net/sw_lasse/9wpHa/

The main idea of the implementation centers around the following recursive function:

实现的主要思想围绕以下递归函数：

// Get parent of node (recursive)
var getParent = function (rootNode, rootId) {

    if (rootNode._id === rootId)
        return rootNode;

    for (var i = 0; i < rootNode.children.length; i++) {
        var child = rootNode.children[i];
        if (child._id === rootId)
            return child;

        if (child.children.length > 0)
            var childResult = getParent(child, rootId);

        if (childResult != null) return childResult;
    }
    return null;
};

... that is used to build the tree.

...用于构建树。

回答by romseguy

You can use array-to-treemodule from npm.

您可以使用npm 中的数组到树模块。

回答by Mr. Polywhirl

Borrowing the caching logic from Vivin Paliath's answer, I have created a reusable function to convert a list of data with child-parent relationships into a tree.

借用 Vivin Paliath 的回答中的缓存逻辑，我创建了一个可重用的函数来将具有子父关系的数据列表转换为树。

var data = [
  { "id" : "root"                     },
  { "id" : "a1",   "parentId" : "root", },
  { "id" : "a2",   "parentId" : "a1",   },
  { "id" : "a3",   "parentId" : "a2",   },
  { "id" : "b1",   "parentId" : "root", },
  { "id" : "b2",   "parentId" : "b1",   },
  { "id" : "b3",   "parentId" : "b1",   }
];
var options = {
  childKey  : 'id',
  parentKey : 'parentId'
};
var tree = walkTree(listToTree(data, options), pruneChildren);

document.body.innerHTML = '<pre>' + JSON.stringify(tree, null, 4) + '</pre>';

function listToTree(list, options) {
  options = options || {};
  var childKey    = options.childKey    || 'child';
  var parentKey   = options.parentKey   || 'parent';
  var childrenKey = options.childrenKey || 'children';
  var nodeFn      = options.nodeFn      || function(node, name, children) {
    return { name : name, children : children };
  };
  var nodeCache = {};
  return list.reduce(function(tree, node) {
    node[childrenKey] = [];
    nodeCache[node[childKey]] = node;
    if (typeof node[parentKey] === 'undefined' || node[parentKey] === '') {
      tree = nodeFn(node, node[childKey], node[childrenKey]);
    } else {
      parentNode = nodeCache[node[parentKey]];
      parentNode[childrenKey].push(nodeFn(node, node[childKey], node[childrenKey]));
    }
    return tree;
  }, {});
}

function walkTree(tree, visitorFn, parent) {
  if (visitorFn == null || typeof visitorFn !== 'function') {
    return tree;
  }
  visitorFn.call(tree, tree, parent);
  if (tree.children && tree.children.length > 0) {
    tree.children.forEach(function(child) {
      walkTree(child, visitorFn, tree);
    });
  }
  return tree;
}

function pruneChildren(node, parent) {
  if (node.children.length < 1) {
    delete node.children;
  }
}

回答by Alexandr Sydorenko

There is an error in your string

你的字符串有错误

a[p].children.push(t);

It should be

它应该是

a[p].children.push(child);

also I'm little optimize it:

我也很少优化它：

var data = [{"id":1,"name":"X","parentId":null},{"id":2,"name":"Y","parentId":1},{"id":3,"name":"D","parentId":2},{"id":2,"name":"S","parentId":1},{"id":5,"name":"K","parentId":4}]
    var obj = {};
    obj.rootElements = [];
    for (i in data) {
        var _elem = data[i];
        if (_elem.parentId) {
            var _parentId = _elem.parentId;
            if (_parentId == _elem.id) {
                // check children, if false - add
                if (!_elem.children) {
                    _elem.children = [];
                }
                _elem.children.push(_elem);
            }
            else {
                addChildToParent(_elem, _parentId);
            }
        }
        else // is root
        {
            obj.rootElements.push(_elem);
        }
    }
    function addChildToParent(child, parentId, root) {
        for (j in data) {
            if (data[j].id.toString() == parentId.toString()) {
                if (!data[j].children) {
                    data[j].children = [];
                }
                data[j].children.push(child);
            }
        }
    }
    res.send(obj.rootElements); 

回答by Eric Frick

Give it a try:

试一试：

   var obj = {};
   obj.rootElements = [];
   var currentRoot;
   var currentParent;
   for (s in a) {
       var t = a[s];
       var id = t._id;
       if (t.parentAreaRef) {
           var parentId = t.parentAreaRef.id;
           if (parentId == currentParent._id) {
               //add children
               if (!currentParent.children) {
                   currentParent.children = [];
               }
               currentParent.children.push(t);
           }
           else {
               addChildToParent(t, parentId);
           }

       }
       else // is root
       {
           currentRoot = t;
           currentParent = t;
           obj.rootElements.push(currentRoot);
       }
   }

   var t = currentRoot

   function addChildToParent(child, parentId, root) {
       for (p in a) {
           if (a[p]._id.toString() == parentId.toString()) {
               if (!a[p].children) {
                   a[p].children = [];
               }
               a[p].children.push(t);
           }
       }
   }