Rekursive Ausgabe eines Binärbaums

[Rekursion]

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

 

[Marcinek]

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]

Wir können den Baum rekursiv durchlaufen und eine Liste der Knoten erstellen:

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:

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:

/**
 * 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é

 

[Rekursion]

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]

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é