# Baum erzeugen



## regtan (27. Jun 2016)

Hallo, ich versuch ein trinären Baum zu erzeugen und muss die Methode "ThreeNode createThree(int depth)" implementieren. Es gelingt mir bis "CorrectTreeForDepthTwo"  aber nicht weiter. Wo könnte das Problem liegen? Das ist mein Code:

```
public static ThreeNode createThree(int depth) {


     ThreeNode root = new ThreeNode();
     while (depth != 0) {

     for (int i = 1; i < depth; i++) {
       ThreeNode knoten = new ThreeNode();

         root.setLeft(knoten);
         root.setMiddle(knoten);
         root.setRight(knoten);
       }
       return root;   
     }if(depth == 0) {

       return null;
     }

   return root;
}
```


----------



## Meniskusschaden (27. Jun 2016)

Ich weiß nicht, was du damit meinst:


regtan hat gesagt.:


> Es gelingt mir bis "CorrectTreeForDepthTwo" aber nicht weiter.


Du solltest vielleicht etwas mehr Code zeigen, denn so ist es nicht kompilierbar, weil mindestens die drei setXXX-Methoden fehlen.

Ausserdem solltest du für dein Programm mal einen Schreibtischtest machen, denn es gibt ziemlich viele Fehler, die du dadurch leicht finden kannst.

Folgende Fehler fallen mir auf:

Die Bedingung der while-Schleife ergibt keinen Sinn, denn depth ändert sich nicht, so dass die Schleife nur durch das return nach der for-Schleife verlassen werden kann.

Deshalb ist derzeit auch die if-Bedingung überflüssig, denn an die Stelle kann man ohnehin nur kommen, wenn depth == 0 ist.

Aus diesem Grund ist auch das nachfolgende return root überflüssig, denn es kann nicht erreicht werden.

Bei jeder Iteration der for-Schleife erzeugst du einen ThreeNode, den du als linken, mittleren und rechten Nachfolger setzt. Sollen die wirklich alle denselben ThreeNode enthalten?

Es bleibt nur der ThreeNode der letzten Schleifeniteration erhalten, denn die vorigen überschreibst du mit setLeft etc. wieder. Zumindest sofern setLeft das tut, was der Name nahe legt.


----------



## regtan (27. Jun 2016)

Die Methode soll einen vollständig balancierten, trinären Baum erzeugen (also alle Knoten, außer die der untersten Ebene haben alle drei Kindknoten). Der erzeugte Baum soll die in depth übergebene Tiefe haben. Als Rückgabewert wird der Wurzelknoten des neu erzeugten Baums erwartet.

```
public class ThreeNode {

   private ThreeNode left;
   private ThreeNode middle;
   private ThreeNode right;

   public ThreeNode left() {
     return left;
   }
   public void setLeft(ThreeNode node) {
     left = node;
   }
   public ThreeNode middle() {
     return middle;
   }
   public void setMiddle(ThreeNode node) {
     middle = node;
   }
   public ThreeNode right() {
     return right;
   }
   public void setRight(ThreeNode node) {
     right = node;
   }

   public static ThreeNode createThree(int depth) {

     ThreeNode root = new ThreeNode();
     if(depth != 0) {

     for (int i = 1; i < depth; i++) {
       ThreeNode knoten = new ThreeNode();

         root.setLeft(knoten);
         root.setMiddle(knoten);
         root.setRight(knoten);
       }
       return root;   
     }else {

       return null;
     }
   }
}
```


----------



## Meniskusschaden (27. Jun 2016)

Scheint so, dass du weiterhin nur einen Nachfolger an den Wurzelknoten anhängst, den jedoch gleichzeitig als linken, mittleren und rechten. Das ist bestimmt nicht so gedacht.

Die Nachfolger (bzw. der eine, der es bisher ist) bekommen ihrerseits keine weiteren Nachfolger. Es enstehen also nur zwei Ebenen. Ich würde versuchen, Rekursion zu nutzen, um bequem alle Ebenen zu erzeugen.


