hallo allerseits,
ich hab folgendes problem. ich soll eine methode schreiben die rekursiv aufgerufen wird um die anzhal der knoten in einem binärbaum zu zählen. hier ist mal mein vorschlag, leider klappts nicht so wie ich will. danke schon mal im vorraus


// Gibt die Anzahl der Knoten im Baum zurück.
// node ist die Wurzel des aktuellen (Teil)baums.
public static int countNodes(BinaryNode node)
{
int z1 = 0;
int z2 = 0;
int zaehler = 0;
if(node.getLeft()!=null)
{
countNodes(node.getLeft());
z1++;

}
if (node.getRight()!=null)
{
countNodes(node.getRight());
z2++;
}
zaehler = z1 + z2;
return zaehler;
}

Code bitte unbedingt in die dafür vorgesehenen Tags (siehe meine Signatur).

kleiner Tipp: dein Code ist zwar rekursiv, allerdings verwendest du die Ergebnisse der weiteren Methodenaufrufe nicht! Stattdessen wird nur die oberste Ebene des Binärbaumes gezählt.

So wäre es richtig:

Code java:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

public static int countNodes(BinaryNode node){  int zaehler = 0;  if(node.getLeft()!=null)  {      zaehler += countNodes(node.getLeft());      zaehler++;  }  if (node.getRight()!=null)  {      zaehler += countNodes(node.getRight());      zaehler++;  }  zaehler = z1 + z2;  return zaehler;  }

Besser wäre allerdings, du würdest keine Rekursion verwenden, das führt zu unnötiger Speicherbelastung!

danke ich werds mal testen.

die rekursion muss ich leider machen da das in der aufgabe so vorgegeben ist

Hallo,

schau mal hier:

Code java:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

package de.tutorials;   public class BinTreeExample {     public static void main(String[] args) {         Node left3 = new Node();         Node right2 = new Node();     Node left2 = new Node(left3,null);         Node right1 = new Node(left2,right2);     Node left1 = new Node();         Node left0 = new Node(left1,right1);     Node right0 = new Node();         Node root = new Node(left0, right0);         System.out.println(countNodes(root));   }       private static int countNodes(Node node) {     return node == null ? 0 : 1 + countNodes(node.left) + countNodes(node.right);   }       static class Node{     Node left;     Node right;         public Node(){}         public Node(Node left, Node right) {       this.left = left;       this.right = right;     }   } }

Gruß Tom

vielen dank für die schnelle hilfe, hat super geklappt

das würde mich aber auch zu noch einer anderen frage bringen. wie kann man nun prüfen ob ein binärbaum vollständig ist? hier mein vorschlag.

Code :

1 2 3 4 5 6 7 8 9 10

public static boolean isComplete(BinaryNode node)     {         if ( node != null)         {             return true;         } else         {             return isComplete(node.getLeft()) && isComplete(node.getRight());         }     }

allerdings gibt diese methode immer nur true zurück weil ich nicht genau weiss wie ich den false-teil einbauen muss

Ein unvollständiger Binärbaum ist doch, wenn ein Knoten genau einen Kindknoten hat, oder? Ich hatte soetwas leider nie gelernt Er wäre vollständig, wenn beide Knoten null oder beide Knoten nicht null sind, der Rückgabewert wäre demzufolge gleich.

Hallo,

schau mal hier: (gemäß der Definition von oben)

Code java:

1 2 3

private static boolean isComplete(Node node) {     return node != null && (isComplete(node.left) == isComplete(node.right));   }

Gruß Tom

@ HonniCilest, also eine Definition die ich gefunden habe lautet: ein vollständiger Baum hat auf jedem Niveau die maximal mögliche Knotenzahl und sämtliche Blätter haben diesselbe Tiefe, so das zur info .

@Thomas, vielen Dank für deinen Tip. Ich werde es später noch testen und morgen posten ob es funktioniert

Zitat von starbug

@ HonniCilest, also eine Definition die ich gefunden habe lautet: ein vollständiger Baum hat auf jedem Niveau die maximal mögliche Knotenzahl und sämtliche Blätter haben diesselbe Tiefe, so das zur info .

Dann müsste man da vermutlich eher Mathematisch herangehen... Ich denke aber du benötigst die Maximale Tiefe deines Baumes, die musst du irgendwo herbekommen. Ansonsten hast du ja bereits die Anzahl der Knoten. Also müsste reintheoretisch eine Gleichung zu bilden sein *nachdenk*...

Knotenanzahl = 2^Baumtiefe-1 <-- (oder so ähnlich)

Dann kannst du die so errechnete Knotenanzahl mit der tatsächlichen Knotenanzahl vergleichen.

danke für alle tips hat alles gut geklappt

Hallo zusammen,

um nicht nen neuen Thread aufzumachen möchte ich hier meine Frage reinstellen in der Hoffnung vll. den ein oder anderen Tipp zu bekommen, und zwar muss ich die Anzahl der Blätter zählen. Ich habe folgenden Code entwickelt:

Code :

1 2 3 4 5 6 7 8 9 10 11 12

public static int countLeaves(BinaryNode node)     {            if (node == null)                  return 0;                                              else if (node.left == null && node.right == null)                 return 1;                            else                  return countLeaves(node.getLeft()) + countLeaves(node.getRight());     }

kann das so richtig sein?

joa das is ganz gut das habe ich auch so

klasse

Du hast du schon den Aufgabenteil2 ? Irgendwie ansatumäßig was gescheihtes? du weißt worum es geht nehm ich an die Höhe des B-Baums etc. ... ich brauch unbedingt 2 Punkte für diese Aufgabe ...