C-树递归编译，但在执行时崩溃

Question

我正在编写一个程序来穿越预建的树。就节点的数量，节点的位置等，我对树结构一无所知，但是我需要遍历所有节点并总和节点的值。

节点定义为

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

我的递归功能是：

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

编译器不会出现任何错误，但是如果我尝试运行它，它将崩溃而没有消息。只是为了理智检查，我打印了节点值，以确保根不是null。我的预感可能与递归终止可能有关，但是我不太确定还要添加什么，因为我正在检查null儿童。

Answer 1

对于起动器，C中的结构必须像

一样声明

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

如果语句

中的条件

if(!root->left){

等于

if( root->left == NULL ){

因此，当功能等于null时，左右节点的函数被递归地调用。但是，在功能内部没有检查root等于NULL。因此该功能具有不确定的行为。

在if-else语句中封闭函数的呼叫和右节点。

也没有意义。

可以按以下方式定义函数

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

或喜欢

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

这是一个具有两个递归功能的示范性程序。

#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( "%lldn", sumTheTreeValues( head ) );
    return 0;
}

其输出是

45