js 遍历嵌套数组

Question

需求：用最优性能的方法将嵌套数组转化为一维数组。

var data = [
  {
    id: '1', 
    title: 'A1', 
    child: [
      {
        id: '4',
        title: 'B1'
      }
    ]
  },
  { 
    id: '2', 
    title: 'A2',
    child: [
      {
        id: '5',
        title: 'B2',
        child: [
          {
            id: '7',
            title: 'C1',
            child: [
              {
                id: '8',
                title: 'D1'
              }
            ]
          }
        ]
      },
      {
        id: '6',
        title: 'B3'
      }
    ] 
  },
  { 
    id: '3', 
    title: 'A3' 
  }
]

// 结果应该为：
// [{id:'1',title:'A1'},{id:'4',title:'B1'},{id:'2',title:'A2'},{id:'5',title:'B2'}...]

请各路大侠赐教！

Answer 1

大概就是个广度优先算法嘛...

var result = [];    // 存放结果
var queue = [data]; // 用于遍历
var item;           // 临时值
// 从队列里取出要转换的数据数组
while (item = queue.shift()) {
    item.forEach(i => {
        // 遍历数组，转换数据，放入结果中
        result.push({
            id: i.id,
            title: i.title,
        });
        // 如果有子数据的，放到队列最后等待处理
        i.child && queue.push(i.child);
    })
}

---

emm...看了下评论是需要深度遍历...都写上吧。

var result = [];    // 存放结果
(function traverse(node) {
    node.forEach(i => {
        result.push({
            id: i.id,
            title: i.title,
        });
        // 有子数据的先遍历子数据
        i.child && traverse(i.child)
    })
})(data);

Answer 2

这是一个遍历树型结构的问题，可以参阅：使用递归遍历并转换树形数据，文中讲到了用递归实现的深度遍历，也讲到了用队列实现的广度遍历。

深度遍历和广度遍历的结果顺序会有所不同，楼上两位都是递归实现（深度），下面给个广度的示例：

function gothrough(data) {
    const queue = [...data];
    const result = [];
    while (true) {
        const next = queue.shift();
        if (!next) {
            break;
        }
        result.push({
            id: next.id,
            title: next.title
        });
        if (Array.isArray(next.child)) {
            queue.push(...next.child);
        }
   }

   return result;
}

代码还可以简洁一些，但性能可能会略差一点

function gothrough(data) {
    let next = [...data];
    const result = [];
    while (next.length) {
        result.push(...next.map(m => ({ id: m.id, title: m.title })));
        next = next
            .filter(m => Array.isArray(m.child))
            .reduce((all, m) => [...all, ...m.child], []);
    }
    return result;
}

Answer 3

var nest_result=[];
function arrNestToNonNest(arr){

for(let item of arr){
    nest_result.shift({"id":item.id,"title":item.title})
    if(item.hasOwnProperty("child")){
        arrNestToNonNest(item.child)
    }
}

}
arrNestToNonNest(data)

Answer 4

(function(_data,_list){
    function t_whill(data){
        for(let info of data){
            if('child' in info){
                t_whill(info['child']);
                delete info['child'];
            }
            _list.push(info);
        }
    }
    t_whill(_data,_list);
    log(_list);
})(data,[]);

Answer 5

可能并不是最优，但很清真（跑

function flattern(data) {
  return data.reduce((iter, val) => {
    let {id, title} = val;
    let com_arr = [...iter, {id, title}];
    return val.child ? [...com_arr, ...flattern(val.child)] : com_arr;
  }, []);
}

let result = flattern(data);
console.log(result);

Answer 6

function TreeToArray(data,list) {
    var i = 0, len = data.length, list = list || [];
    for (; i < len;) {
        var item = data[i++], child = item.child;
        if (child) {
            delete item.child;
            list.push(item);
            arguments.callee(child, list);
        } else {
            list.push(item);
        }
    }
}

var list = [];
TreeToArray(data, list);
console.log(JSON.stringify(list));

Answer 7

楼上的方法都不错了，这个性能也就这样的。