打印二叉搜索树范围内的总和

Question

我的代码几乎可以正常工作了，但由于某种原因，它实际上并没有获取每个节点的值并将它们相加。相反，sum 的输出每次都是 0。我认为 btreeSumRange 方法中的 sum = sum + data 行会解决这个问题。知道如何解决这个问题吗？

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

  static long long sum;

  typedef struct node
  {  
      long long data;
      struct node *left;
      struct node *right;
  } node;


node * btreeInsert(node *node,long long data)
{
    if(node==NULL)
    {
        struct node *temp;
        temp = (struct node *)malloc(sizeof(node));
        temp -> data = data;
        temp -> left = temp -> right = NULL;
        return temp;
    }

    if(data >(node->data))
    {
        node->right = btreeInsert(node->right,data);
    }
    else if(data < (node->data))
    {
        node->left = btreeInsert(node->left,data);
    }
    return node;

}

void btreeSumRange(node *tree, long long min,long long max) {
    if (tree == NULL) {
       return;
    }
    btreeSumRange(tree->left, min, max);
    long long data= tree->data;

    if((data>=min)&&(data<=max)){
        sum = sum + data;
    }
    btreeSumRange(tree->right, min, max);
}


int main() {

    node *root;
    long long value;
    root = NULL;

    FILE* data = fopen ("dataA", "r");
    FILE* range = fopen ("rangeA", "r");

    while(fscanf(data, "%lld\n", &value) != EOF){
        printf("%lld\n", value);
        btreeInsert(root, value);
    }

    long long min;
    long long max;

    while(fscanf(range, "%lld %lld\n", &min, &max) != EOF){
        btreeSumRange(root, min, max);
        printf("Range [%lld,%lld]. Sum = %lld. \n", min, max, sum);
    }


    return 0;
}

Answer 1

你的代码有两个问题。

在顶层 root 未由 btreeInsert 的初始调用设置。所以 btreeInsert(root, value); 应该是 root = btreeInsert(root, value);
malloc 调用使用的大小不正确：

temp = (struct node *)malloc(sizeof(node));

混淆来自这样一个事实，即有一个名为 node 的 type 和一个名为 [=15] 的 variable =].在那一行中，它是范围内的 variable。该变量是一个指针，因此 sizeof(node) 给出了指针大小。但是您显然想要结构大小而不是指针大小。建议您通过不重载类型和变量名称来避免将来出现此类混淆。解决这个问题的一种方法是将该行更改为以下内容（顺便说一句，不需要转换）：

temp = malloc(sizeof(*temp));

打印二叉搜索树范围内的总和

Printing Sums within range for a Binary Search Tree

c

binary-search-tree