C So „zeichnen“ Sie einen Binärbaum auf die Konsole [geschlossen]

70

Welche Algorithmen können verwendet werden, um einen Binärbaum in der Konsole zu zeichnen? Der Baum ist in C implementiert. Beispielsweise würde eine BST mit den Nummern: 2 3 4 5 8 in der Konsole wie folgt angezeigt:

Alt-Text

Marek Szanyi
quelle
2
Erstellen Sie eine Punktdatei mit Ihren Knoten und Kanten und rendern Sie sie mit graphviz. Sieht ordentlich aus
Johannes Schaub - litb
@litb: schön. Ich habe tatsächlich eine Renderliste und einen Framebuffer implementiert und meine eigenen BMPs generiert!
Bitte Bild aktualisieren :)
Andreas Storvik Strauman

Antworten:

46

Schauen Sie sich das Drucken von Binärbäumen in Ascii an

Von @AnyOneElse Pastbin unten:

Ausgabe:

Jonas Elfström
quelle
Genau das, wonach ich gesucht habe, vielen Dank!
Marek Szanyi
2
Leider scheint es so. Es konnte nicht im Google Cache oder auf dem Internet Archive Wayback-Computer gefunden werden. Das könnte es sein, ich habe noch nicht versucht, es auszuführen: datastructuresblog.wordpress.com/2007/12/21/…
Jonas Elfström
Der Text scheint beschädigt zu sein und der Code-Link ist defekt. Wenn jemand den Code finden kann, helfen Sie bitte! Ein Link zu Pastebin ist möglicherweise nicht falsch ...
Norman Ramsey
1
Ich habe dies vor ein paar Jahren auf JS portiert. Github.com/gaastonsr/treevis
Gaston Sanchez
48

Code:

Ausgabe:

oder

user1571409
quelle
7
+1 für die SCHÖNHEIT der rekursiven Implementierung und der Ausgabe.
OnTheEasiestWay
Ich habe versucht, dies mit einem Baum mit Zeichenfolgenwerten zu verwenden. Hat nicht wirklich gut funktioniert, auch wenn die Breitenvariable erhöht wurde. Auch die festgelegte Anzahl von Zeilen ist unglücklich.
Ray Hulha
20

Einige Hinweise: Der Abstand zwischen Knoten in derselben Tiefe (z. B. 2 und 4 oder 3 und 8 in Ihrem Beispiel) ist eine Funktion der Tiefe.

Jede gedruckte Zeile besteht aus allen Knoten mit derselben Tiefe, die vom Knoten ganz links bis zum Knoten ganz rechts gedruckt werden.

Sie benötigen also eine Möglichkeit, Ihre Knoten beispielsweise in Reihenarrays entsprechend ihrer Tiefe in der Reihenfolge ihrer Entfernung ganz links anzuordnen.

Ausgehend vom Wurzelknoten werden bei einer Breitensuche Knoten in der Reihenfolge der Tiefe und der am weitesten links liegenden Knoten besucht.

Der Abstand zwischen Knoten kann ermittelt werden, indem die maximale Höhe des Baums ermittelt, eine konstante Breite für die tiefsten Knoten verwendet und diese Breite für jede geringere Tiefe verdoppelt wird, sodass die Breite für jede Tiefe = (1 + maxdepth - currentdepth) * deepestwidth ist .

Diese Zahl gibt Ihnen die gedruckte "horizontale Breite" jedes Knotens in einer bestimmten Tiefe.

Ein linker Knoten horizontal positioniert in der linken Hälfte der Mutterbreite, ein righ Knoten in der rechten Hälfte. Sie fügen Dummy-Abstandhalter für jeden Knoten ein, der keine Eltern hat. Ein einfacher Weg, dies zu tun, wäre sicherzustellen, dass sich alle Blätter in der gleichen Tiefe wie der tiefste Knoten befinden und der Wert leer ist. Natürlich müssen Sie auch die Breite der Werte kompensieren, indem Sie die Breite der größten Tiefe mindestens so breit machen wie die gedruckte (vermutlich dezimale Darstellung) des Knotens mit dem größten Wert.

tpdi
quelle
12

Hier ist noch eine Einstellung, wenn ein Baum in einem Array implementiert ist:

Ausgabe:

Bula
quelle
8

Ich habe diese kleine Lösung in c ++ - sie könnte leicht in c konvertiert werden.

Meine Lösung erfordert eine zusätzliche Datenstruktur, um die Tiefe des aktuellen Knotens im Baum zu speichern (wenn Sie mit einem unvollständigen Baum arbeiten, stimmt die Tiefe eines bestimmten Teilbaums möglicherweise nicht mit der Tiefe im vollständigen Baum überein.)

Folgendes wird gedruckt:

Steve Lorimer
quelle
Vielen Dank. Ich verwende Ihre Lösung, aber es liegt ein kleiner Fehler vor. Der zweite q.push_back (node_depth (nd.n-> l, last_lvl + 1)) sollte q.push_back (node_depth (nd.n-> r, last_lvl + 1)) sein
sank
@sank - nicht sicher , was Sie sprechen - es ist die Berechnung node_depthdes rechten Unterbaum bereits. Haben Sie es vorab falsch geschrieben, als Sie es kopiert haben? Arbeitscode
Steve Lorimer
3

Schauen Sie sich die Ausgabe des Befehls pstree unter Linux an. Die Ausgabe wird nicht genau in der gewünschten Form erstellt, aber meiner Meinung nach ist sie auf diese Weise besser lesbar.

Anonym
quelle
3

Ich stimme der Empfehlung von litb zu. Ich musste dies in letzter Zeit tun, um den VAD-Baum eines Windows-Prozesses zu drucken, und ich habe die DOT-Sprache verwendet (drucken Sie einfach Knoten aus Ihrer Binärbaum-Walking-Funktion aus):

http://en.wikipedia.org/wiki/DOT_language

Zum Beispiel würde Ihre DOT-Datei Folgendes enthalten:

digraph graphname {
     5 -> 3;
     5 -> 8;
     3 -> 4;
     3 -> 2;
}}

Sie generieren das Diagramm mit dotty.exe oder konvertieren es mit dot.exe in PNG.

Martin
quelle
Punkt ist fabelhaft, aber das Problem hier ist ASCII
Norman Ramsey
2

Ein sehr einfacher C ++ - Lösungsdruckbaum in horizontaler Richtung:

Code ( Node::print()Funktion ist wichtig):

cpp
quelle
1

Ich denke, Sie sollten das nicht selbst codieren, sondern sich Tree :: Visualize ansehen , das eine nette Perl-Implementierung mit verschiedenen möglichen Stilen zu sein scheint, und einen der dortigen Algorithmen verwenden / portieren.

Schnaader
quelle
1

Ich habe ein Ruby-Programm, das die Koordinaten berechnet, an denen jeder Knoten in einem Binärbaum gezeichnet werden soll: http://hectorcorrea.com/Blog/Drawing-a-Binary-Tree-in-Ruby

Dieser Code verwendet einen sehr einfachen Algorithmus zur Berechnung der Koordinaten und ist nicht "flächeneffizient", aber ein guter Anfang. Wenn Sie den Code "live" sehen möchten, können Sie ihn hier testen: http://binarytree.heroku.com/

Hector Correa
quelle
ASCII! Die Frage fragt nach ASCII.
Norman Ramsey
@Norman - ja, aber er fragt auch nach einem Algorithmus und er kann das auf dem Beitrag finden, den ich aufgelistet habe.
Hector Correa