Baum erzeugen

[regtan]

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]

Ich weiß nicht, was du damit meinst:

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]

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]

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]

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

 

[Meniskusschaden]

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]

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]

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]

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]

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]

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

 

[JStein52]

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]

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]

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]

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

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]

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]

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

 

[Meniskusschaden]

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]

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

 

[regtan]

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]

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]

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]

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]

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

 

[mrBrown]

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]

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]

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]

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]

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]

Kleine Verbesserung:
Statt

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

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

 

[regtan]

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]

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

 

[regtan]

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

 

[JStein52]

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

 

[regtan]

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

 

[regtan]

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]

Und was war falsch ?

 

[JStein52]

Das ist der ganze Code

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

 

[regtan]

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]

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

wird auch ein bug erzeugen

warum sollte es?

 

[JStein52]

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]

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

 

[regtan]

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]

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]

Jaaaaaaa das hat funktioniert endlich. Super super super Danke!

 

[mrBrown]

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

 

[JStein52]

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]

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]

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

das fangt aber schon von eine Ebene hoch an, oder??

 

[mrBrown]

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

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.