javascript - 遍历树的深度而不是分支

Question

我有很多对象，例如重复模式的{id, followers}地方：followers

{
  id: 0, followers: [{
    id: 1, followers: [{
      id: 11, followers: [{
        id: 111, followers: [...]
      }]
    }]
  }, {
    id: 2, followers: [{
      id: 21, followers: [{
        id: 211, followers: [...]
      }]
    }]
  }, {
    id: 3, followers: [{
      id: 31, followers: [...]
    }]
  }, ...]
}

我想走这棵树并创建一个扁平的类型数组{id, depth}

我正在使用以下递归函数：

function recurse(user, depth = 0, list = []) {
  for (const { id } of user.followers) {
    list.push({ id, depth });
  }
  for (const follower of user.followers) {
    recurse(
      user: follower,
      depth: depth + 1,
      list
    );
  }
  return list;
}

在继续之前，它会越来越深入每个分支，这会导致类似

[
  { id: 0, depth: 0},
  { id: 1, depth: 1},
  { id: 11, depth: 2},
  { id: 111, depth: 3},
  { id: 1111, depth: 4},
  { id: 11111, depth: 5},
  ...
  { id: 2, depth: 1},
  { id: 21, depth: 2},
  { id: 211, depth: 3},
  ...
  { id: 3, depth: 1},
  { id: 31, depth: 2},
  { id: 311, depth: 3},
  ...
]

但我希望它自动按深度排序，如下所示：

[
  { id: 0, depth: 0},
  { id: 1, depth: 1},
  { id: 2, depth: 1},
  { id: 3, depth: 1},
  { id: 4, depth: 1},
  ...
  { id: 11, depth: 2},
  { id: 12, depth: 2},
  { id: 13, depth: 2},
  ...
  { id: 111, depth: 3},
  { id: 211, depth: 3},
  ...
]

我想去元素深度，即深度0的所有元素，然后深度1的所有元素，依此类推。

我的实现不尊重深度顺序。它只是简单地跟随分支，尽可能深入，然后移动到下一个分支。

我知道我可以稍后对其进行排序，但其他问题阻止我这样做。主要是我有重复的项目，我想把它们过滤掉。在过滤时，我想保留深度最低的项目。我的方法不允许这样做，因为它不会首先遍历所有最低深度的元素。

我怎样才能遍历这棵树的深度而不是分支？

标签： javascriptarraysbreadth-first-searchtree-traversal

Answer 1

找到了解决方案。显然这是一个广度优先搜索，需要维护一个队列：

function traverse(user) {
  const queue = [];
  const list = [];
  queue.push({ followers: user.followers, depth: 0 });

  let item;
  while (item = queue.shift()) {
    const { followers, depth } = item;
    for (const follower of followers) {
      if (list.find(l => l.id === follower.id)) continue;
      list.push({ id: follower.id, depth });
      queue.push({ followers: follower.followers, depth: depth + 1 });
    }
  }

  return list;
}