----------



## regtan (27. Jun 2016)

Ja du hast recht nur wie schreibt man knoten rekursiv??


----------



## Meniskusschaden (27. Jun 2016)

Dazu gibt es jede Menge Erklärungen, z.B. hier (ist allerdings kein Java):https://de.wikipedia.org/wiki/Rekursive_Programmierung
Falls ihr Rekursion noch nicht hattet, kannst du es aber auch iterativ machen. Bei Baumstrukturen ist Rekursion aber häufig bequemer, sobald man sie einmal verstanden hat.


----------



## regtan (27. Jun 2016)

Ich hab so weiter geschrieben aber hab wieder Fehler. Eine praktische Hinweis wäre echt cool 

```
public static ThreeNode createThree(int depth) {
  
     ThreeNode root = new ThreeNode();
     while(depth != 0) {
     for (int i = 1; i < depth ; i++) {
        ThreeNode knoten = new ThreeNode();
  root.setLeft(knoten);
  if (knoten.left() != null) {
     knoten.setLeft(knoten.left());
     knoten.setMiddle(knoten.left());
           knoten.setRight(knoten.left());
         }
  root.setMiddle(knoten);
  if (knoten.middle() != null) {
     knoten.setLeft(knoten.middle());
     knoten.setMiddle(knoten.middle());
           knoten.setRight(knoten.middle());
         }
  root.setRight(knoten);
  if (knoten.right() != null) {
     knoten.setLeft(knoten.right());
     knoten.setMiddle(knoten.right());
           knoten.setRight(knoten.right());
         }
       }
       return root;  
     }
       return null;
   }
```


----------



## Meniskusschaden (27. Jun 2016)

Ich würde dir wirklich empfehlen, einen Schreibtischtest zu machen. Also das Programm Schritt für Schritt durchgehen (Schleifen entsprechend mehrmals) und dabei jedes erzeugte Objekt auf ein Blatt Papier malen und die Referenzen darauf ebenfalls als Pfeile einzeichnen. Dann siehst du bald wie die Objekte vernetzt sind.


----------



## Phtevenz (28. Jun 2016)

bei einer rekursiven erzeugung musst du irgendeine variable als terminationskriterium mitgeben, irgendeine dummyvaribale die beim ersten aufruf mit 0 aufgerufen wird z.b.

DreiBlatt rekursivKind(DreiBlatt db, int tiefe, int dummy){
     if(dummy>=tiefe)
        return null;
      else
          db.links = rekursivKind(new DreiBlatt(), tiefe, dummy+1);
           ......
}


 mit aufruf "Dreiblatt root = new Dreiblatt(); rekursivKind(root,3,0)";


*ungetestet und nur als grobe vorlage*


----------



## JStein52 (28. Jun 2016)

Phtevenz hat gesagt.:


> bei einer rekursiven erzeugung


Ihr müsst euch schon mal auf einen Weg einigen. Nicht einer zeigt es ihm links rum und der andere rechtsrum. Und es gibt keine Variablen die "dummy" heissen. Bei dir würde die "aktuelleTiefe" heissen.


----------



## regtan (28. Jun 2016)

Ich check das nicht. Wie kann diese "DreiBlatt rekursivKind(DreiBlatt db, int tiefe, int dummy)....." in die Methode rein passen.


----------



## JStein52 (28. Jun 2016)

Und schon ist es passiert. Ich würde sagen die passt erst mal gar nicht weil du eine iterative Lösung gewählt hast. Versuche mal das nachzuvollziehen was dir @Meniskusschaden vorgeschlagen hat und korrigiere deine aktuellen Fehler bevor du auf neue Lösungen umschwenkst.


----------



## regtan (28. Jun 2016)

Ich hab es anders geschrieben aber trotzdem ohne Erfolg. 

