扁平 JSON 到具有重复节点的层次结构

Question

我正在从平面结构构建分层对象结构。到目前为止一切正常，但我对共享相同父 ID 的项目有疑问。例如：

{
   'id': 9,
   'parentid': 7
 }, {
   'id': 9,
   'parentid': 8
 }, {
   'id': 10,
   'parentid': 9
 }

根据我的理解，正确的是 ID 为 9 的项目同时出现在父级 7 和父级 8 下。同时，ID 为 10 的项目出现在 ID 9 的两个实例下。所以，我基本上想要这个：

{
    "id": 7,
    "parentid": 1,
    "children": [
     {
      "id": 9,
      "parentid": 7,
      "children": [
       {
        "id": 10,
        "parentid": 9,
        "children": []
       },
{
    "id": 8,
    "parentid": 1,
    "children": [
     {
      "id": 9,
      "parentid": 8,
      "children": [
       {
        "id": 10,
        "parentid": 9,
        "children": []
       }

但我得到的是这个。当一个 id 被分配一次时，该 id 可能的新出现将被忽略。

  {
    "id": 8,
    "parentid": 1,
    "children": [
     {
      "id": 9,
      "parentid": 8,
      "children": [
       {
        "id": 10,
        "parentid": 9,
        "children": []
       }

这是我正在使用的功能：

 function unflatten(arr) {
   var tree = [],
     mappedArr = {},
     arrElem,
     mappedElem;

   // First map the nodes of the array to an object -> create a hash table.
   for (var i = 0, len = arr.length; i < len; i++) {
     arrElem = arr[i];
     mappedArr[arrElem.id] = arrElem;
     mappedArr[arrElem.id]['children'] = [];
   }


   for (var id in mappedArr) {
     if (mappedArr.hasOwnProperty(id)) {
       mappedElem = mappedArr[id];
       // If the element is not at the root level, add it to its parent array of children.
       if (mappedElem.parentid) {
         mappedArr[mappedElem['parentid']]['children'].push(mappedElem);
       }
       // If the element is at the root level, add it to first level elements array.
       else {
         tree.push(mappedElem);
       }
     }
   }
   return tree;
 }

 var tree = unflatten(arr);

我不明白需要考虑 id 的所有出现，而不仅仅是第一次。我应该进一步研究哪个想法？

Answer 1

拥有一个对象 id，但又想拥有一个具有一个值的对象版本是违反直觉的parentid，另一个具有 parentid 的另一个值。从逻辑上讲，一个id应该标识一个对象，一个对象不能同时对同一个属性有两个不同的值。

注意这如何使您的代码在这一行出错：

mappedArr[arrElem.id] = arrElem;

由于相同的 id 出现多次，您 overwrite 相同的条目与您在此处分配的最后一个对象（版本）相同, 失去了之前 parentid 的其他值。

您应该考虑以复数形式创建一个属性 parentIds，并为其分配父级 id 值的数组。这样你就可以保持一个对象有多个父对象的情况。

请注意，节点不仅可以有多个子节点，还可以有多个父节点的图不是树（因此您的变量名称具有误导性），而是（有向）图。

从您的代码开始，我将其修改为：

function unflatten(arr) {
    var node,
        graph = [], // it is not a tree
        mapped = [];
    
    // 1. combine nodes with the same id:
    arr.forEach( function (node) {
        (mapped[node.id] || (mapped[node.id] = {
            id: node.id,
            parentIds: [],
            children: []
        })).parentIds.push(node.parentid);
    });
    
    // 2. assign children:
    mapped.forEach(function (node) {
        // Add as child to each of the parents 
        node.parentIds.forEach(function (parentid) {
            if (mapped[parentid]) {
                mapped[parentid]['children'].push(node);
            } else {
                // If parent does not exist as node, create it at the root level, 
                // and add it to first level elements array.
                graph.push(mapped[parentid] = {
                    id: parentid,
                    parentids: [],
                    children: [node]
                });
            }
        });
    });
    return graph;
}
// Sample data
var arr = [{
   'id': 9,
   'parentid': 7
}, {
   'id': 9,
   'parentid': 8
}, {
   'id': 10,
   'parentid': 9
}];
// Convert:
var graph = unflatten(arr);
console.log(JSON.stringify(graph, null, 4));

.as-console-wrapper { max-height: 100% !important; top: 0; }

扁平 JSON 到具有重复节点的层次结构

Flat JSON to hierarchy with repeated nodes

javascript

arrays

object

flatten