Rekursive Ausgabe eines Binärbaums

R

Rekursion

Gast
Hallo!

Ich würde gerne einen Binärbaum auf der Konsole ausgeben. Ich möchte dazu gern eine rekursive Lösung benutzen.

Wichtig ist es, dass dieser auch so aussieht wie man ihn aus der Lektüre kennt, also in Form der Baumstruktur.

Mein erster Gedanke ist folgender:

Ich übergebe einer Methode printTree den Wurzelknoten (also den obersten Knoten). Und dieser hangelt sich jetzt links und rechts den Baum hinunter. Dabei wird der Methode immer wieder aufs neue der nächste Knoten übergeben.

Mein Problem ist nun:
Die jeweiligen Knoten müssen auf gleicher Ebene sein, dazu kommt noch, dass der ein oder andere Knoten ja nicht unbedingt da sein muss.
Also auf erster Ebene gibt es einen Knoten, dann höchstens 2, dann höchstens 4, dann höchstens 8 usw.

Ich hab hier leider nicht so ganz den Ansatz. Gestehe auch, dass die Rekursion mir schon immer den Kopf verdreht hat und ich mich schwer tue die Funktionsweise nachzuvollziehen.

Für Vorschläge wäre ich dankbar.

Danke
 
M

Marcinek

Gast
Hi,

auf der Konsole ist das schwer. Du musst erst die Breite bestimmen dafür musst du schon mal einmal rauf und runter.

Die breiteste Stelle bestimmen. Dann nochmal runter und die Elemente entsprechend Positionieren.

Dafür übergibst du immer die Tiefe an die nächste Rekursion.
 
André Uhres

André Uhres

Top Contributor
Wir können den Baum rekursiv durchlaufen und eine Liste der Knoten erstellen:
Java:
private void getNodeList(final Node node) {
    list.add(node);
    SortedSet<Node> children = node.getChildren();
    for (Node child : children) {
        if (child.getChildren().isEmpty()) {
            list.add(child);
        } else {
            getNodeList(child);
        }
    }
}
Dann können wir diese Liste Ebene für Ebene abarbeiten und ausdrucken:
Java:
for (int level = 0; level <= maxLevel; level++) {
    int x = 0;
    int y = 0;
    for (Node node : list) {
        int nodeLevel = node.getLevel();
        if (nodeLevel == level) {
            Rectangle bounds = node.getBounds();
            if (bounds.y != y) {
                System.out.println("");
                y = bounds.y;
                x = 0;
            }
            for (; x < bounds.x; x++) {
                System.out.print(" ");
            }
            System.out.print(node);
            x += node.getText().length();
        }
    }
    System.out.println("");
}
Vorher müssen wir natürlich die "bounds" der Knoten noch ausbalancieren, was wiederum rekursiv geschieht:
Java:
/**
 * balance the subtree on x axis
 */
public void balanceX() {
    if (children.size() > 0) {
        int childrenWidth = childrenWidth();
        int middleX = bounds.x + bounds.width / 2;
        int leftX = middleX - childrenWidth / 2;
        for (Node node : children) {
            int rowWidth = node.childrenWidth();
            if (rowWidth < bounds.width) {
                rowWidth = bounds.width;
            }
            int balX = (leftX + rowWidth / 2) - node.getBounds().width / 2;
            node.getBounds().x = balX;
            node.balanceX();
            leftX = leftX + rowWidth + dist.x;
        }

    }
}

/**
 * balance the subtree on y axis
 */
public void balanceY() {
    balanceY(bounds.height);
}

private void balanceY(final int height) {
    int childHeight = 0;
    int balY = bounds.y + height + dist.y;
    for (Node node : children) {
        if (node.getBounds().height > childHeight) {
            childHeight = node.getBounds().height;
        }
    }
    for (Node node : children) {
        node.getBounds().y = balY;
        node.balanceY(childHeight);
    }
}

private int childrenWidth() {
    int width = 0;
    for (Iterator<Node> it = children.iterator(); it.hasNext();) {
        Node node = it.next();
        int rowWidth = node.childrenWidth();
        if (rowWidth < bounds.width) {
            rowWidth = bounds.width;
        }
        width += rowWidth;
        if (it.hasNext()) {
            width += dist.x;
        }
    }
    return width;
}

Gruß,
André
 
R

Rekursion

Gast
Oha, das sieht ja alles andere als "mal eben eine Ausgabe machen" aus.

Danke schon mal für deine Mühe André Uhres.
Eine einfachere Möglichkeit gibt es nicht?
Nichts gegen den Code, aber für eine "einfache" Ausgabe sieht das alles recht kompliziert aus.
 
André Uhres

André Uhres

