范围在BST中搜索

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

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; 


    }

来源

2015-11-20 sat

您需要**使用**递归调用的返回值... – BeyelerStudios

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

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

-resolve的“基本情况”，这通常是微不足道的。（对于大多数数据结构，通常是空结构或单元结构）。

-解决组成结构的子结构的一般情况（例如，当考虑树时，考虑左子树和右子树）假设你可以指望子结构的解决方案。

我敢肯定，我没有解释得很好，所以让我做一个简单的例子：

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

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

来源

2015-11-20 14:33:24

很好解释！：）谢谢哥们！！ – sat

另一个问题：你可以使用C++中的模板来解释函数声明的格式吗？ – sat

据我了解，作为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; 
}

来源

2015-11-20 13:37:58 Codor

您可能需要在'else if'中删除'else' – BeyelerStudios

哦谢谢！有效！！ :) – sat

范围在BST中搜索

回答

相关问题