Ich schlage vor, den Baum in einer Linie zu zeichnen. Dazu verwenden Sie eine Art beweglichen "Zeichencursor".
Sie könnten ein Attribut speichern width für jeden Knoten, die wie folgt berechnet wird:
- le site
width eines Urlaubs ist 1
- le site
width eines inneren Knotens ist die Summe der Werte aller untergeordneten width s
Dann zeichnet man die Wurzel "in der ersten Linie" in der Mitte, d.h. man nimmt einfach die Wurzel des width der Hälfte.
Dann erzeugt man ein Gitter über dem Bild, so dass jede Gitterlinie einer Zeile bzw. einem Schritt von links nach rechts entspricht und jeder Schnittpunkt von Gitterlinien einen Knoten enthalten kann und jeder Knoten genügend Platz hat.
Dann iterieren Sie durch die Kinder, und während der Iteration akkumulieren Sie die Werte der Kinder width s und zeichnen Sie die Kinder "in die nächste Zeile". Zum Zeichnen currentChild bewegen Sie Ihren Zeichencursor currentWidth/2 nach rechts, zeichnen currentChild und bewegen Sie den Zeichencursor um die restlichen currentWidth/2 nach rechts.
Um die Knoten in eine gute Reihenfolge zu bringen, könnten Sie eine Suche in der Breite in Betracht ziehen.
Ich hoffe, meine Erklärung ist klar, aber ich denke, es wird besser sein, wenn ich ein kleines Bild zeichne.
Dies ist unser Baum ( x sind Knoten, alles andere sind Kanten)
+-------x--+-------+
| | |
+-x-+ +-+x+-+ +-x-+
| | | | | | | | |
x x x x x x x x x
Sie berechnen also den Wert des Blattes width s:
+-------x--+-------+
| | |
+-x-+ +-+x+-+ +-x-+
| | | | | | | | |
1 1 1 1 1 1 1 1 1
Dann, von unten nach oben, die width s als Summen der Kinder width s:
+-------9--+-------+
| | |
+-2-+ +-+4+-+ +-3-+
| | | | | | | | |
1 1 1 1 1 1 1 1 1
Sie beginnen also an der Wurzel ( width 9) und gehen Sie 4,5 Schritte zur rechten Seite in der ersten Zeile.
Dann bewegen Sie Ihren "Zeichencursor" auf die zweite Zeile, "Spalte 0" (nach links).
Das erste Kind hat width 2, also gehen wir 2/2=1 Gitterlinien nach rechts, zeichnen Sie den Knoten und bewegen Sie den Zeichencursor die verbleibenden 1 Gitterlinien nach rechts, um den Knoten fertigzustellen. Der nächste Knoten hat also width 4, was bedeutet, dass wir 4/2=2 Gitterlinien nach rechts gehen, zeichnen, die restlichen 2 Schritte gehen, und so weiter.
Und so geht es weiter mit der nächsten Zeile. Verbinden Sie am Ende (oder in Zwischenschritten) die Knotenpunkte.
Dieses Verfahren stellt sicher, dass es keine sich überschneidenden Knoten gibt (wenn die Gitterlinien weit genug voneinander entfernt sind), aber es kann zu recht großen Baumdiagrammen führen, die den Platz effizienter nutzen könnten.
Um ungenutzten Raum zu erkennen, könnte man die Linien nach dem obigen Vorgang einfach scannen und nachsehen, ob es ungenutzte Gitterlinienkreuzungen gibt, und dann möglicherweise einige Knoten neu ausrichten, um den Raum zu füllen.