```
ThreeNode root = new ThreeNode();
       while(depth != 0) {
       for (int i = 1; i < depth ; i++) {
          ThreeNode knoten = new ThreeNode();
    root.setLeft(knoten);
    root.setMiddle(knoten);
    root.setRight(knoten);
    for (int j = 2; j < (Math.pow(3, i)-1); j++) {
             knoten.setLeft(knoten);
             knoten.setMiddle(knoten);
             knoten.setRight(knoten);
           }
         }
       
         return root;   
       }

         return null;
   }
```


----------



## regtan (28. Jun 2016)

Soll diese teil nur einmal gerufen 

```
root.setLeft(knoten);
    root.setMiddle(knoten);
    root.setRight(knoten);
```
und dann nur ?

```
knoten.setLeft(knoten);
             knoten.setMiddle(knoten);
             knoten.setRight(knoten);
```


----------



## mrBrown (28. Jun 2016)

Phtevenz hat gesagt.:


> bei einer rekursiven erzeugung musst du irgendeine variable als terminationskriterium mitgeben, irgendeine dummyvaribale die beim ersten aufruf mit 0 aufgerufen wird z.b.
> 
> *ungetestet und nur als grobe vorlage*



sehr grob  Die Variable zum Terminieren ist in dem Fall die Tiefe, und auch die Übergabe eines Knoten kann man sich sparen...



regtan hat gesagt.:


> Ich hab es anders geschrieben aber trotzdem ohne Erfolg.


Hast du dich schon mal mit Rekursion beschäftigt? Das dürfte dann hierbei der leichtere Weg sein...

Bei der iterativen Lösung müsste man doch noch ne Liste mitschleppen, oder steh ich da grad aufm Schlauch?


----------



## JStein52 (28. Jun 2016)

Du hängst in deinen diversen Schleifen immer unter den root-Knoten das aktuell erzeugte Knoten-Objekt und zwar als left, middle und right. Und dann setzt du in deinem neuen Knoten diesen selber wieder als left, middle, right.  Was willst du denn machen


----------



## regtan (28. Jun 2016)

Ich wollte fur jede neue erzeugte knote 3 knoten verweisen zwar left middle, right


----------



## Meniskusschaden (28. Jun 2016)

Ich glaube, du hast dir noch nicht bewusst gemacht, was deine einzelnen Operationen überhaupt bewirken. So lange dir das nicht klar wird, wirst du es nicht hinbekommen. Das Bild im Anhang enthält zwei Graphen. Der obere zeigt das, was du im Moment tust, der untere zeigt (unvollständig) das, was du vermutlich möchtest.


----------



## regtan (28. Jun 2016)

Ja genau so sollte es aussehen und ich hab manche Codefehler gefunden( glaub ich mindesten) aber trotzdem hab ich bis zweite knote geschafft.


----------



## regtan (28. Jun 2016)

Ich hab jetzt anders versucht:

```
public static ThreeNode createThree(int depth) {

     if (depth == 0)
       return null;
     
     Stack <ThreeNode> three = new Stack <ThreeNode>();
     ThreeNode root = new ThreeNode();
     three.push(root);
     
     while(!three.empty()){
     ThreeNode Node = (ThreeNode)three.pop();
     
       if (Node.left != null) {
         three.push(Node.left);
         if (Node.middle != null) {
           three.push(Node.middle);
           if (Node.right != null) {
             three.push(Node.right);
           }
         }
       }

     }
     return root;
   }
```
trotzdem krieg ich Fehler


----------



## mrBrown (28. Jun 2016)

Du erzeugst nur den Root-Node, von dem sind immer alle Kinder erstmal null, also wird auch nichts anderes als der gepusht, sodass de direkt zurückgegeben wird.

Außerdem beachtest du die Tiefe (außer beim ==0) nicht


----------



## regtan (28. Jun 2016)

Könntest du mir bitte sehr konkret zeigen was ich im Code ändern soll? Weil ich verstehe nicht warum wird nur root zurückgegeben.


----------



