Binärbaum formatiert ausgeben.

[jdnkr]

Ich knobel schon eine ganze Weile an einem Problem rum.
Ein Binärbaum soll erstellt werden und dann formatiert ausgegeben werden.
Das Erstellen ist auch kein Problem, nur bei der Ausgabe hapert es.

Soweit bin ich bis jetzt gekommen:

class Tree
{
    int wert ;
    Tree left, right ;
    Tree( int i, Tree l, Tree r ) { wert=i ; left=l ; right=r ; }
    void insert( int i )
    {      if ( i<=wert )
            if (left==null) left = new Tree( i , null , null ) ;
            else left.insert( i ) ;
        else
            if (right==null) right = new Tree( i , null , null ) ;
            else right.insert( i ) ;
    }
    void print()
    {
        if(right != null)
        {
            System.out.print("   ");
            right.print();
            System.out.println(wert);
        }
        if(left != null)
        {
            System.out.print("   ");
            left.print();
            System.out.println(wert);
        }
  }
}
public class P11
{
   public static void main( String[] args )
   {
    Tree t=new Tree( Integer.parseInt( args[0]), null, null ) ;
    for (int i=1; i<args.length ; i++)
        t.insert( Integer.parseInt( args[i])) ;
     t.print();
   }
}

Bei einer Eingabe von: java P11 4 5 1 7 7 3 9 4 1 2
sollte dann eine Ausgabe ungefähr so aussehen:

aber ich bekomme nur das hier:

Schon mal im Vorraus vielen dank für jede Hilfe.

 

[Meniskusschaden]

Ich sehe zwei Probleme. Zum Einen gibst du manche Werte gar nicht und manche doppelt aus. Da stimmen die Bedingungen noch nicht.
Zum Anderen verlierst du beim Ausgeben eines Wertes die Einrückung, weil es danach ja wieder am Zeilenanfang los geht. Du könntest beim Aufruf den gewünschten Abstand als Paramter übergeben und so rekursiv durchreichen. Vor dem Drucken des Wertes musst du dann nur noch in einer Schleife die entsprechende Anzahl von Leerzeichen ausgeben.

 

[kneitzel]

Also ein Algorithmus mit korrekter Einrückung ist nicht ganz so einfach zu realisieren. Die Einrückung, die notwendig ist, ist Abhängig von der Höhe des Teilbaums.
Und dann muss in eine Zeile ja Werte aus zwei Teilbäumen. Das ist nicht unmöglich, aber da müsste ich jetzt auch erst noch einen Algorithmus überlegen.

Was mir so durch den Kopf geht ist:
Die Print-Routine gibt immer ein String[] Array zurück.
Einen Baum auszugeben ist damit dann immer:
- linken und rechten Teilbaum drucken. Dadurch hat man dann zwei String[] arrays und damit auch die maximale höhe und ich würde evtl. sogar festlegen, dass jeder String die gleiche Länge hat.
==> So hat man dann die höhe und Breite der Teilbäume.
- den aktuellen Baum kann man dann ausgeben, indem man
a) Anzahl der Zeichen im linken Teilbaum - (Anzahl Ziffern Knoten / 2) + (Anzahl Zeichen Trenner / 2 ) an Leerzeichen + Zahl + ggf. Auffüllen Leerzeichen, so dass diese Zeile so lang ist, wie die anderen, die nun folgen werden.
b) Dann immer die Zeilen zusammenfügen: Linker Teilbaum + Trenner (z.B. " ") + rechter Teilbaum bzw. wenn die es einen Teilbaum nicht mehr gibt, dann halt Leerzeichen wie benötigt.
So hat man dann am Ende ein String[], das man ausgeben kann. Aber wirklich gut wird das nicht aussehen, denn ab einer bestimmten Größe sind die Zeichen recht weit voneinander entfernt. Evtl. trennt man die Teilbäume statt mit " " mit " || " oder so - dann hat man eine Trennung zwischen Teilbäumen.

 

[kneitzel]

Ach ja - Zwei Sonderfälle:
1) Keine Unterknoten: Da wird dann einfach ein String[] { wert.toString() } zurückgegeben.
2) Nur ein Unterknoten - da würde ich dann am Anfang die vorhandene Seite erstellen und dann würde ich die leere Seite durch Leerzeilen mit der gleichen Länge, wie es auf der anderen Seite war, füllen.

Also wenn rechts "123" war, dann würde ich links als " " sehen, so dass dann " || 123" als Ergebnis-Zeile erzeugen. Und da fällt schon etwas auf, dass || wohl nicht ganz so toll aussieht ... Was wir haben würden, wäre dann eine Ausgabe wie

   47
    || 123

Aber das muss man sich dann ansehen, wenn man es generieren läßt.

 

[jdnkr]

Danke für die Antworten! Ich werde mich morgen wohl nochmal dransetzten, vielleicht kommt mir ja noch ein Geistesblitz.

 

[Meniskusschaden]

Wenn ich den TE richtig verstanden habe, genügt es ihm, den Baum um 90 Grad gedreht auszugeben, also von links nach rechts statt von oben nach unten. Das ist deutlich einfacher (sieht aber wahrscheinlich nicht so toll aus). Das nur sicherheitshalber als Hinweis, damit die beiden Ansätze auseinander gehalten werden. Die "normale" Ausgabe von oben nach unten ist wirklich recht anspruchsvoll.

 

[kneitzel]

Um 90 Grad gedreht ist nicht viel einfacher meine Ich. Da müsste ich jetzt auch erst noch mehr nachdenken....

 

[Meniskusschaden]

Wenn eine rudimentäre Version ohne Verbindungslinien genügt, ist der Algorithmus vom TE schon fast fertig. Die print-Methode könnte dann ungefähr so aussehen:

void print(int offset) {
    if(right != null) {
        right.print(offset+GAP_SIZE);
    }
  
    for (int i=0; i<offset;i++) {
        System.out.print(" ");
    }
    System.out.println(wert);
  
    if(left != null) {
        left.print(offset+GAP_SIZE);
    }      
}