我正在编写一个程序来遍历预先构建的树。就节点数、节点位置等而言,我对树结构一无所知,但我需要遍历所有节点并对节点的值求和。
节点定义为
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
子项。
最佳答案
对于初学者来说,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
关于c - 树递归编译,但在执行时崩溃,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44812325/