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

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

您的代码中有两个问题。

1. 在顶层，初始调用 btreeInsert 并未设置root。所以 btreeInsert(root, value); 应该是 root = btreeInsert(root, value);

2. malloc 调用使用的大小不正确:

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

   造成困惑的原因是，同时存在一个名为 node 的类型和一个名为 node 的变量 。在该行中，它是范围内的变量。该变量是一个指针，因此 sizeof(node) 给出了指针的大小。但您显然需要结构大小而不是指针大小。建议您不要重载类型和变量名称，以避免将来出现此类困惑。解决这个问题的一种方法是将该行更改为以下内容(顺便说一句，无需强制转换):

   temp = malloc(sizeof(*temp));