c - BST 中的范围搜索

Question

我需要在二叉搜索树中执行范围搜索功能，这将给出给定范围内的项目数量。我不明白如何在找到项目时增加计数值。因为，我必须使用递归函数&如果我在递归过程中将计数变量初始化为0，它将始终从0开始计数值，而不是计数中已更新的计数值。

    int rangeSearch(struct treeNode * node, int leftBound, int rightBound) 
    {

        int count=0;
        if( node->item >= leftBound & node->item <= rightBound)
        {
            printf("%d ",node->item);
            count++;
        }
        if( node->left!=0 & node->item > leftBound) rangeSearch( node -> left, leftBound , rightBound );
        else if( node->right!=0 & node->item < rightBound )rangeSearch( node -> right, leftBound , rightBound );
        return count;


    }

Answer 1

这是我的第一个回答，所以我很抱歉我的英语不好。

在每个这样的递归问题中，思考问题的最简单方法是:

-解决“基本情况”，这通常是微不足道的。 (对于大多数数据结构来说，这通常是空结构或单元素结构。)

- 根据构成结构的子结构解决一般情况(例如，在考虑树时，这是在考虑左子树和右子树的情况下完成的)假设您可以依靠子结构的解决方案。

我确信我没有解释清楚，所以让我做一个简单的例子:

我们想要计算 BST 中元素的总数。解决方法是这样的:

int countElement(struct treeNode* node)
{
    if(node == null)
    {
        //we are in the base case: the tree is empty, so we can return zero.
        return 0;
    }
    else
    {
        /*the tree is not empty:
          We return 1 (the element that we are considering)
          + the elements of the left subtree 
          + the elements of the right subtree.*/

          return 1 + countElement(node->left) + countElement(node->right);
    }   
}

如果您清楚这一点，我们可以继续处理您的请求:

int rangeSearch(struct treeNode * node, int leftBound, int rightBound)
{
    if(node == 0)
    {
        //base case: the tree is empty, we can return 0
        return 0;
    }
    else
    {
        /*our tree is not empty.
          Remember that we can assume that the procedure called on
          the left and right child is correct.*/

          int countLeft = rangeSearch(node->left, leftBound, rightBound);
          int countRight = rangeSearch(node->right, leftBound, rightBound);

          /*So what we have to return?
          if the current node->item is between leftbound and rightbound,
          we return 1 (our node->item is valid) + rangeSearch called
          on the left and child subtree with the same identical range.*/

          if(node->item > leftBound && node->item < rightBound)
          {
              /*the element is in the range: we MUST count it 
                in the final result*/
              return 1 + countLeft + countRight;
          }
          else
          {
              /*the element is not in the range: we must NOT count it 
                in the final result*/
              return 0 + countLeft + countRight;
          }
    }
}

请记住，最关键的部分是，如果您很好地定义和解决了基本情况，那么当您考虑更大的结构时，您可以假设您的递归过程调用了该子结构，做了正确的事情并返回正确的值。