二叉树的级别顺序遍历

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)
}