## mrBrown (28. Jun 2016)

Auf deinen Stack push du root, dann nimmst du das erste runter (in dem Fall Root), prüfst dann, ob davon das linke Element != null ist, das ist es aber nie, da es nirgendwo gesetzt wird.
Die Schleife fängt dann wieder von vorn an, der Stack ist aber schon leer, also endet die Schleife direkt, und es wird root zurückgegeben.


Um nochmal die Frage von vorhin zurückzukommen, kennst du Rekursion?


----------



## regtan (28. Jun 2016)

Ja ich kenne Rekursion aber ich weiß nicht wie man hier benutzen kann , da ich kenne Nodes nicht so gut.


----------



## mrBrown (28. Jun 2016)

Dann geh das Problem mal von einer anderen Seite an:

Du sollst einen Baum der Tiefe n erzeugen, das ist das gleiche, wie ein Knoten, mit Bäumen der Tiefe (n-1) als Kinder, und diese sind wieder Knoten, mit Bäumen der Tiefe ((n-1)-1) als Kinder


----------



## regtan (30. Jun 2016)

Ich hab den Code Tausend mal umgeschrieben und immer noch hab nicht den richtigen hin gekriegt  Ich wäre sehr dankbar wenn jemand mein Code so umschreibt wo die Fehler sind. Vielen Dank im Voraus!

```
ThreeNode root = new ThreeNode();
     while(depth != 0) {

       ThreeNode Node = new ThreeNode();
       root.setLeft(Node.left);
       root.setMiddle(Node.middle);
       root.setRight(Node.right);

       for (int j = 1; j <= depth; j++) {

         if (Node.left != null) {
           Node.setLeft(Node.left);
           Node.setMiddle(Node.middle);
           Node.setRight(Node.right);
           if (Node.middle != null) {
             Node.setLeft(Node.left);
             Node.setMiddle(Node.middle);
             Node.setRight(Node.right);
             if (Node.right != null) {
               Node.setLeft(Node.left);
               Node.setMiddle(Node.middle);
               Node.setRight(Node.right);
             }
           }
         }

       }
       return root;   
     }
     return null;
   }
```


----------



## Meniskusschaden (30. Jun 2016)

regtan hat gesagt.:


> Ich hab den Code Tausend mal umgeschrieben und immer noch hab nicht den richtigen hin gekriegt


Durch herum probieren wirst du es auch nicht hinbekommen. Es ist schwer, dir zu helfen, denn dein Problem ist nicht, dass du die Lösung nicht findest. Das wäre nicht weiter schlimm, denn man könnte einfache Hinweise dazu geben.
Das Problem ist, dass dir offenbar überhaupt nicht klar ist, was deine einzelnen Anweisungen überhaupt bewirken. Anstatt weiter nach einer Lösung zu suchen, müsstest du zuerst daran arbeiten, zu verstehen, was dein Programm macht. Meines Erachtens hilft da nur ein Schreibtischtest, also das Programm schrittweise Zeile für Zeile durchzugehen und auf Papier aufzuzeichnen, was in der jeweiligen Zeile passiert. Aber das habe ich oben bereits zweimal vorgeschlagen.

Ein paar Zeilen in deinem Code habe ich hier noch mal kommentiert:

```
ThreeNode root = new ThreeNode();    // Hier erzeugst du den Wurzelknoten.
    while(depth != 0) {                

      ThreeNode Node = new ThreeNode();  // Hier erzeugst du einen weiteren Knoten.
      root.setLeft(Node.left);           // Hier hängst du den linken Unterknoten des neuen Knotens als linken
                                         // Unterknoten des Wurzelknotens ein. Da der neue Knoten jedoch keinen
                                         // linken Unterknoten hat, hat auch der Wurzelknoten keinen linken
                                         // Unterknoten.
      root.setMiddle(Node.middle);
      root.setRight(Node.right);

      for (int j = 1; j <= depth; j++) {

        if (Node.left != null) {         // Hier prüfst du, ob der Knoten einen linken Unterknoten hat
          Node.setLeft(Node.left);       // Falls ja, ersetzt du ihn durch sich selbst
          Node.setMiddle(Node.middle);
...
```


