Rekursiv Tiefe eines binären Suchbaums ermitteln

[Trümmermacher]

Hier wir sollen diese AUfgabe lösen .Weiter unten ist mein Lösungsansatz ich wüsste leider nur die Möglichkeit es zu lösen. Wenn ich die Methoden getleftNode und getRightNode hinzufüge.

Leider weiss ich nicht ob es erlaubt ist gibt es einen anderen Weg??
Ich glaube es ist auch gewollt das die Aufgabe rekursiv gelöst wird !

Bitte um Hilfe

public class BinaryTree {
private TreeNode root = null;
private static class TreeNode { public int value; public TreeNode left, right; }

public int getNumberOfLeaves() {
// TODO
return 0;

}
private int getNumberOfLeaves(TreeNode tree) {
// TODO
return 0; }

}

public int getNumLeafNodes(){
        int c=0;
     
        if(getLeftNode()!=null)
            c+=getLeftNode().getNumLeafNodes();
        if(getRightNode()!=null)
            c+=getRightNode().getNumLeafNodes();
        else
            return 1;
     
     
        return c;
    }

 

[Flown]

Was ist jetzt die Frage dazu?

 

[flopalko]

Die TreeNodes sind public und somit brauchst du keine getter. Du greifst direkt auf den Wert zu.
Also bei deinem Code statt dem getLeft/RightNode einfach direkt drauf zugreifen.
In welcher Klasse hast du überhaupt vor diese Methode zu implementieren? Im Tree oder in TreeNode?

 

[Andi_CH]

Einfach mal ein weiterer Hinweis:

public int getNumLeafNodes(){
        int c=0;
   
        if(getLeftNode()!=null)
// Annahme: ist nicht null -> c bekommt also einen Wert
            c+=getLeftNode().getNumLeafNodes();

        if(getRightNode()!=null)
// Annahme das ist null
            c+=getRightNode().getNumLeafNodes();
        else
//Das wird ausgeführt und somit der Wert von c vergessen
            return 1;
        return c;
    }

 

[Trümmermacher]

Ich hab ne Nacht drüber geschlafen

Aber wie kann ich denn left und right zugreifen ich bekomme immer eine Fehlermeldung irgendwas mache ich falsch

Ich muss doch eigentlich den baum jede node abklppern und gucken ob sie eine left oder right Node haben und wenn nicht wird beim zähler +1 gezählt , oder irre ich mich da???

 

[Trümmermacher]

@Andi_CH ich rechne die Werte doch bei c dazu ich verwende += und damit wird es nicht überschrieben sondern dazu gerechnet nur unten habe ich den Fehler mit else return 1 return c das müsste anders rum sein .

 

[Meniskusschaden]

Wie lautet denn überhaupt die Aufgabenstellung? Soll nun die Baumtiefe ermittelt werden oder die Anzahl der Blätter oder die Anzahl aller Knoten? Habe den Eindruck, dass der bisherige Code nur wenig mit dem Thread-Titel zu tun hat.

 

[Trümmermacher]

Ok der Titel ist ein wenig falsch gewählt es soll die Anzahl aller Blattknoten gezählt werden !!!!

 

[Meniskusschaden]

Ich muss doch eigentlich den baum jede node abklppern und gucken ob sie eine left oder right Node haben und wenn nicht wird beim zähler +1 gezählt , oder irre ich mich da???

Wenn es keinen Nachfolger gibt, muß 1 zurück geliefert werden. Du lieferst aber auch 1 zurück, falls es nur einen Nachfolger gibt und verwirfst die Blätter-Anzahl aus dem Zweig des Nachfolgers. Siehe Hinweis von @Andi_CH.

 

[Trümmermacher]

Könnte ich es nicht ungefähr so lösen??? weil ich muss ja beide methoden benutzen sonst wären sie nicht aufgeführt

public class TreeNode2 {
private TreeNode root = null;
private static class TreeNode {
public int value;
public TreeNode left, right;
}
     public int getNumLeafNodes() {
    if (root.left == null && root.right == null) {
      
    return 1;// er zeigt mir einen fehler an wenn ich 1 zurückgeben will
    }
     }


private int getNumberOfLeaves(TreeNode tree) {
        int leafNb = 0;
         for (Treenode tree : root) {// die zeile ist noch nichr richtig kann mir da jemand helfen ???
             int childLeafs = tree.getNumLeafNodes();
             leafNb = childLeafs;
         }
         return leafNb;
}
}

 

