将父子关系数组转换为树形结构

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

谢谢！

- Mark Pope

---

很多 :) 但是（显然）我还没有得出解决方案。我可以发布一些我正在研究的代码片段，但我认为它们会导致更多的混乱而不是清晰度。 - Mark Pope

@Scobal请发布代码片段。你可能已经非常接近解决方案了，我们可以告诉你解决方案是什么。 - Vivin Paliath

你需要进行解析和映射。 - G. Bach

这是我的当前尝试：http://jsfiddle.net/5AgqT 希望能有所帮助！ - Mark Pope

这里也有一个解决方案 https://dev59.com/CWMl5IYBdhLWcg3w7qlq#32326075 - DenQ

Answer 1

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

你的算法应该像这样：

1. 创建一个将id映射到节点的map。这将使查找节点变得容易。 2. 循环遍历节点数组。 3. 对于每个元素。

- 在map中添加一个条目。 - 为此节点添加一个children属性（一个数组）。 - 这个元素有父节点吗？如果没有，它必须是根，所以将此元素分配给树的根。 - 这个元素有父节点，所以查找父节点，然后将此当前节点作为父节点的子节点添加到父节点的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。其余算法基本相同（除了存储节点到映射中的那一行；因为你已经在第一次遍历中完成了这个操作，所以不需要了）。

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

- Vivin Paliath

---

仅供参考，当前的fiddle出现了一个“Uncaught TypeError: Cannot read property '#<Object>' of undefined”错误。除此之外，我喜欢这个实现-简单而简洁，+1。 - Lasse Christiansen

@LasseChristiansen-sw_lasse 抱歉，我链接的是旧版本。我已经修复了链接。 - Vivin Paliath

这个解决方案假设原始的“数组”数据已经按照某种方式排序，以便于parentNode = idToNodeMap [datum.parentAreaRef.id] 已经包含了你要查找的父节点的引用。虽然提问者在问题中的示例数据可能已经表明了这一点，但我认为在所提出的解决方案中应该承认这一事实，因为它是该算法的一个严重限制。 - arcseldon

@arcseldon 我在回答一开始就基本上承认了这一点。 - Vivin Paliath

Answer 2

我知道现在有点晚了，但我刚刚完成了这个算法，也许可以帮助其他寻求解决相同问题的人：http://jsfiddle.net/akerbeltz/9dQcn/

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

如果您需要根据自己的需求进行调整，请更改以下行：

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])

希望能帮到您！ 更新： 基于@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);

谢谢！

- AkerbeltZ

---

这对我很有用。谢谢。 - Enkode

最好在这里发布您的代码 - jsfiddle 有时可能会删除它。 - ESP32

完成 @Gerfried。谢谢！ - AkerbeltZ

Answer 3

虽然我来晚了，但是我刚完成了一个如何实现这个的示例，我想分享一下，也许能为另一种解决方案提供有用的信息或启发。

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

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

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

...用于构建树结构的工具。

- Lasse Christiansen

---

谢谢！你需要更改你的代码为 if (!child.children)。 - Kapila Perera

Answer 4

您可以使用npm中的array-to-tree模块。

- romseguy

---

或者使用我的更高效的实现（经过单元测试，100％代码覆盖率，仅0.5 kb大小并包含类型定义）：npmjs.com/package/performant-array-to-tree - Philip Stanislaus

Answer 5

借鉴了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;
  }
}

- Mr. Polywhirl

---

一个相关的问题，在PHP中，可以在这里找到：将一系列父子关系转换为分层树？ - Mr. Polywhirl

Answer 6

你的字符串有误

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

应该是这样的

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

我也稍微优化了一下：

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

- Alexandr Sydorenko

Answer 7

试一试：

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

- Eric Frick