✔ Knoten zählen in einem Binärbaum

[starbug]

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

 

[genodeftest]

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:

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!

 

[starbug]

danke ich werds mal testen.

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

 

[Thomas Darimont]

Hallo,

schau mal hier:

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

 

[starbug]

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

 

[starbug]

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.

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

 

[HonniCilest]

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.

 

[Thomas Darimont]

Hallo,

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

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

Gruß Tom

 

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

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

 

[HonniCilest]

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