树形结构转为扁平数组结构

我们在之前一篇文章 如何将评论数据从扁平数组结构转为树形结构 ，讲解过如何把数组结构转为树形结构。这里我们讲下，如何将树形结构转为扁平的数组结构。

我们先来定义一个树形结构的数据：

COPYJAVASCRIPT
const tree = [
  {
    id: 1,
    nick: '111',
    children: [{ id: 6, nick: '666' }],
  },
  {
    id: 2,
    nick: '222',
    children: [
      {
        id: 3,
        nick: '333',
        children: [
          {
            id: 4,
            nick: '444',
            children: [
              {
                id: 5,
                nick: '555',
                children: [
                  { id: 8, nick: '888' },
                  { id: 9, nick: '999' },
                  { id: 10, nick: 'aaa' },
                  { id: 11, nick: 'bbb' },
                ],
              },
            ],
          },
          { id: 7, nick: '777' },
        ],
      },
    ],
  },
];

这是一个多层级的树形结构，我们把它转成数组。

这里我们有两个方式来进行转换：深度优先和广度优先。即优先使用当前节点的子节点，还是优先当前节点的兄弟节点。

1. 深度优先转换

深度优先，即若当前节点有子节点，优先遍历子节点，直到没有子节点，才遍历其兄弟节点。

COPYJAVASCRIPT
// 深度优先
const treeToListDepth = (tree) => {
  let result = [];

  tree.forEach((item) => {
    result.push(item); // 将该节点压进去

    // 若该节点有子节点，则优先执行子节点
    if (Array.isArray(item.children) && item.children.length) {
      result = result.concat(treeToListDepth(item.children));
    }
  });
  return result;
};

我们输出下结果：

从数组的排列顺序中，也能看到，子节点要比兄弟节点更靠前。

2. 广度优先转换

广度优先，即若当前节点有兄弟，优先遍历兄弟节点，有子节点时，则先存起来，等待后续的遍历。

COPYJAVASCRIPT
const treeToListBreadth = (tree) => {
  let queue = tree; // 用一个队列来存储将要遍历的节点
  const result = [];

  while (queue.length) {
    const item = queue.shift();
    result.push(item);

    // 子节点存储到队列中，等待遍历
    if (Array.isArray(item.children) && item.children.length) {
      queue = queue.concat(item.children);
    }
  }
  return result;
};

我们输出下结果：

从数组的排列顺序中，也能看到，兄弟节点要比子节点更靠前。

3. 总结

无论是深度优先还是广度优先，复杂度都差不多。从图片上也能看到，这里我们并没有进行特殊的处理，有几个节点的children还在，更细致的话，应该把每个节点的 children 属性去掉。