二叉树的层次顺序遍历

Question

我想对二叉树执行级别顺序遍历。因此，对于给定的树，说：

     3
    / \
   2   1
  / \   \
 4   6   10

产出将是：

3 2 1 4 6 10

我知道我可以使用某种队列，但在C中递归地实现这一点的算法是什么？感谢您的帮助。

Answer 1

这里是C5库中的代码（无递归函数）：C5 UserGuideExamples-TreeTraversal

public static void BreadthFirst(Tree<T> t, Action<T> action)
{
  IQueue<Tree<T>> work = new CircularQueue<Tree<T>>();
  work.Enqueue(t);
  while (!work.IsEmpty)
  {
    Tree<T> cur = work.Dequeue();
    if (cur != null)
    {
      work.Enqueue(cur.t1);
      work.Enqueue(cur.t2);
      action(cur.val);
    }
  }
}

Answer 2

这里是维基百科的伪代码

levelorder(root)
  q = empty queue
  q.enqueue(root)
  while not q.empty do
    node := q.dequeue()
    visit(node)
    if node.left ≠ null
    q.enqueue(node.left)
    if node.right ≠ null
    q.enqueue(node.right)

然后，您可以将其转换为C，这是微不足道的……

Answer 3

该图算法称为“宽度优先搜索”，它使用一个队列执行级别顺序遍历，这是伪代码

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