Baum Code kurze frage ...

[Mino1337]

Hallo,

ich habe eine Klasse und eine Methode.


Klasse Tree :

class Tree<T> {
private class Node {
Node[] children;
T data;
}
Node root;
}

Methode :

int countNodes() {
return countNodes(root);
}
int countNodes(Node pos){
int count = 0;
if (pos.children != null)
for (int i=0;i<pos.children.length;i++)
count += countNodes(pos.children[i]);
return count+1;
}

Die Methode soll rekursiv die ANzahl der Knoten des Baums wiedergeben aber ich verstehe nicht wie:

Nehmen wir an ich habe einen Baum mit 1000 Knoten und die Wurzel hat 2 Kinder dann gibt mir diese Methode doch nur die zahl 3 zurück. Wo ist da was Rekursiv ?

Die Wurzel ist ja auch nur ein Knoten und hat einen Array mit 2 Kindern drinnen und die Methode tut nichts als diesen Array abzuzählen und das ergebniss +1 zurück zu schicken oder hab ich die rekursion doch übersehen ?!


Danke =)

 

[kaoZ]

das ist nicht rekursiv

for (int i=0;i<pos.children.length;i++)
count += countNodes(pos.children[i]);
return count+1;

rekursiv bedeutet das sich etwas so oft selbst aufruft bis eine bestimmte Abbruchbedingung eintritt, in deinem Fall würde sich die Methode also dementsprechend selbst aufrufen.

[EDIT]Die formatierung ist aber auch grausam, es sind 2 Methoden die ineinander ausgeführt werden btw, also könnte das ganze doch rekursiv ablaufen, die intern verwendete Methode iteriert lediglich über die knoten der Kinder und zählt diese zusammen, ob die implementierung nun richtig ist habe ich aber nicht geschaut[/EDIT]

 

[Mino1337]

    int countNodes() {
    return countNodes(root);
    }


    int countNodes(Node pos){
    int count = 0;
       if (pos.children != null)
          for (int i=0;i<pos.children.length;i++)
              count += countNodes(pos.children[i]);
              return count+1;
    }

Ich habe mal versucht das besser einzurücken ... Das sollte zumindest Richtig sein da es aus einer Musterlösung ist ...

Ich verstehe nur nicht wie das Rekursiv sein soll ... Die Methoden laufen ja hintereinander nicht ineinander ...

 

[Natac]

Natürlich ist das Rekursiv. Habe zur Verdeutlichung mal { } gesetzt, denn deine Einrückung suggeriert einen falschen Ablauf.

int countNodes() {
  return countNodes(root); // Aufruf mit der Wurzel
}
     
     
int countNodes(Node pos){ // Zähle Kinder +1 (für die Node selbst)
  int count = 0;
  if (pos.children != null){ // wenn wir Kinder haben haben
    for (int i=0;i<pos.children.length;i++){ // für jedes Kind, Abbruchbedingung ist die maximale Anzahl an Kindern
      count += countNodes(pos.children[i]); // Zähle Kinder der Kinder -> Rekursion, da Methode erneut aufgerufen wird.
    }
  }
  return count+1; // Rückgabe Anzahl aller Kinder + 1 (pos selbst).
}

Ich denke das Problem ist die Einrückung gewesen. Am besten für alle for und ifs immer Klammern {} setzen, sonst können solche Fehler eben schnell passieren.

 

[kaoZ]

stimmt hab ich übersehen da die rekursion hier während eines iterativen Vorganges abläuft

countNodes(pos.children[i])

[EDIT]Ich sagte ja suboptimal formatiert ^^[/EDIT]

 

[Natac]

Rekursion heißt ja nur, dass sich die Methode selbst aufruft. Es trifft keine Aussage darüber, wie oft sie das pro Aufruf tut.

 

[Mino1337]

Oh Dankesehr, ja ist schon hart wenn man nichtmal die Musterlösung schnallt aufgrund von solchen sachen ...

Danke dir =D ...