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语句中的条件

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( "%lld\n", sumTheTreeValues( head ) );

    return 0;
}

它的输出是

45