BST 中的范围搜索

Question

我需要在二叉搜索树中执行范围搜索功能，这将给出给定项的编号 range.i 不明白如何在找到时增加计数值 items.because, 我必须使用递归函数 & 如果我在递归过程中将计数变量初始化为 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

据我了解，由于 count 在 rangeSearch 中是本地的，必须按如下方式更改实现以实现所需的评估。

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)
        count += rangeSearch( node->left, leftBound, rightBound );
    if( node->right!=0 & node->item < rightBound )
        count += rangeSearch( node->right, leftBound, rightBound );
    return count;
}

Answer 2

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

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

-解决"base case"，这通常是微不足道的。（对于大多数数据结构，这通常是空结构或单元素结构。）

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

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

我们要计算 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;
          }
    }
}

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

BST 中的范围搜索

Range Search in BST

c

binary-search-tree