c - 您将如何按行打印二叉树？

Question

我刚开始学习二叉树。我试图弄清楚如何按行打印二叉树的值。

例子:

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

将输出:

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

假设您获得了根节点。感谢您花时间提供帮助。

Answer 1

基本上是一个BFS (breadth first search)会做要求的。它的另一个名字是level-order-traversal。之所以叫层序遍历，是因为它层层遍历。

例如，对于您的二叉树，级别是:

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

另一个约定是级别从 1 开始。现在因为 BFS 遍历树 level by level

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