----------



## regtan (30. Jun 2016)

Wenn ich richtig verstanden habe dann sollte ich so einfach eine linke Knote an root hangen?

```
root.setLeft(Node);
```
und 

```
if (Node.left != null) {       
     Node.setLeft(Node);  //hier wird eine neue Knote erzeugt werden falls keine links gibt, richtig so oder??
```


----------



## JStein52 (30. Jun 2016)

Jetzt versuchst du es mal so:


```
public static void generateTree(int depth) {

        ThreeNode root = new ThreeNode();

        LinkedList<ThreeNode> listOfNodes = new LinkedList<ThreeNode>();
        listOfNodes.add(root);

        for (int i = 1; i <= depth; i++) {

            LinkedList<ThreeNode> tempList = (LinkedList<ThreeNode>) listOfNodes.clone();

            for (ThreeNode node : tempList) {

                // delete root element from list
                listOfNodes.remove(node);

                // create left/right
                ThreeNode left = new ThreeNode();
                ThreeNode right = new ThreeNode();
                ThreeNode middle = new ThreeNode();

                // set left/right to root node
                node.setLeft(left);
                node.setRight(right);
                node.setMiddle(middle);

                // add left/right to list
                listOfNodes.add(left);
                listOfNodes.add(right);
                listOfNodes.add(middle);
            }
        }
    }
```

