你會如何通過行打印二叉樹？

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從現在開始，因爲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用於表示隨後的圖表：

時間複雜度：Ö（V^2）和 空間複雜性：Ó（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’ 
    } 
}