如何按二叉树的行打印二叉树？

Question

我刚开始学习二叉树。我试图找出如何通过二叉树的行来打印二叉树的值。

示例：

             .-------(098)-------.
      .--(012)--.         .--(402)--.
   (006)     (056)      (256)     (512)

将产出：

 >98
 >12
 >402
 >6
 >56
 >256
 >512

假设您获得了根节点。谢谢你抽出时间来帮忙。

Answer 1

基本上，BFS (breadth first search)将完成所需的操作。它的另一个名字是level-order-traversal。之所以被称为水平顺序遍历，是因为它遍历了树level by level。

例如，对于二叉树，级别为：

           .-------(098)-------.                  //level 0
      .--(012)--.         .--(402)--.             //level 1
   (006)     (056)      (256)     (512)           //level 2

另一个惯例是这个级别从1开始。

First 098 is visited and we are done with level 0

Then 012 and 402 is visited and we are done with level 1

Then 006 , 056 , 256 , 512 are visited and we are done with level 2

BFS不仅仅是针对二叉树的，它基本上是一个graph traversal algorithm，因为树只不过是一个没有循环连接的图，所以我们也可以将它用于树。

根据所使用的数据结构，时间和空间复杂性各不相同：

如果使用adjacency matrix来表示图形，那么：

时间复杂度：O(V^2)和空间复杂度：O(V^2)

如果使用adjacency list来表示图形，那么：

时间复杂度：O(V + E)和空间复杂度：O(V + E)

以下是可以很容易转换为代码的BFS伪代码：

BFS(source vertex v)
{
 Enque(v)
 Mark v as visited.
 While(Q is not empty)
  {
    Vertex v’ = deque(Q)
    For all adjacent vertices of v’ that are not visited
     {  Enque them and mark them as visited  }
    We are done with vertex v’
  }
}