Wie würden Sie einen binären Baum durch seine Zeilen drucken?

Question

Ich bin neu zu lernen über Binärbäume. Ich versuche herauszufinden, wie man die Werte eines binären Baumes durch seine Zeilen drucken kann.

Beispiel:

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

Will Ausgang:

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

Angenommen, Sie den Wurzelknoten angegeben. Danke, dass Sie sich die Zeit genommen haben, um zu helfen.

Answer 1

Grundsätzlich eine BFS (breadth first search) wird die erforderlichen tun. Sein anderer Name ist level-order-traversal. Der Grund dafür, dass es als "level order traversal" bezeichnet wird, ist, dass es den Baum level by level durchquert.

Zum Beispiel im Falle Ihrer binären Baum sind die Ebenen:

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

Die andere Konvention ist, dass Niveau von 1. Nun beginnt weil BFS den Baum 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 ist durchquert nicht nur für binäre Bäume gedacht, es ist im Grunde ein graph traversal algorithm, und weil ein Baum ist nichts anderes als ein Diagramm , die ohne Zyklus verbunden ist Wir können es auch für den Baum verwenden.

auf der Datenstruktur Je verwendet, um die Zeit und Raum Komplexität variiert:

Wenn adjacency matrix verwendet wird, um die Grafik zu repräsentieren, dann:

Zeitkomplexität: O (V^2) und Platzkomplexität : O (V^2)

Wenn adjacency list wird verwendet, um die Grafik zu repräsentieren, dann:

Zeitkomplexität: O (V + E) und Raum Komplexität: O (V + E)

Es folgt BFS Pseudo-Code, die leicht zu Code umgewandelt werden kann:

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