Baumrekursion kompiliert, stürzt aber bei Ausführung ab

Question

Ich schreibe ein Programm, um einen vorgefertigten Baum zu durchlaufen. Ich weiß nichts über die Baumstruktur, soweit es die Anzahl der Knoten, die Position der Knoten usw. betrifft, aber ich muss alle Knoten durchqueren und die Werte der Knoten summieren. stürzt nur ohne Nachrichten

int sumTheTreeValues(struct node* root) 
{ 
    int sum = root->value; 
    if(!root->left){ 
    sum = sum + sumTheTreeValues(root->left); 
    } 
    else if(!root->right){ 
     sum = sum + sumTheTreeValues(root->right); 
    } 
    return sum; 
} 

Der Compiler keinen Fehler wirft, aber wenn ich versuche, es zu laufen:

Der Knoten ist definiert als

struct node 
{ 
    int value; 
    node* left; 
    node* right; 
} 

Und meine rekursive Funktion ist die folgende . Nur um die Plausibilitätsprüfung zu überprüfen, druckte ich den Knotenwert, um sicherzustellen, dass der Stamm nicht null ist. Ich habe eine Ahnung, dass es mit Rekursionstermination in Verbindung stehen könnte, aber ich bin mir nicht sicher, was ich noch hinzufügen soll, da ich nach null Kindern suche.

Answer 1

Für den Anfang hat die Struktur in C wie die Funktion ist rekursiv So zu

if(root->left == NULL){ 

gleichwertig if-Anweisung

if(!root->left){ 

ist in dieser

struct node 
{ 
    int value; 
    struct node *left; 
    struct node *right; 
}; 

Die Bedingung erklärt werden aufgerufen für die linken und rechten Knoten, wenn sie gleich NULL sind. Innerhalb der Funktion wird jedoch nicht überprüft, ob root gleich NULL ist. Die Funktion hat also ein undefiniertes Verhalten.

Es ist auch nicht sinnvoll, die Aufrufe der Funktion für den linken und den rechten Knoten in der if-else-Anweisung einzuschließen.

Die Funktion kann auf folgende Weise

long long int sumTheTreeValues(struct node *root) 
{ 
    long long int sum = 0; 

    if (root) 
    { 
     sum = root->value + 
       sumTheTreeValues(root->left) + 
       sumTheTreeValues(root->right); 
    } 

    return sum; 
} 

Oder wie

long long int sumTheTreeValues(struct node *root) 
{ 
    return root == NULL ? 0 
         : root->value + sumTheTreeValues(root->left) 
             + sumTheTreeValues(root->right); 
} 

Hier ist ein demonstratives Programm mit zwei rekursiven Funktionen definiert werden.

#include <stdio.h> 
#include <stdlib.h> 

struct node 
{ 
    int value; 
    struct node *left; 
    struct node *right; 
}; 

void insert(struct node **head, int value) 
{ 
    if (*head == NULL) 
    { 
     *head = malloc(sizeof(struct node)); 
     (*head)->value = value; 
     (*head)->left = NULL; 
     (*head)->right = NULL; 
    } 
    else if (value < (*head)->value) 
    { 
     insert(&(*head)->left, value); 
    } 
    else 
    { 
     insert(&(*head)->right, value); 
    } 
} 

long long int sumTheTreeValues(struct node *root) 
{ 
    return root == NULL ? 0 
         : root->value + sumTheTreeValues(root->left) 
             + sumTheTreeValues(root->right); 
} 

int main(void) 
{ 
    struct node *head = NULL; 
    const int N = 10; 

    for (int i = 1; i < N; i++) 
    { 
     insert(&head, i); 
    } 

    printf("%lld\n", sumTheTreeValues(head)); 

    return 0; 
} 

Sein Ausgang ist

45