Top Contributor
für eine "einfache" Ausgabe sieht das alles recht kompliziert aus.
Der erste Code kann entfallen, wenn schon eine Liste der Knoten besteht. Die Ausgabe ist eigentlich nur der mittlere Code (kann eventuell noch optimiert werden, hat aber nichts mit Rekursion zu tun). Der Code für das Ausbalancieren ist auch für grafische Ausgaben geeignet, also unverändert wiederverwendbar! Im Übrigen darf eine komplizierte Struktur wohl auch mal eine komplizierte Verarbeitung verlangen, nicht wahr?

Gruß,
André
 
Zuletzt bearbeitet:
Ähnliche Java Themen
  Titel Forum Antworten Datum
B Datentypen Suchbaum - Rekursive Ausgabe Java Basics - Anfänger-Themen 1
D rekursive ausgabe einer zahl Java Basics - Anfänger-Themen 14
veryck Methoden Rekursive Methoden mit Rückgabeparameter Java Basics - Anfänger-Themen 9
macle Rekursive String Methode, Gerade Zahlen rausfiltern Java Basics - Anfänger-Themen 10
M Rekursive Prüfung ob ein Array sortiert ist... Java Basics - Anfänger-Themen 4
J Rekursive swapArray Methode Java Basics - Anfänger-Themen 69
D Rekursive Methode Java Basics - Anfänger-Themen 8
R Methoden rekursive Methoden Java Basics - Anfänger-Themen 6
O Quersumme rekursive Methode Java Basics - Anfänger-Themen 3
B Treetable (rekursive Funktion) aufbauen von Datenbank Java Basics - Anfänger-Themen 4
M Rekursive Methode Programmieren Java Basics - Anfänger-Themen 3
J rekursive Methode Java Basics - Anfänger-Themen 26
M rekursive division/0 mit exception Java Basics - Anfänger-Themen 18
J Rekursive Methode - Ziffern einer Zahl ausgeben Java Basics - Anfänger-Themen 2
M Rekursive Dateiliste erstellen mit Dateiendung(en) ?? Java Basics - Anfänger-Themen 4
S Rekursive Methode Java Basics - Anfänger-Themen 8
O Rekursive Methode Java Basics - Anfänger-Themen 4
V Methoden Rekursive Methode mit String als Rückgabe Java Basics - Anfänger-Themen 7
K Rekursive Methode Java Basics - Anfänger-Themen 1
K Rekursive Methode für Fakultät mit BigInteger Java Basics - Anfänger-Themen 10
L Rekursive Methode a * b berechnen Java Basics - Anfänger-Themen 2
L Rekursive Methode zur Berechnung der Potenz q hoch p Java Basics - Anfänger-Themen 17
J Methoden Rekursive Return Methode Java Basics - Anfänger-Themen 2
G Harmonische Rekursive Folge Java Basics - Anfänger-Themen 3
T Stack Overflow - Rekursive Fibonacci Java Basics - Anfänger-Themen 10
P Methoden Rekursive Methode für Potenzen Java Basics - Anfänger-Themen 2
M Methoden Binäre Suche als rekursive Variante Java Basics - Anfänger-Themen 5
B Rekursive Algorithmus schreiben Java Basics - Anfänger-Themen 8
S Eine rekursive Lösung Java Basics - Anfänger-Themen 4
S Int zu Hexadezimal - Rekursive Methode Java Basics - Anfänger-Themen 2
M Rekursive Suche in einem Feld Java Basics - Anfänger-Themen 11
N Rekursive Addition mit Scanner Java Basics - Anfänger-Themen 12
shiroX OOP Rekursive und Iterative Definition Java Basics - Anfänger-Themen 2
B Methoden Rekursive Methoden Java Basics - Anfänger-Themen 2
T Iterative Pi Berechnung in Rekursive Java Basics - Anfänger-Themen 2
C rekursive methode Java Basics - Anfänger-Themen 2
D Methoden Rekursive Methoden Java Basics - Anfänger-Themen 13
R rekursive Methode funktioniert nicht Java Basics - Anfänger-Themen 4
M Stürzen alle Rekursive Methoden irgendwann ab? Java Basics - Anfänger-Themen 11
D Primzahlen und Rekursive Liste Java Basics - Anfänger-Themen 29
R Rekursive Methode, Files finden Java Basics - Anfänger-Themen 2
S rekursive folge verbessern Java Basics - Anfänger-Themen 2
C rekursive Methode verstehe nicht! Java Basics - Anfänger-Themen 3
S Methoden rekursive Methode funktioniert nicht Java Basics - Anfänger-Themen 4
E Rekursive Methode Java Basics - Anfänger-Themen 3
N Methoden Rekursive Fibonaccizahlen mit Array Java Basics - Anfänger-Themen 2
J Methoden Rekursive Potenz ohne Math.Pow() Java Basics - Anfänger-Themen 9
A Rekursive Methode in Iterative umwandeln Java Basics - Anfänger-Themen 6
S Labyrith Rekursive Wegsuche Java Basics - Anfänger-Themen 4
C Rekursive Methode - Ziffern in Zahl Java Basics - Anfänger-Themen 33
U Dezimal zu Hexadezimal rekursive Funktion Java Basics - Anfänger-Themen 8
M rekursive Funktion zur Berechnung der Spiegelzahl Java Basics - Anfänger-Themen 7
L iterative und rekursive Folge Java Basics - Anfänger-Themen 20
G Rekursive Methode Java Basics - Anfänger-Themen 3
A rekursive Listen in Java? Java Basics - Anfänger-Themen 5
B OOP Einfach verkettete Liste - rekursive Methoden Java Basics - Anfänger-Themen 1
E Rekursive Methode mit Zufallsarray Java Basics - Anfänger-Themen 6
E Rekursive Methode Java Basics - Anfänger-Themen 18
U Rekursive lösung von pascal dreieck Java Basics - Anfänger-Themen 11
M Rekursive Methode - wo ist der Fehler? Java Basics - Anfänger-Themen 4
J rekursive methode Java Basics - Anfänger-Themen 6
H ScrollBar inaktiv / Rekursive Methode Java Basics - Anfänger-Themen 4
J Rekursive Methode Java Basics - Anfänger-Themen 11
G Rekursive Methode Java Basics - Anfänger-Themen 5
N Rekursive Berechnung der Höhe eines binären Baumes Java Basics - Anfänger-Themen 4
K Rekursive Methoden Java Basics - Anfänger-Themen 15
K Rekursive Funktion (Verständnissfrage) Java Basics - Anfänger-Themen 5
S Rekursive Bruch potenzierung Java Basics - Anfänger-Themen 2
D rekursive Summenberechnung Java Basics - Anfänger-Themen 8
J Rekursive Methode: Fakultaet berechnen Java Basics - Anfänger-Themen 5
E Rekursive definierten Folge Java Basics - Anfänger-Themen 10
A HILFE! Rekursive Funktion Java Basics - Anfänger-Themen 20
kulturfenster rekursive Binaere Suche Java Basics - Anfänger-Themen 12
F Rekursive Aufrufe, Parameterübergabe, call by reference Java Basics - Anfänger-Themen 3
G Rekursive Berechnung von n über k schlägt fehl Java Basics - Anfänger-Themen 5
B Rekursive & schreiben im ArrayList Java Basics - Anfänger-Themen 2
J Rekursive Fkt. Java Basics - Anfänger-Themen 2
A Rekursive Dateisuche Java Basics - Anfänger-Themen 12
K rekursive Funktion mit mehreren Parametern Java Basics - Anfänger-Themen 5
G rekursive Methode Java Basics - Anfänger-Themen 3
N rekursive Beispiele Java Basics - Anfänger-Themen 3
G rekursive u iterative Methode Java Basics - Anfänger-Themen 8
G Rekursive Methode Java Basics - Anfänger-Themen 7
ven000m Rekursive Funktionen - Frage Java Basics - Anfänger-Themen 16
S Rekursive Funktionen in imperative Funktionen umwandeln Java Basics - Anfänger-Themen 2
M Rekursive Binärsuche Java Basics - Anfänger-Themen 6
S rekursive methoden Java Basics - Anfänger-Themen 5
V Multiplikationstafel - Ausgabe Java Basics - Anfänger-Themen 4
L Warum ist die Ausgabe anders als das was im Bezeichner steht? Java Basics - Anfänger-Themen 4
M In gleicher zeile hinter ausgabe noch etwas ausgeben Java Basics - Anfänger-Themen 1
newcomerJava Nach doppelter Zahl eine Ausgabe Java Basics - Anfänger-Themen 10
H Falsche Ausgabe Java Basics - Anfänger-Themen 2
P Klassenübergreifende Ausgabe mittels "getter" nicht möglich Java Basics - Anfänger-Themen 21
R Call-by-Value, Call-by-Reference, Call-by-Name Ausgabe Java Basics - Anfänger-Themen 1
JavaClap "Bruchrechner" liefert Fehler/keine Ausgabe bei Addition und Subtraktion Java Basics - Anfänger-Themen 0
D Warum erfolgt folgende Ausgabe und warum? Java Basics - Anfänger-Themen 4
C Ausgabe in der Konsole Java Basics - Anfänger-Themen 11
M Problem bei Ausgabe Java Basics - Anfänger-Themen 7
C Konvertierung des int typs in den double typ für die Ausgabe mit Nachkommastellen Java Basics - Anfänger-Themen 4
A Ausgabe mit boolean Java Basics - Anfänger-Themen 3

Ähnliche Java Themen

Anzeige

Neue Themen


Oben