在javascript中从平面数组构建树数组

IT技术 javascript arrays list tree
2021-01-10 07:10:13

我有一个复杂的 json 文件,我必须用 javascript 处理它以使其分层,以便以后构建一棵树。json 的每个条目都有: id :一个唯一的 id, parentId :父节点的 id (如果节点是树的根,则为 0) level :树中的深度级别

json 数据已经“排序”了。我的意思是一个条目将在其自身之上有一个父节点或兄弟节点,在其自身之下有一个子节点或兄弟节点。

输入 :

{
    "People": [
        {
            "id": "12",
            "parentId": "0",
            "text": "Man",
            "level": "1",
            "children": null
        },
        {
            "id": "6",
            "parentId": "12",
            "text": "Boy",
            "level": "2",
            "children": null
        },
                {
            "id": "7",
            "parentId": "12",
            "text": "Other",
            "level": "2",
            "children": null
        },
        {
            "id": "9",
            "parentId": "0",
            "text": "Woman",
            "level": "1",
            "children": null
        },
        {
            "id": "11",
            "parentId": "9",
            "text": "Girl",
            "level": "2",
            "children": null
        }
    ],
    "Animals": [
        {
            "id": "5",
            "parentId": "0",
            "text": "Dog",
            "level": "1",
            "children": null
        },
        {
            "id": "8",
            "parentId": "5",
            "text": "Puppy",
            "level": "2",
            "children": null
        },
        {
            "id": "10",
            "parentId": "13",
            "text": "Cat",
            "level": "1",
            "children": null
        },
        {
            "id": "14",
            "parentId": "13",
            "text": "Kitten",
            "level": "2",
            "children": null
        },
    ]
}

预期输出:

{
    "People": [
        {
            "id": "12",
            "parentId": "0",
            "text": "Man",
            "level": "1",
            "children": [
                {
                    "id": "6",
                    "parentId": "12",
                    "text": "Boy",
                    "level": "2",
                    "children": null
                },
                {
                    "id": "7",
                    "parentId": "12",
                    "text": "Other",
                    "level": "2",
                    "children": null
                }   
            ]
        },
        {
            "id": "9",
            "parentId": "0",
            "text": "Woman",
            "level": "1",
            "children":
            {

                "id": "11",
                "parentId": "9",
                "text": "Girl",
                "level": "2",
                "children": null
            }
        }

    ],    

    "Animals": [
        {
            "id": "5",
            "parentId": "0",
            "text": "Dog",
            "level": "1",
            "children": 
                {
                    "id": "8",
                    "parentId": "5",
                    "text": "Puppy",
                    "level": "2",
                    "children": null
                }
        },
        {
            "id": "10",
            "parentId": "13",
            "text": "Cat",
            "level": "1",
            "children": 
            {
                "id": "14",
                "parentId": "13",
                "text": "Kitten",
                "level": "2",
                "children": null
            }
        }

    ]
}
6个回答

如果您使用地图查找,则有一个有效的解决方案。如果父母总是在他们的孩子之前,你可以合并两个 for 循环。它支持多个根。它在悬垂的分支上给出错误,但可以修改以忽略它们。它不需要第 3 方库。据我所知,这是最快的解决方案。

function list_to_tree(list) {
  var map = {}, node, roots = [], i;
  
  for (i = 0; i < list.length; i += 1) {
    map[list[i].id] = i; // initialize the map
    list[i].children = []; // initialize the children
  }
  
  for (i = 0; i < list.length; i += 1) {
    node = list[i];
    if (node.parentId !== "0") {
      // if you have dangling branches check that map[node.parentId] exists
      list[map[node.parentId]].children.push(node);
    } else {
      roots.push(node);
    }
  }
  return roots;
}

