Wie funktioniert diese Funktion, um die Anzahl der Knoten im binären Baum berechnet

Question

Ich habe eine Funktion, die ich versuche zu analysieren, welche seine Ausgabe 7:

dieser Code-Block Gegeben:

int func_1(struct node* node) 
{ 
    if (node == NULL) 
     return 0; 
    else 
     return func_1(node->left) + 1 + func_1(node->right); 
} 

Und der Binary Search Baum:

Der Rückgabewert ist 7.

Ich weiß, Rekursion und es ist ein bisschen einfach hier, ich versuchte zu folgen und ich kann nicht verstehen, wie es zurückkam 7. Ich berechnete, dass es nur links geht, links, dann einmal richtig, und das ist es. was wird 3. Und selbst wenn es 3 Mal richtig geht, nach der Wurzel, wird es immer noch 6 zurückgeben und nicht 7.

Können Sie mir bitte helfen?

Answer 1

Semantisch nimmt es die Anzahl der linken Knoten + 1 (der aktuelle Knoten) + die Anzahl der rechten Knoten.

mit func_1 (x) Ich meine die Funktion auf diesem bestimmten Knoten aufrufen.

So ist die vollständige Berechnung ist

• func_1 (8) + 1 + func_1 (14)
• (func_1 (7) + 1 + func_1 (9)) + 1 + func_1 (14)
• (1 + 1 + 1) + 1 + (0 + 1 + func_1 (17)
• 3 + 1 + (0 + 1 + (0 + 1 + func_1 (18))
• 3 + 1 + (1 + (1 + (0 + 1 + 0)
• Ergebnisse in 7

Dieses Prinzip sehr oft in Rekursion verwendet:

• zunächst für den ‚aktuellen‘ Artikel, die Berechnung tun (der aktuelle Knoten), in diesem Fall die Anzahl der Knoten für den ‚Knoten selbst‘ ist 1. Fügen Sie die Berechnung der anderen Elemente rekursiv hinzu, in diesem Fall die Anzahl der Knoten, die vom aktuellen Knoten übrig sind, und die Anzahl der Knoten rechts vom aktuellen Knoten. Aus Bestellgründen wird in diesem Fall die +1 für den aktuellen Knoten (Anzahl der Knoten) in die Mitte gelegt.

Answer 2

Werfen Sie einen Blick auf dem Blattknoten 7.

Wenn func_1 mit dem Wert des Knotens 7, die if-Anweisung wird verzweigen in den else-Teil genannt wird, da der Zeiger auf diesen Knoten gültig ist.

Dann wird func_1 zweimal einmal für das linke Kind und einmal für das richtige Kind aufgerufen. In beiden Fällen geben die Funktionen 0 zurück, da linkes und rechtes Kind NULL sind. Die Funktion gibt 1 zurück:

return func_1(node->left) + 1 + func_1(node->right); 

äquivalent zu:

return func_1(NULL) + 1 + func_1(NULL); 

wird:

return 0 + 1 + 0; 

Answer 3

Blick auf diese Aussage

return func_1(node->left) + 1 + func_1(node->right); 
          ^^^^^ 

Wenn ein Knoten nicht gleich ist, NULL zählt es plus die Zahl von Knoten in den linken und rechten Unterbäumen relativ zu diesem Knoten.

So erhalten Sie ein Ergebnis, das gleich der Anzahl der Knoten ist, die ungleich NULL sind.