c - 二叉树的层序遍历

Question

我想执行二叉树的层序遍历。因此，对于给定的树，说:

     3
    / \
   2   1
  / \   \
 4   6   10

输出将是:

3 2 1 4 6 10

我知道我可以使用某种队列，但在 C 中递归执行此操作的算法是什么？任何帮助表示赞赏。

Answer 1

该图算法称为广度优先搜索，它使用队列进行层序遍历，这是伪代码

void breadth_first(Node root)
{
  Queue q;
  q.push(root);
  breadth_first_recursive(q)
}

void breadth_first_recursive(Queue q)
{
  if q.empty() return;
  Node node = q.pop()
  print Node
  if (n.left) q.push(n.left)
  if (n.right) q.push(n.right)
  breadth_first_recursive(q)
}