[Kababär]

Hast du einen Konstruktor oder kommt der Tree einfach bei "getNumberOfLeaves" mit?

Einfach mal ein weiterer Hinweis:

public int getNumLeafNodes(){
        int c=0;
  
        if(getLeftNode()!=null)
// Annahme: ist nicht null -> c bekommt also einen Wert
            c+=getLeftNode().getNumLeafNodes();

        if(getRightNode()!=null)
// Annahme das ist null
            c+=getRightNode().getNumLeafNodes();
        else
//Das wird ausgeführt und somit der Wert von c vergessen
            return 1;
        return c;
    }

Dabei zählst du aber nicht alle Blätter, sondern Knoten auf dem Weg. Dabei hast du auch das Problem, dass int kein null besitzt.
Dabei hast du noch einen Logikfehler. Angenommen, der linke Knoten ist nicht 0, sondern 1, aber dafür gibt es keinen rechten Knoten, dann returnst du trotzdem 1, läufst aber den linken Knoten trotzdem ab.
Lösung: einfach den else-Zweig entfernen mit Inhalt.
Aber wieso arbeitest du denn eigentlich so, wenn er doch das Objekt TreeNode hat?
Wozu eine getRight und getLeft Methode? Mann direkt auf left und right zugreifen.
Wieso geht ihr nicht einfach hin und schickt den TreeNode mit als Parameter?
Um auf Blätter zu prüfen, müsstest du demnach noch folgendes übernehmen (rekursiv):

  private int getNumberOfLeaves(TreeNode tree) {
  if (tree == null) {
  return 0;
  }
  if (tree.left == null && tree.right == null) {
  return 1;
  } else {
  return getNumberOfLeaves(tree.left) + getNumberOfLeaves(tree.right);
  }
  }

TE: Ich kann mir nicht vorstellen, dass ihr den Code so bekommen habt. Hast du das alles selbst geschrieben? Hoffe ich konnte etwas helfen

 

[Kababär]

Könnte ich es nicht ungefähr so lösen??? weil ich muss ja beide methoden benutzen sonst wären sie nicht aufgeführt

public class TreeNode2 {
private TreeNode root = null;
private static class TreeNode {
public int value;
public TreeNode left, right;
}
     public int getNumLeafNodes() {
    if (root.left == null && root.right == null) {
     
    return 1;// er zeigt mir einen fehler an wenn ich 1 zurückgeben will
    }
     }


private int getNumberOfLeaves(TreeNode tree) {
        int leafNb = 0;
         for (Treenode tree : root) {// die zeile ist noch nichr richtig kann mir da jemand helfen ???
             int childLeafs = tree.getNumLeafNodes();
             leafNb = childLeafs;
         }
         return leafNb;
}
}

Falls ein "root" einen Nachfolger hat, der u.U. auch mehrere Blätter hat, gibst du trotzdem nur 1 zurück.
Und: dachte es soll rekursiv sein?

 

[Trümmermacher]

@Kababär das ist der Code den wirbekommen haben mit der Aufgabenstellung die Blattknoten zu zählen

public class TreeNode2 {
private TreeNode root = null;
private static class TreeNode {
public int value;
public TreeNode left, right;
}
     public int getNumLeafNodes() {
    
       
    return 0;
    
     }


private int getNumberOfLeaves(TreeNode tree) {
        return 0
         }
         

}
[/JAVA]

 

[Trümmermacher]

@Kababär wollte es so programmieren das die Methode für jeden Knoten einzeln aufgerufen wird . Und dann sollte es doch eigentlich passen

 

[Trümmermacher]

@Kababär so wie hier bei dieser Methode aus einer anderen Aufgabe

    public int getNumLeafNodes() {
           if (children == null || children.length == 0) {
               return 1;
           }

           int leafs = 0;
           for (Treenode child: children) {
               leafs += child.getNumLeafNodes();
           }
           
           return leafs;
       }
[/JAVA]

 

[Kababär]

Ok, eine rekusrive Methode ist eine Methode, die sich selbst aufruft bis zu eine gewisse Bedingung erfüllt ist.
Das was du machst ist: Rufe bis eine gewisse Bedingung erfüllt ist, eine Methode auf.
Das ist was anderes. Brauchst du es denn rekursiv?

 

[Meniskusschaden]

Falls ein "root" einen Nachfolger hat, der u.U. auch mehrere Blätter hat, gibst du trotzdem nur 1 zurück.