Edit:
In der temporären Liste tempList werden sich die Knoten einer Ebene gemerkt damit man sie im nächsten Durchgang alle bearbeiten kann. Das brauchst du bei einer iterativen Lösung (hat dir @mrBrown oben schon mal gesagt.


----------



## mrBrown (30. Jun 2016)

Kleine Verbesserung:
Statt 





JStein52 hat gesagt.:


> `LinkedList<ThreeNode> tempList = (LinkedList<ThreeNode>) listOfNodes.clone();`


lieber
`LinkedList<ThreeNode> tempList = new LinkedList<>(listOfNodes);`


----------



## regtan (30. Jun 2016)

Sollte die for - schleife mit der math.pow genau die knoten in den Baum hängen???

```
while(depth != 0) {

       ThreeNode root = new ThreeNode();

       LinkedList<ThreeNode> listOfNodes = new LinkedList<ThreeNode>();
       listOfNodes.add(root);

       LinkedList<ThreeNode> tempList = new LinkedList<ThreeNode>(listOfNodes);

       for (ThreeNode node : tempList) {

         for (int i = 1; i < depth; i++) {

           ThreeNode left = new ThreeNode();
           ThreeNode right = new ThreeNode();
           ThreeNode middle = new ThreeNode();

           node.setLeft(left);
           node.setRight(right);
           node.setMiddle(middle);

           for (int j = 0; j < Math.pow(3, i); j++) { // ich meine diese schleife hier

             listOfNodes.add(left);
             listOfNodes.add(right);
             listOfNodes.add(middle);
           }
         }
       }
       return root;   
     }
     return null;
   }
```


----------



## JStein52 (30. Jun 2016)

Wo hast du denn jetzt diese Schleife hergezaubert ? So wie ich es oben gepostet habe hat es doch funktioniert ?


----------



## regtan (30. Jun 2016)

nein hat es nicht funktioniert. Die schleife ,dachte ich , wird immer die genaue Anzahl der Knote für Ebene anhängen.


----------



## JStein52 (30. Jun 2016)

So, so. Wie hast du das kontrolliert dass es nicht funktioniert ?


----------



## regtan (30. Jun 2016)

Es ist so das wir können der Code testen ob es Funktioniert und leider hat nicht.


----------



## regtan (30. Jun 2016)

Das ist der ganze Code

```
public class ThreeNode {

   private ThreeNode left;
   private ThreeNode middle;
   private ThreeNode right;

   public ThreeNode left() {
     return left;
   }

   public void setLeft(ThreeNode node) {
     left = node;
   }

   public ThreeNode middle() {
     return middle;
   }

   public void setMiddle(ThreeNode node) {
     middle = node;
   }

   public ThreeNode right() {
     return right;
   }

   public void setRight(ThreeNode node) {
     right = node;
   }


   public static ThreeNode createThree(int depth) {

     while(depth != 0) {

       ThreeNode root = new ThreeNode();

    LinkedList<ThreeNode> listOfNodes = new LinkedList<ThreeNode>();
    listOfNodes.add(root);

    for (int i = 1; i <= depth; i++) {

       LinkedList<ThreeNode> tempList = new LinkedList<ThreeNode>(listOfNodes);

    for (ThreeNode node : tempList) {

    // delete root element from list
    listOfNodes.remove(node);

    // create left/right
    ThreeNode left = new ThreeNode();
    ThreeNode right = new ThreeNode();
    ThreeNode middle = new ThreeNode();

    // set left/right to root node
    node.setLeft(left);
    node.setRight(right);
    node.setMiddle(middle);

    // add left/right to list
    listOfNodes.add(left);
    listOfNodes.add(right);
    listOfNodes.add(middle);
    }
    }
       return root;   
     }
     return null;
   }
}
```


----------



## JStein52 (30. Jun 2016)

Und was war falsch ?


----------



## JStein52 (30. Jun 2016)

regtan hat gesagt.:


> Das ist der ganze Code


Das ist nicht das was ich dir gepostet habe ! Bitte nimm meinen Code dann wird es funktionieren


----------



## regtan (30. Jun 2016)

Aber hab genau dein Code genommen und trotzdem funktioniert leider nicht. Erstens gibt nichts Zurück auch wenn depth null ist. Dann des 

```
LinkedList<ThreeNode> tempList = (LinkedList<ThreeNode>) listOfNodes.clone();
```
wird auch ein bug erzeugen


----------



## mrBrown (30. Jun 2016)

Da fehlt nur das return, das solltest du zumindest an die passende Stelle schreiben können 



regtan hat gesagt.:


> wird auch ein bug erzeugen


warum sollte es?


----------



## JStein52 (30. Jun 2016)

Ja, ich dachte du benutzt diese Zeile:


```
LinkedList<ThreeNode> tempList = new LinkedList<>(listOfNodes);
```

Und ein return root;  darfst du am Ende ja einbauen.  Aber lass endlich mal diese whiel depth != 0) -Schleife weg. Was soll die. Und was funktioniert dann am Rest nicht ?


----------



## JStein52 (30. Jun 2016)

Wenn depth = 0 ist kommt er gar nicht an die Stelle wo du sagst das gibt einen Fehler


----------



## regtan (30. Jun 2016)

ich hab das so umgeschrieben:

```
public static ThreeNode createThree(int depth) {
     
     if (depth == 0) {
       return null;
     }

     ThreeNode root = new ThreeNode();

  LinkedList<ThreeNode> listOfNodes = new LinkedList<ThreeNode>();
  listOfNodes.add(root);

  for (int i = 1; i <= depth; i++) {

   
     LinkedList<ThreeNode> tempList = new LinkedList<ThreeNode>(listOfNodes);

  for (ThreeNode node : tempList) {

  // delete root element from list
  listOfNodes.remove(node);

  // create left/right
  ThreeNode left = new ThreeNode();
  ThreeNode right = new ThreeNode();
  ThreeNode middle = new ThreeNode();

  // set left/right to root node
  node.setLeft(left);
  node.setRight(right);
  node.setMiddle(middle);

  // add left/right to list
  listOfNodes.add(left);
  listOfNodes.add(right);
  listOfNodes.add(middle);
  }
  }
  return root;
}
```
Funktioniert aber nicht:

*Test nicht bestanden*

