c++ - 二叉树 - 根据级别打印元素

Question

这个问题是在面试中问我的:

假设我们有上面的二叉树，我怎样才能产生如下所示的输出

2 7 5 2 6 9 5 11 4

我的回答可能是我们可以有一个级别计数变量，并通过检查每个节点的级别计数变量按顺序打印所有元素。可能我错了。

谁能告诉我们如何才能做到这一点？

Answer 1

您需要对树进行广度优先遍历。 Here描述如下:

Breadth-first traversal: Depth-first is not the only way to go through the elements of a tree. Another way is to go through them level-by-level.

For example, each element exists at a certain level (or depth) in the tree:

    tree
      ----
       j         <-- level 0
     /   \
    f      k     <-- level 1
  /   \      \
 a     h      z  <-- level 2
  \
   d             <-- level 3

people like to number things starting with 0.)

So, if we want to visit the elements level-by-level (and left-to-right, as usual), we would start at level 0 with j, then go to level 1 for f and k, then go to level 2 for a, h and z, and finally go to level 3 for d.

This level-by-level traversal is called a breadth-first traversal because we explore the breadth, i.e., full width of the tree at a given level, before going deeper.