Nein, für den Fall gibt es keine return-Anweisung. Vermutlich wird deshalb auch ein Fehler angezeigt.

 

[Trümmermacher]

ne nicht unbedingt anscheinend thema echt falsch gewählt !!!
Mir ist klar das eine Methode die sich immer wieder selbst aufruft nur rekursiv ist . In diesem Fall hab ich das Wort falsch benutzt

Die Aufgabe soll mit den zwei angegeben Methoden erledigt werden!!!!

 

[flopalko]

Poste doch mal die Aufgabenstellung. Ich glaube nämlich, dass du selbst schon den Überblick verloren hast was gegeben und was verlangt ist.
Im ersten Post meinst du es ist rekursiv zu lösen, dafür fehlt aber die Methode getNumLeafNodes in der Klasse TreeNode. Du hast diese nur im BinaryTree und somit kannst du es gar nicht rekursiv lösen.
Solltest du nur die Angabe falsch übertragen haben hier der Code aus deinem ersten Post angepasst damit es funktioniert:

public int getNumLeafNodes(){
        int c=0;
      
        if (left == null && right == null)
            return 1;
      
        if (left != null)
            c += left.getNumLeafNodes();
        if (right != null)
            c += right.getNumLeafNodes();   
    
        return c;
    }

Dieser Code gehört in die Klasse TreeNode. Folgend der Code für die Klasse BinaryTree zum Starten der Rekursion.

public int getNumberOfLeaves(){
    if (root != null)
        return root.getNumLeafNodes();
    return 0;
}

Aber poste wie gesagt die Aufgabenstellung denn nachdem du dir mit fast jedem Post selbst bezüglich der Aufgabenstellung widersprichst ist das hier nur geraten^^

EDIT: und aja @all: warum verwenden jetzt alle die getLeftNode und getRightNode Methoden? Er hat ja zu Beginn erwähnt, dass er nicht weiß, ob er diese verwenden darf, da nicht gegeben. Sie sind ja aber auch nicht nötig, da die TreeNodes left und right public sind, also warum nicht einfach direkt drauf zugreifen?

 

[Trümmermacher]

Hier nochmal der Code der uns zur Verfügung gestellt wurde und die Aufgabe war:

In dieser Aufgabe soll eine Methode implementiert werden,
die die Knotenblätter zählt und zurück gibt

public class TreeNode2 {
private TreeNode root = null;
private static class TreeNode {
public int value;
public TreeNode left, right;
}
     public int getNumLeafNodes() {
//TODO
return 0
     }


private int getNumberOfLeaves(TreeNode tree) {
  //TODO
return 0;
}
<0
[/JAVA]

 

[Trümmermacher]

Das war die vorherige Aufgabe in der das Minimum im Baum gesucht wurde

public class BinaryTree {
private TreeNode root = null;
private static class TreeNode {
public int value;
public TreeNode left, right;
}
public int findMinValue () {
// TODO
return 0;
}
private int findMinValue (TreeNode tree) {
// TODO
return 0;
}
}
[/JAVA]
Die Aufgabe habe ich so gelöst und ich denke die Anzahl der Blattknoten zählen müsste so ähnlich funktionieren 

[code=JAVA]
public int getMin (){
    return getMin(root);
}
private int getMin (TreeNode tree){
    if(tree.left!=null)                // If theres left, go left
        return getMin(tree.left);
    else
    return tree.value;                // if theres no left, return the value
}

}
[/JAVA]

 

[flopalko]

public class TreeNode2 {
    private TreeNode root = null;
    private static class TreeNode {
        public int value;
        public TreeNode left, right;
    }
    
    public int getNumLeafNodes() {
        if (root != null)
            return getNumberOfLeaves(root);
        return 0;
     }

    private int getNumberOfLeaves(TreeNode tree) {
        int c=0;
      
        if (tree.left == null && tree.right == null)
            return 1;
      
        if (tree.left != null)
            c += getNumberOfLeaves(tree.left);
        if (tree.right != null)
            c += getNumberOfLeaves(tree.right);   
    
        return c;
    }
}

und für die Zukunft bitte: ordentliches Einrücken vom Code beachten, Aufgabenstellung klar formulieren, mehr Eigeninitiative zeigen

 

[Andi_CH]

@flopalko
Hast du den Code aus meinem Kopf geklaut?

mehr Eigeninitiative zeigen

Vor allem das kann ich nur unterschreiben. *kopfschüttel*