returnsNullForDepthZero //nur das ist ok

returnsCorrectTreeForDepthTen

Expected: is null
     got: <ThreeNode@440231a5>


returnsCorrectTreeForDepthFour

Expected: is null
     got: <ThreeNode@6a0c9792>


returnsCorrectTreeForDepthTwo

Expected: is null
     got: <ThreeNode@4254f9bd>


returnsSingleNodeForDepthOne

Expected: is null
     got: <ThreeNode@100386b8>


----------



## mrBrown (30. Jun 2016)

Wenn die Ausgabe der Tests zumindest sinnvoll ist, erwartet der bei egal welcher Tiefe null als Rückgabewert, was alles andere als richtig wäre...

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;
    }
```


----------



## regtan (30. Jun 2016)

Jaaaaaaa das hat funktioniert endlich. Super super super Danke!


----------



## mrBrown (30. Jun 2016)

Dann ist die Ausgabe der Tests überaus missverständlich...


----------



## JStein52 (30. Jun 2016)

mrBrown hat gesagt.:


> was alles andere als richtig wäre...


Ja, merkwürdiger Test. Bei mir war alles richtig. Undjetzt haben wir 3 Tage versucht eine iterative Lösung zu finden, plötzlich mag er es doch rekursiv. Da hätten wir uns viel Mühe sparen können


----------



## JStein52 (30. Jun 2016)

Und ich denke die Interpretation der Tiefe war bei der iterativen Lösung falsch. Das muss einfach alles nur eine Ebene hoch. Aber jetzt egal.


----------



## regtan (30. Jun 2016)

```
for (int i = 1; i <= depth; i++)
```
  das fangt aber schon von eine Ebene hoch an, oder??


----------



## mrBrown (30. Jun 2016)

JStein52 hat gesagt.:


> Ja, merkwürdiger Test. Bei mir war alles richtig. Undjetzt haben wir 3 Tage versucht eine iterative Lösung zu finden, plötzlich mag er es doch rekursiv. Da hätten wir uns viel Mühe sparen können



Ich versuch seit 3 Tagen, ihn zur rekursiven Lösung zu bewegen 



JStein52 hat gesagt.:


> Und ich denke die Interpretation der Tiefe war bei der iterativen Lösung falsch. Das muss einfach alles nur eine Ebene hoch. Aber jetzt egal.



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


Aber egal von wem die Tests kommen, er sollte denjenigen drauf hinweisen, das die Ausgabe Mist ist.


----------



## regtan (30. Jun 2016)

Ich hatte auch die = weg gemacht aber trotzdem ohne Erfolg


----------



## JStein52 (30. Jun 2016)

mrBrown hat gesagt.:


> 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 (30. Jun 2016)

Mhmmm,, was bedeutetdas denn immer bei den Tests:

returnsCorrectTreeForDepthTen

Ist das dann ok oder falsch ??


----------



## regtan (30. Jun 2016)

früher war falsch aber jetzt nicht mehr


----------



## mrBrown (30. Jun 2016)

JStein52 hat gesagt.:


> returnsCorrectTreeForDepthTen


ist nur der TestName


----------



## Lazyyy (6. Jun 2018)

Schon ein bisschen her das Thema:



mrBrown hat gesagt.:


> Versuch ansonsten mal das:
> 
> ```
> public static ThreeNode createThree(int depth) {
> ...



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 (6. Jun 2018)

Lazyyy hat gesagt.:


> 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 (6. Jun 2018)

mrBrown hat gesagt.:


> ThreeNode node = *new* ThreeNode(); _//erstelle die Wurzel für den Baum_


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



Lazyyy hat gesagt.:


> 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 (6. Jun 2018)

Blender3D hat gesagt.:


> 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 (6. Jun 2018)

Blender3D hat gesagt.:


> 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 (7. Jun 2018)

mrBrown hat gesagt.:


> 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 (7. Jun 2018)

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 ^^.


----------

