c++ - 如何打印 BST 中特定范围内的数字，从最高到最低，访问的节点最少？

Question

对于 BST，我想在 [a,b] 中找到节点的值，从最大值到最小值。我能想到的最简单的方法如下：

void printRange(BSTNode<Key,E>* root,int lowValue,int highValue) const
{
    if(root==NULL) return;

    printRange(root->right(),lowValue,highValue);
    if(root->key()>=lowValue&&root->key()<=highValue)
        cout<<root->key()<<" ";

    printRange(root->left(),lowValue,highValue);
}

但我想知道是否有一种方法可以打印出访问的节点较少的这些值？

Answer 1

您正在访问 BST 的所有节点，无论它们是否在范围内。并且只打印所需的值。更精细的算法是：

1. 对 BST 进行中序遍历。

2. 从根开始。

3. 仅当左子树的根小于“lowValue”时才处理左子树以进行中序遍历

4. 仅当右子树的根大于“highValue”时才处理右子树

5. 否则只是从函数返回。

   这样您就可以进行过滤的中序遍历，仅访问 BST 的所需部分。

Answer 2

这个问题的答案，是伪代码，应该是这样的：

void printRange(int lower, int upper, BSTNode * node){
  if (node == NULL) return
  if (node->key <= upper) printRange(lower, upper, node->right);
  if (node->key >= lower && node->key <= upper) printf("%d",node->value);
  if (node->key >= lower) printRange(lower, upper, node->left);
}