Schreiben Sie eine rekursive Methode, die die Anzahl der Knoten in einem Binärbaum zählt und zurückgibt

Question

Schreiben Sie eine rekursive Methode, die die Anzahl der Knoten in einem Binärbaum zählt und zurückgibt. Die Knotenklasse ist bereits implementiert. Wir haben GETNEXT()

hier ist mein Code

int countnode(binarynode n){ 
n = root; 
int i = i + 1； 
count + = countnode(node.getnext(); 
return count; 
} 

aber irgendwie ist es nicht funktioniert. Kann jemand erklären warum?

Answer 1

Im ersten Blick scheint, dass Sie nicht den Basisfall für die Rekursion behandeln, die für Methode wie Rekursion muss.

Hier ist der Code, den ich in C implementiert haben

int count(node *n) // Here you will pass your java node class 
{ 
    int cont = 1; // By default It will be on for the root only 

    if (n == NULL) { // Base Case 
     return 0; 
    }else { 
     cont += count(n->left); // you will pass you left class member 
     cont += count(n->right); // Right class member 
     return cont; 
    } 
} 

Answer 2

Was meinst du mit binären Knoten? hat es nur ein Kind oder zwei? count wird nicht deklariert? Angenommen, Ihr binärer Knoten hat zwei Kinder, dann könnte die folgende Lösung funktionieren?

class BinaryNode { 

    BinaryNode left; // Pointer to left child 
    BinaryNode right; // Pointer to right child 

    BinaryNode() { 
    BinaryNode root = null; 
    left = null; 
    right = null; 
    } 

    // Method to count total nodes for above structure. 

     int numberOfNodes(BinaryNode root, int counter) { 
      if (root == null) { 
       return counter; 
      }else{ 
       return (numberOfNodes(root.left,++counter)+numberOfNodes(root.right,++counter)); 

      } 

} 
}