二叉树级序遍历 [英] Level-order traversal of a binary tree

问题描述

我想执行一个二叉树层次序遍历。因此，对于一个给定的分类，说：

I want to perform level-order traversal of a binary tree. Hence, for a given tree, say:

     3
    / \
   2   1
  / \   \
 4   6   10

输出是：

3 2 1 4 6 10

据我所知，我可以用某种队列，但什么是算法来做到这在C递归？任何帮助AP preciated。

I understand that I could use some sort of queue, but what is the algorithm to do this in C recursively? Any help appreciated.

推荐答案

图形算法称为广度优先搜索，它使用一个队列来执行层面序遍历，这里是伪code

The graph algorithm is called Breadth First Search, it uses a queue to perform the level-order traversal, here is the pseudo-code

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

这篇关于二叉树级序遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！