Baum erzeugen

[regtan]

Ich hatte auch die = weg gemacht aber trotzdem ohne Erfolg

 

[JStein52]

Wenn ichs richtig sehe, müsset nur die Schleifenbedingung von <= zu < geändert werden

Stimmt. Und natürlich return null wenn depth == 0 ist.

 

[JStein52]

Mhmmm,, was bedeutetdas denn immer bei den Tests:

returnsCorrectTreeForDepthTen

Ist das dann ok oder falsch ??😉

 

[regtan]

früher war falsch aber jetzt nicht mehr 🙂

 

[mrBrown]

returnsCorrectTreeForDepthTen

ist nur der TestName 😛

 

[Lazyyy]

Schon ein bisschen her das Thema:

Versuch ansonsten mal das:

public static ThreeNode createThree(int depth) {
        if (depth <= 0) {
            return null;
        }
    
        ThreeNode node = new ThreeNode();
        node.left = createThree(depth-1);
        node.middle = createThree(depth-1);
        node.right = createThree(depth-1);
    
        return node;
    }

Habe eine ähnliche aufgabe welche ich so Lösen kann .. wäre es möglich diese Lösung Schrittweise erläutert zu bekommen ?
was stellt hier die rekursion schritt für schritt an ^^?

 

[mrBrown]

Habe eine ähnliche aufgabe welche ich so Lösen kann .. wäre es möglich diese Lösung Schrittweise erläutert zu bekommen ?
was stellt hier die rekursion schritt für schritt an ^^?

Ich versuchs mal...

public static ThreeNode createThree(int depth) {
        if (depth <= 0) { //wenn die zu erzeugende Tiefe 0 ist (also gar kein Baum erzeugt werden soll)
            return null;     // dann wird kein Baum zurückgegeben
        }
   
        //ansonsten:
        ThreeNode node = new ThreeNode(); //erstelle die Wurzel für den Baum
        node.left = createThree(depth-1);     //füllen den rechten Teil-baum. Dieser ist auch einfach nur ein Baum, nur mit geringerer Tiefe (einfach mal aufmalen, dann sieht man das 
        node.middle = createThree(depth-1); //gleiches für die anderen beiden Teilbäume
        node.right = createThree(depth-1);
   
        return node;
    }

 

[Blender3D]

ThreeNode node = new ThreeNode(); //erstelle die Wurzel für den Baum

Hier wird nicht nur die Wurzel erzeugt, sondern jeder Knoten des Baumes.

was stellt hier die rekursion schritt für schritt an ^^?

Ich habe dir eine levelweise Printfuktion geschrieben, um den Baum zu visualisieren.

import java.util.Vector;

public class TreeNode {
    private final int value;
    private TreeNode left;
    private TreeNode middle;
    private TreeNode right;

    public TreeNode(int value) {
        this.value = value;
    }

    public TreeNode getLeft() {
        return left;
    }

    public TreeNode getMiddle() {
        return middle;
    }

    public TreeNode getRight() {
        return right;
    }

    public int getValue() {
        return value;
    }

    private static void getTreeStrings(TreeNode node, int level, Vector<String> str) {
        if (node == null)
            return;
        int size = str.size();
        String nodePrt = level < size ? str.get(level) : "Level " + level + "\t> ";
        nodePrt += node + "\t";
        if (level >= size)
            str.add(nodePrt);
        else
            str.set(level, nodePrt);
        if (node != null) {
            if (node.getLeft() != null)
                getTreeStrings(node.getLeft(), level + 1, str);
            if (node.getMiddle() != null)
                getTreeStrings(node.getMiddle(), level + 1, str);
            if (node.getRight() != null)
                getTreeStrings(node.getRight(), level + 1, str);
        }
    }

    /**
     * Prints tree in level order.
     *
     * @param node
     */
    public static void printTree(TreeNode node) {
        Vector<String> str = new Vector<String>();
        getTreeStrings(node, 0, str);
        for (String s : str)
            System.out.println(s);
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public void setMiddle(TreeNode middle) {
        this.middle = middle;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "[" + value + "]";
    }
}

public class start {
    public static int cnt = 0; // Counter um die Knoten zu Numerieren

    public static void main(String[] args) {
        TreeNode root = createThree(3);
        TreeNode.printTree(root); // gibt den erzeugten Baum levelweise aus
    }

    public static TreeNode createThree(int depth) {
        if (depth <= 0) // Wenn die Tiefe 0 ist, ist die gewünscht Höhe des Baumes erreicht und es wird
            return null; // kein weiterer Knoten erzeugt.

        // Erstelle den aktuellen Knoten. Falls depth gleich dem Wert des Aufrufers
        // außerhalb der Rekursion ist ( hier 3 ), handelt es sich um die Wurzel
        TreeNode node = new TreeNode(cnt++); // aktueller Knoten wird mit einer laufen Nummer versehen

        // setze die Knoten für alle Äste ( links, mitte ,rechts ) durch den rekursiven
        // Aufruf mit einer um 1 verminderten Tiefe. Das geschieht für jeden Ast solange
        // bis die obige Abruchbedigung Tiefe <= 0 erreicht ist.
        node.setLeft(createThree(depth - 1)); // setzte die Verbindung nach Links
        node.setMiddle(createThree(depth - 1)); // setzte die Verbindung zur Mitte
        node.setRight(createThree(depth - 1));// setzte die Verbindung nach Rechts

        return node; // Gib den aktuell erzeugten Konten zurück. Bei der Rückkehr zum urprünlichen
                        // Aufrufer handelt es sich dann um die Wurzel.
    }
}

Die Ausgabe:

Hier wurde die Funktion

createTree ()

13 x aufgerufen. Jedes Level das noch nicht die gewünschte Höhe erreicht hat erzeugt ein tieferliegendes Level mit 3 mal soviel Knoten. ( Links, Mitte, Rechts ). Man kann auch sehr gut sehen, wie die Knoten sich den Levels zuordnen. 🙄

Vielleicht hilft Dir das etwas weiter, um die Rekursion zu verstehen. 😉

 

[mrBrown]

Hier wird nicht nur die Wurzel erzeugt, sondern jeder Knoten des Baumes.

Da jeder Knoten eines Baumes auch gleichzeitig Wurzel des Teilbaumes ist, und da immer nur ein Teilbaum erzeugt wird, wird da auch immer die Wurzel erzeugt. Und in dem Methodenkontext ist nie bekannt, ob es Wurzel des Gesamtbaumes ist, oder nicht 😉

 

[Meniskusschaden]

Hier wird nicht nur die Wurzel erzeugt, sondern jeder Knoten des Baumes.

Das ist ja kein Widerspruch, denn es ist immer die Wurzel des Baumes, der mit diesem Aufruf von createTree() erzeugt wird. Wenn dieser Baum gleichzeitig Teilbaum eines übergeordneten Baumes ist, ist es aus dessen Sicht natürlich ein untergeordneter Knoten, bleibt aber dennoch die Wurzel des Teilbaums.

 

[Blender3D]

Und in dem Methodenkontext ist nie bekannt, ob es Wurzel des Gesamtbaumes ist, oder nicht

Stimmt 🙂. Aber irreführend für jemanden der die Rekursion noch nicht versteht. Von daher ist die Bezeichnung aktueller Knoten besser gewählt.

 

[Lazyyy]

Vielen Dank für die Antworten.
Bin das Ganze mit einem Blatt Papier zusätzlich noch einmal durch gegangen und eigtl lässt es sich gut nachvollziehen. Mal sehen ob ich die Rekursion auf ähnliche aufgaben übertragen kann.
Ansonsten schreibe ich hier noch einmal rein ^^.