var entries = [{
    "id": "12",
    "parentId": "0",
    "text": "Man",
    "level": "1",
    "children": null
  },
  {
    "id": "6",
    "parentId": "12",
    "text": "Boy",
    "level": "2",
    "children": null
  },
  {
    "id": "7",
    "parentId": "12",
    "text": "Other",
    "level": "2",
    "children": null
  },
  {
    "id": "9",
    "parentId": "0",
    "text": "Woman",
    "level": "1",
    "children": null
  },
  {
    "id": "11",
    "parentId": "9",
    "text": "Girl",
    "level": "2",
    "children": null
  }
];

console.log(list_to_tree(entries));

如果您对复杂性理论感兴趣,则此解决方案是 Θ(n log(n))。递归过滤器的解决方案是 Θ(n^2),这对于大型数据集来说可能是一个问题。

尽管答案很好,但它很复杂。仅对两行代码应用我的答案:链接
2021-03-11 07:10:13
请记住,使用此解决方案,您的节点必须专门排序以确保首先将父节点推送到地图中,否则查找过程将出错...因此您要么需要在 level 属性上对它们进行排序,要么需要首先将它们推入地图。并使用单独的 for 循环进行查找。(我更喜欢 sort 但是当您没有 level 属性时,单独的循环可能是一种选择)
2021-03-15 07:10:13
@Halcyon 在地图中查找需要恒定的时间,即 O(1)。
2021-03-21 07:10:13
请你解释一下为什么这个解决方案是 Θ(n log(n)),它似乎需要 O(n) 时间。
2021-03-27 07:10:13
一开始我发现令人惊讶的是,无法在其中有效地使用附加信息,例如:[1, 5, 6] 之类的路径,其中数组是后续祖先。但是看看代码有点道理,因为我相信它是 O(n)
2021-04-07 07:10:13

(奖励 1:节点可能会或可能不会被订购)

(奖励 2:不需要第 3 方库,纯 JS)

(奖励3:用户“Elias Rabl”说这是性能最高的解决方案,请参阅下面的答案)

这里是:

const createDataTree = dataset => {
  const hashTable = Object.create(null);
  dataset.forEach(aData => hashTable[aData.ID] = {...aData, childNodes: []});
  const dataTree = [];
  dataset.forEach(aData => {
    if(aData.parentID) hashTable[aData.parentID].childNodes.push(hashTable[aData.ID])
    else dataTree.push(hashTable[aData.ID])
  });
  return dataTree;
};

这是一个测试,它可能会帮助您了解解决方案的工作原理:

it('creates a correct shape of dataTree', () => {
  const dataSet = [{
    "ID": 1,
    "Phone": "(403) 125-2552",
    "City": "Coevorden",
    "Name": "Grady"
  }, {
    "ID": 2,
    "parentID": 1,
    "Phone": "(979) 486-1932",
    "City": "Chełm",
    "Name": "Scarlet"
  }];

  const expectedDataTree = [{
    "ID": 1,
    "Phone": "(403) 125-2552",
    "City": "Coevorden",
    "Name": "Grady",
    childNodes: [{
      "ID": 2,
      "parentID": 1,
      "Phone": "(979) 486-1932",
      "City": "Chełm",
      "Name": "Scarlet",
      childNodes : []
    }]
  }];

  expect(createDataTree(dataSet)).toEqual(expectedDataTree);
});
childNodes只在需要的时候添加不是更准确吗?通过将它们从第一个中移除并将它们forEach移动到第二个中?
2021-03-20 07:10:13
我可以得到特定项目的孩子吗?
2021-03-25 07:10:13
@FurkanO 非常好的解决方案,但是是否有可能通过函数式编程(无突变)获得接近此性能的任何地方
2021-04-03 07:10:13
如果有人想要一个孩子有多个父母,请参阅-> stackoverflow.com/a/65626153/8577819
2021-04-09 07:10:13

正如@Sander 所提到的,@Halcyon 的回答假设一个预先排序的数组,以下不是。(但是,它确实假设您已经加载了 underscore.js - 尽管它可以用 vanilla javascript 编写):

代码

