logo标签列表

如何将具有父子关系的嵌套数组转换为平面数组？

javascriptarraysalgorithmtreedepth-first-search
4

我有一个数组，其中包含具有父子关系的嵌套对象，如下所示：

[
{id: 1, title: 'hello', parent: 0, children: [
    {id: 3, title: 'hello', parent: 1, children: [
        {id: 4, title: 'hello', parent: 3, children: [
            {id: 5, title: 'hello', parent: 4, children: []},
            {id: 6, title: 'hello', parent: 4, children: []}
        ]},
        {id: 7, title: 'hello', parent: 3, children: []}
    ]}
]},
{id: 2, title: 'hello', parent: 0, children: [
    {id: 8, title: 'hello', parent: 2, children: []}
]}
]

我需要将它转换为一个普通数组，并保留类似于父子关系的结构，按照父级和其所有子元素先返回，然后再继续下一个父级。
[
{id: 1, title: 'hello', parent: 0},
{id: 3, title: 'hello', parent: 1},
{id: 4, title: 'hello', parent: 3},
{id: 5, title: 'hello', parent: 4},
{id: 6, title: 'hello', parent: 4},
{id: 7, title: 'hello', parent: 3},
{id: 2, title: 'hello', parent: 0},
{id: 8, title: 'hello', parent: 2}
]

我可以使用递归函数将其转换回来。

但是我需要以高效的方式执行相反的操作。如示例嵌套数组所示，存在多级嵌套。

编辑：更新嵌套数组以便叶节点具有空的子数组。

此外，ES5中的答案将会有所帮助。

@a.mola：请查看mplungjan的答案，其中提供了一种非递归解决方案。 - MrSmith42
1
你的问题被标记为 breadth-first-search，但是你的扁平数组是深度优先搜索的输出。 - trincot
1
@trincot 没错。标签已更改。 - Priyanker Rao
6个回答
3
我只是使用一个简单的递归函数来将数组对象转换为普通数组。 

var arr = [ {id: 1, title: 'hello', parent: 0, children: [ {id: 3, title: 'hello', parent: 1, children: [ {id: 4, title: 'hello', parent: 3, children: [ {id: 5, title: 'hello', parent: 4, children: []}, {id: 6, title: 'hello', parent: 4, children: []} ]}, {id: 7, title: 'hello', parent: 3, children: []} ]} ]}, {id: 2, title: 'hello', parent: 0, children: [ {id: 8, title: 'hello', parent: 2, children: []} ]} ];

var result = [];
var convertArrToObj = (arr) => {
  arr.forEach(e => {
    if (e.children) {
      result.push({
        id: e.id,
        title: e.title,
        parent: e.parent
      });
      convertArrToObj(e.children);
    } else result.push(e);

  });
};
convertArrToObj(arr);
console.log(result);

简单易懂。 - mplungjan
谢谢。我稍微更新了这个解决方案，通过深度克隆'e'对象并从中删除children属性。这只是为了以防万一我有很多属性，最好只删除一个children属性。var i = JSON.parse(JSON.stringify(e)); delete i.subTrendingTopics; result.push(i); - Priyanker Rao
3

在ES5中，您还可以使用一些函数式编程方法，并使用[].concat.apply来展平数组：

function flatten(arr) {
    return [].concat.apply([], arr.map(function (obj) {
        return [].concat.apply([
            { id: obj.id, title: obj.title, parent: obj.parent }
        ], flatten(obj.children));
    }));
}

let arr = [{id: 1, title: 'hello', parent: 0, children: [{id: 3, title: 'hello', parent: 1, children: [{id: 4, title: 'hello', parent: 3, children: [{id: 5, title: 'hello', parent: 4, children: []},{id: 6, title: 'hello', parent: 4, children: []}]},{id: 7, title: 'hello', parent: 3, children: []}]}]},{id: 2, title: 'hello', parent: 0, children: [{id: 8, title: 'hello', parent: 2, children: []}]}];

console.log(flatten(arr));

在ES6中，相同的算法可简化为以下内容： 

const flatten = arr => arr.flatMap(({children, ...o}) => [o, ...flatten(children)]);

let arr = [{id: 1, title: 'hello', parent: 0, children: [{id: 3, title: 'hello', parent: 1, children: [{id: 4, title: 'hello', parent: 3, children: [{id: 5, title: 'hello', parent: 4, children: []},{id: 6, title: 'hello', parent: 4, children: []}]},{id: 7, title: 'hello', parent: 3, children: []}]}]},{id: 2, title: 'hello', parent: 0, children: [{id: 8, title: 'hello', parent: 2, children: []}]}];

console.log(flatten(arr));

2

使用 ES5 将需要更多的代码行，并且像您所说的那样不太高效。

这是我的 ES5 版本，您应该能够注意到性能上的差异。

