Baum erzeugen

R

regtan

Aktives Mitglied
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:
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;
}
 
Ich weiß nicht, was du damit meinst:
regtan hat gesagt.:
Es gelingt mir bis "CorrectTreeForDepthTwo" aber nicht weiter.
Zum Vergrößern anklicken....
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.
 
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.
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) {

     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;
     }
   }
}
 
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.
 
Ich hab so weiter geschrieben aber hab wieder Fehler. Eine praktische Hinweis wäre echt cool 🙁
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);
  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;
   }
 
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.
 
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*
 
Ich check das nicht. Wie kann diese "DreiBlatt rekursivKind(DreiBlatt db, int tiefe, int dummy)....." in die Methode rein passen. 🙁
 
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.
 
Ich hab es anders geschrieben aber trotzdem ohne Erfolg.
Code: 
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;
   }
 
Soll diese teil nur einmal gerufen
Code: 
root.setLeft(knoten);
    root.setMiddle(knoten);
    root.setRight(knoten);
und dann nur ?
Code: 
             knoten.setLeft(knoten);
             knoten.setMiddle(knoten);
             knoten.setRight(knoten);
 
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*
Zum Vergrößern anklicken....

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.
Zum Vergrößern anklicken....
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?
 
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
 
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.
 

Anhänge

  • ThreeNode.png
    ThreeNode.png
    23 KB · Aufrufe: 70
Ja genau so sollte es aussehen und ich hab manche Codefehler gefunden( glaub ich mindesten) aber trotzdem hab ich bis zweite knote geschafft.
 
Ich hab jetzt anders versucht:
Code: 
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 🙁
 
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
 
Könntest du mir bitte sehr konkret zeigen was ich im Code ändern soll? Weil ich verstehe nicht warum wird nur root zurückgegeben.
 
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?
 
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 😉
 
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!
Code: 
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;
   }
 
regtan hat gesagt.:
Ich hab den Code Tausend mal umgeschrieben und immer noch hab nicht den richtigen hin gekriegt
Zum Vergrößern anklicken....
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:
Java: 
    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);
...
 
Wenn ich richtig verstanden habe dann sollte ich so einfach eine linke Knote an root hangen?
Code: 
root.setLeft(Node);
und
Code: 
if (Node.left != null) {       
     Node.setLeft(Node);  //hier wird eine neue Knote erzeugt werden falls keine links gibt, richtig so oder??
 
Jetzt versuchst du es mal so:

Code: 
    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.
 
Sollte die for - schleife mit der math.pow genau die knoten in den Baum hängen???
Code: 
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;
   }
 
Das ist der ganze Code
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;
   }
}
 
Aber hab genau dein Code genommen und trotzdem funktioniert leider nicht. Erstens gibt nichts Zurück auch wenn depth null ist. Dann des
Code: 
LinkedList<ThreeNode> tempList = (LinkedList<ThreeNode>) listOfNodes.clone();
wird auch ein bug erzeugen
 
Ja, ich dachte du benutzt diese Zeile:

Code: 
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 ?
 
ich hab das so umgeschrieben:
Code: 
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>
 
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:
Java: 
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;
    }
 
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.
 
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 😉😉
Zum Vergrößern anklicken....

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.
Zum Vergrößern anklicken....

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.
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

Baum > Baum-Swing
Antworten: 4
2-3-4 Baum vs. (2,4) Baum
Antworten: 2
Teilbaum aus DOM-Baum erzeugen
Antworten: 5
Beim Erzeugen einer XML Datei auch die XML Struktur erzeugen?
Antworten: 11
Rot-Schwarz-Baum min und max-Tiefe
Antworten: 1

Zurück
Oben