查找 bst 中所有非终端节点的总和

Question

我该如何更正这个程序？

给我输出 0。请帮帮我。我是编程新手。我试过输入 10,15,9,8 它给我的输出为零或一些大数。我知道这是一个愚蠢的问题，但我找不到答案



void findProductSum(struct node* root, int sum)
{

    if (root == NULL || (root->left == NULL&& root->right == NULL))
        return;


    if (root->left != NULL || root->right != NULL)
    {

        sum += root->data;
        
    }

    findProductSum(root->left,sum);
    findProductSum(root->right,sum);
    return sum;

}```

Answer 1

该函数具有 return 类型 void。所以例如这条语句

return sum;

没有意义。

这个if语句

if (root->left != NULL || root->right != NULL)

是多余的。您已经检查过其中一个指针不等于此语句

中的 NULL

if (root == NULL || (root->left == NULL&& root->right == NULL))

也在函数内更改了它的局部变量sum（参数是函数局部变量）。

因此这些电话

findProductSum(root->left,sum);
findProductSum(root->right,sum);

没有效果。

函数可以这样定义

long long int findProductSum( const struct node* root )
{
    return root == NULL || ( root->left == NULL && root->right == NULL )
           ? 0ll
           : root->data + findProductSum( root->left ) + findProductSum( root->right );
}

并称赞

long long int sum = findProductSum( root );

其中 root 是指向调用者中声明的根节点的指针。

然后就可以像这样输出得到的值

printf( "%lld\n", sum );

这是一个演示程序

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

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

int insert( struct node **root, int data )
{
    struct node *new_node = malloc( sizeof( struct node ) );
    int success = new_node != NULL;
    
    if ( success )
    {
        new_node->data  = data;
        new_node->left  = NULL;
        new_node->right = NULL;
        
        while ( *root != NULL )
        {
            if ( data < ( *root )->data )
            {
                root = &( *root )->left;
            }
            else
            {
                root = &( *root )->right;
            }
        }
        
        *root = new_node;
    }
    
    return success;
}

long long int findProductSum( const struct node* root )
{
    return root == NULL || ( root->left == NULL && root->right == NULL )
           ? 0ll
           : root->data + findProductSum( root->left ) + findProductSum( root->right );
}  

int main(void) 
{
    struct node *root = NULL;
    int data[] = { 10, 15, 9, 8 };
    const size_t N = sizeof( data ) / sizeof( *data );
    
    for ( size_t i = 0; i < N; i++ ) insert( &root, data[i] );
    
    long long int sum = findProductSum( root );
    
    printf( "The sum of non-terminal nodes is equal to %lld\n", sum );
    
    return 0;
}

程序输出为

The sum of non-terminal nodes is equal to 19

值为15和8的节点是终端节点。因此它们的值不会添加到结果总和中。

查找 bst 中所有非终端节点的总和

finding sum of all non terminal node in bst

c

recursion

struct

binary-search-tree

function-definition