// Example usage
var arr = [
    {'id':1 ,'parentid' : 0},
    {'id':2 ,'parentid' : 1},
    {'id':3 ,'parentid' : 1},
    {'id':4 ,'parentid' : 2},
    {'id':5 ,'parentid' : 0},
    {'id':6 ,'parentid' : 0},
    {'id':7 ,'parentid' : 4}
];

unflatten = function( array, parent, tree ){
    tree = typeof tree !== 'undefined' ? tree : [];
    parent = typeof parent !== 'undefined' ? parent : { id: 0 };
        
    var children = _.filter( array, function(child){ return child.parentid == parent.id; });
    
    if( !_.isEmpty( children )  ){
        if( parent.id == 0 ){
           tree = children;   
        }else{
           parent['children'] = children
        }
        _.each( children, function( child ){ unflatten( array, child ) } );                    
    }
    
    return tree;
}

tree = unflatten( arr );
document.body.innerHTML = "<pre>" + (JSON.stringify(tree, null, " "))
<script src="https://cdnjs.cloudflare.com/ajax/libs/underscore.js/1.9.1/underscore-min.js"></script>

要求

它假定属性 'id' 和 'parentid' 分别表示 ID 和父 ID。必须有父 ID 为 0 的元素,否则会返回一个空数组。孤立元素及其后代“丢失”

http://jsfiddle.net/LkkwH/1/

您的代码片段运行良好,谢谢!!唯一的事情是:tree在递归调用函数时永远不会作为参数传递,所以我认为该行tree = typeof tree !== 'undefined' ? tree : [];可以替换为let tree = [];
2021-03-21 07:10:13
您可以else { parent['children'] = []; }在第一个 if 子句之后添加以确保每个节点都有一个属性children(如果该节点是叶节点,它将为空)
2021-03-27 07:10:13
请记住,上述答案使用了两个循环,因此可以改进。由于我找不到实现 O(n) 解决方案的 npm module,我创建了以下module(单元测试,100% 代码覆盖率,大小仅 0.5 kb,包括类型)。也许它对某人有帮助:npmjs.com/package/performant-array-to-tree
2021-03-31 07:10:13
这可以修改为允许nullparent_ids 而不是 0 吗?编辑:没关系,我把它通过改变工作id: 0id: null
2021-04-07 07:10:13
对于任何感兴趣的人,代码很容易转换为 vanilla js:jsfiddle.net/LkkwH/853
2021-04-09 07:10:13

使用这种 ES6 方法。像魅力一样工作

// Data Set
// One top level comment 
const comments = [{
    id: 1,
    parent_id: null
}, {
    id: 2,
    parent_id: 1
}, {
    id: 3,
    parent_id: 1
}, {
    id: 4,
    parent_id: 2
}, {
    id: 5,
    parent_id: 4
}];

const nest = (items, id = null, link = 'parent_id') =>
  items
    .filter(item => item[link] === id)
    .map(item => ({ ...item, children: nest(items, item.id) }));

console.log(
  nest(comments)
)

如果数组有一个以上的 null parentId,则不起作用
2021-03-19 07:10:13
与 FurkanO 的回答相比慢
2021-04-01 07:10:13
我认为最短最好的答案
2021-04-02 07:10:13

有同样的问题,但我无法确定数据是否已排序我无法使用 3rd 方库,所以这只是普通的 Js;输入数据可以从@Stephen 的例子中获取;

 var arr = [
        {'id':1 ,'parentid' : 0},
        {'id':4 ,'parentid' : 2},
        {'id':3 ,'parentid' : 1},
        {'id':5 ,'parentid' : 0},
        {'id':6 ,'parentid' : 0},
        {'id':2 ,'parentid' : 1},
        {'id':7 ,'parentid' : 4},
        {'id':8 ,'parentid' : 1}
      ];
    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);
document.body.innerHTML = "<pre>" + (JSON.stringify(tree, null, " "))

JS小提琴

平面数组到树

我将如何从 parent id:1 开始?
2021-03-17 07:10:13
在某些情况下mappedArr[mappedElem['parentid']]['children']由于无法访问children未定义而失败
2021-03-31 07:10:13