const data = [{id:1,title:'hello',parent:0,children:[{id:3,title:'hello',parent:1,children:[{id:4,title:'hello',parent:3,children:[{id:5,title:'hello',parent:4,children:[]},{id:6,title:'hello',parent:4,children:[]}]},{id:7,title:'hello',parent:3,children:[]}]}]},{id:2,title:'hello',parent:0,children:[{id:8,title:'hello',parent:2,children:[]}]}];

// Recursively
function reduceArrayDimension(array) {
  var level = [];

  array.forEach(function(item) {
    level.push({
      id: item.id,
      title: item.title,
      parent: item.parent
    });
    item.children.forEach(function(child) {
        reduceArrayDimension([child]).forEach(function(childItem) {
          level.push(childItem);
        });
    });
  });

  return level;
}

console.log(reduceArrayDimension(data));

并且ES6

const data=[{id:1,title:'hello',parent:0,children:[{id:3,title:'hello',parent:1,children:[{id:4,title:'hello',parent:3,children:[{id:5,title:'hello',parent:4,children:[]},{id:6,title:'hello',parent:4,children:[]}]},{id:7,title:'hello',parent:3,children:[]}]}]},{id:2,title:'hello',parent:0,children:[{id:8,title:'hello',parent:2,children:[]}]}];

// Recursively
function reduceArrayDimension(array) {
  const level = [];
  
  array.forEach(item => {
    level.push({id: item.id, title: item.title, parent: item.parent});
    if (item.children) level.push(...reduceArrayDimension(item.children));
  });
  
  return level;
}

console.log(reduceArrayDimension(data));

这会生成一个从子级到父级的顺序。我需要从父级到子级。我认为你之前的解决方案给出了正确的输出，就我所知。无论如何，感谢你的努力。 - Priyanker Rao
@PriyankerRao 我已经编辑了，现在是从父级到子级。 - a.mola
0
如果数据不是很大，这可能是一种实用的方法。 

const data = [{ id: 1, title: 'hello', parent: 0, children: [{ id: 3, title: 'hello', parent: 1, children: [{ id: 4, title: 'hello', parent: 3, children: [{ id: 5, title: 'hello', parent: 4 }, { id: 6, title: 'hello', parent: 4 , children:[]} ] }, { id: 7, title: 'hello', parent: 3 } ] }] }, { id: 2, title: 'hello', parent: 0, children: [{ id: 8, title: 'hello', parent: 2 }] } ];

const str = JSON.stringify(data)
  .replaceAll('"children":[',"},")
  .replaceAll("]}","")
  .replaceAll(",,",",")   // handle empty children
  .replaceAll(",}","}");


console.log(JSON.parse(str).sort((a,b) => a.id-b.id))

更新了问题，包括叶节点的空数组。这会导致更新后的情况出现错误。不过我可以解析对象并删除空的子数组以使其正常工作。 - Priyanker Rao
@PriyankerRao 这次更新处理了空子元素。 - mplungjan
1
我从不想依赖这样的东西，但我很惊讶它能够工作！ - Scott Sauyet
0
如果数据很大，可以考虑使用尾递归优化和async/await。 

const arr = [
{id: 1, title: 'hello', parent: 0, children: [
    {id: 3, title: 'hello', parent: 1, children: [
        {id: 4, title: 'hello', parent: 3, children: [
            {id: 5, title: 'hello', parent: 4},
            {id: 6, title: 'hello', parent: 4}
        ]},
        {id: 7, title: 'hello', parent: 3}
    ]}
]},
{id: 2, title: 'hello', parent: 0, children: [
    {id: 8, title: 'hello', parent: 2}
]}
];

const convertArr = (arr) => {
  return arr.reduce((init, cur) => {
    const plain = init.concat(cur);
    const children = cur.children;
    return plain.concat(children && children.length ? convertArr(children) : [])
  }, [])
}

const generateArr = (arr) => {
  return convertArr(arr).map(v => ({
    id: v.id,
    parent: v.parent,
    title: v.title
  }))
}
console.log('result:', generateArr(arr))

远远太复杂了。 - mplungjan
0
你可以使用生成器函数： 

var arr = [ {id: 1, title: 'hello', parent: 0, children: [ {id: 3, title: 'hello', parent: 1, children: [ {id: 4, title: 'hello', parent: 3, children: [ {id: 5, title: 'hello', parent: 4, children: []}, {id: 6, title: 'hello', parent: 4, children: []} ]}, {id: 7, title: 'hello', parent: 3, children: []} ]} ]}, {id: 2, title: 'hello', parent: 0, children: [ {id: 8, title: 'hello', parent: 2, children: []} ]} ];
function* flatten(d){
   for (var i of d){
      yield {id:i.id, title:i.title, parent:i.parent}
      yield* flatten(i.children)
   }
}
console.log([...flatten(arr)])

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接