Binärbaum ohne Überlappung zeichnen

[MyPiano]

Hallo,

ich habe eine Klasse geschrieben, die einen Binärbaum erzeugt. Das klappt alles prima. Das ganze möchte ich jetzt noch visualisieren, also als Grafik ausgeben. Die Grundstruktur sieht gut aus, nur leider überlappen sich einige Knoten (siehe Bild im Anhang).

Meine Methode zum zeichnen sieht bisher wie folgt aus:

public class BinaryTree {

    private Integer content = null;
    private BinaryTree left = null;
    private BinaryTree right = null;

   //....

      public void drawBinaryTree(Graphics painter, int x, int y) {
        if (content != null) {
            painter.drawRect(x, y, 40, 30);
            painter.drawString(Integer.toString(content), x + 7, y + 21);
            painter.drawLine(x + 20, y + 30, x - 65, y + 50);
            painter.drawLine(x + 20, y + 30, x + 100, y + 50);
            if (left != null) {
                //  painter.drawRect(x-85, y+50, 40, 30);
                left.drawBinaryTree(painter, x - 85, y + 50);
            } else {
                painter.drawRect(x - 85, y + 50, 40, 30);
                painter.drawString("Null", x - 78, y + 71);
            }
            if (right != null) {
//                painter.drawRect(x+80, y+50, 40, 30);
                right.drawBinaryTree(painter, x + 80, y + 50);
            } else {
                painter.drawRect(x + 80, y + 50, 40, 30);
                painter.drawString("Null", x + 87, y + 71);
            }
        } else {
            painter.drawRect(x, y, 40, 30);
            painter.drawString("Null", x + 7, y + 21);
        }
    }
}

Hat jemand eine Idee, wie ich diesen Fehler beheben kann?

Viele Grüße

MyPiano

 

[Marco13]

Im wesentlichen würden mir da zwei Möglichkeiten einfallen:
1. Entweder die oberen Knoten weiter auseinander zeichnen als die Unteren oder
2. Die unteren dichter zusammen zeichnen als die oberen
Alles weitere würde vmtl. auf irgendwelche "komplexeren" Baumlayoutalgorithmen rauslaufen

 

[slawaweis]

ich habe eine Klasse geschrieben, die einen Binärbaum erzeugt. Das klappt alles prima. Das ganze möchte ich jetzt noch visualisieren, also als Grafik ausgeben. Die Grundstruktur sieht gut aus, nur leider überlappen sich einige Knoten (siehe Bild im Anhang).

...

Hat jemand eine Idee, wie ich diesen Fehler beheben kann?

der schnellste Weg wäre sich ein TreeModel abzuleiten und das ganze in einen JTree zu werfen, wo man dann alle Knoten expandiert. So muss man such nicht um die Grafik kümmern, höchstens um einen CellRenderer.

Der harte Weg führt über den folgenden Algorithmus. Zuerst wird der Baum in eine Zeilenform überführt, alle Knoten in einer Ebene werden zu einer Zeile zusammengefasst. D.h. der Wurzelknoten ist in der ersten Zeile, die Kinder des Wurzelknoten in der zweiten, die Kindeskinder in der dritten und so weiter. So könnte es am Ende aussehen:

 Object [][] zeilen_darstellung = {

  {root},
  {root_lkind, root_rkind},
  {root_lkind_lkind, root_lkind_rkind, root_rkind_lkind, root_rkind_rkind},
  // ...
 };

jetzt muss man den Baum nur noch Zeile für Zeile zeichnen und dabei die Abstände zwischen den Konten anhand einer Zeile ausrechnen.

Slawa

 

[MyPiano]

Hallo ihr beiden,

vielen dank für eure Tipps. Ich denke, ich werde den ersten Tipp ausprobieren, da er am einfachsten ist und für meine Zwecke völlig ausreicht.

Viele Grüße

MyPIano