c - 在 BST 中查找从低到高范围内的整数数量 (C)

Question

给定一个高值和一个低值，此函数的要点是找到相等或介于两者之间的数字数量。我使用 5 和 10 作为我的最低值和最高值，并且应该收到 4 的返回结果。因为我使用递归，所以我使用静态变量来跟踪。但是，结果我一直得到 1。为什么？

在我的测试函数中:

int main()
{
  int i;

  int a[] = {8, 2, 7, 9, 11, 3, 2, 6};


  BST_PTR t = bst_create();

  for(i=0; i<8; i++)
    bst_insert(t, a[i]);

    printf("%d\n", bst_num_in_range(t,5,10)); <----- **calls the function here**
  //rest of tests here

int bst_num_in_range(BST_PTR t, int low, int hi)
{
    static int x = 0;

    if ( NULL == t->root)
        return 0;

    return num_in_range_helper(t->root, low, hi, x);
}

int num_in_range_helper(NODE *r , int low, int hi, static int x)
{
    if (r == NULL)
       return 0;

    if (low < r->val)
       num_in_range_helper(r->left, low, hi, x);

    if ( low <= r->val && hi >= r->val )
        x++;

    if (hi > r->val)
        num_in_range_helper(r->right, low, hi, x);

    return x;
}

Answer 1

static 关键字不会使 x 在这两个函数中成为相同的变量。您需要在每次调用后将返回值分配给 x，即尝试这样的操作

int bst_num_in_range(BST_PTR t, int low, int hi)
{
    if ( NULL == t->root)
        return 0;

    return num_in_range_helper(t->root, low, hi);
}

int num_in_range_helper(NODE *r , int low, int hi)
{
    if (r == NULL)
        return 0;

    int x = 0;

    if (low < r->val)
        x += num_in_range_helper(r->left, low, hi);

    if ( low <= r->val && hi >= r->val )
        x++;

    if (hi > r->val)
        x += num_in_range_helper(r->right, low, hi);

    return x;
}

编辑:您也不需要将当前 x 发送给助手，您只需向助手询问两个子树中的顶点数，将它们相加并仅返回当前子树中的总数