如何打印值介于最小值和最大值之间的所有BST节点

Question

我有以下BST供参考。英国夏令时

假设最小值：9 和最大值：20 它满足所有条件，对于每个节点 （X），左侧子树中的所有节点都小于，并且右侧子树中的所有节点都大于 X 的值。

我在创建打印所有值的函数(成员函数，因此它可以访问根节点)时遇到了问题。具体来说，假设我的当前节点是10，但是我仍然需要检查左右两边的子树。我不能在参数中传递节点(否则我会这样做？)，所以我要实现这个功能

void printBetween(int min, int max);

此外，函数应该只访问值可能有效的子树。

假设节点结构如下所示:

struct Node{
        T data_;
        Node* left_;
        Node* right_;
        Node(const T& data, Node* left=nullptr, Node* right=nullptr){
            data_=data;
            left_=left;
            right_=right;
        }        
    };

如果左子项和右子项的值都可以介于最小值和最大值之间，我将如何处理？

void printBetween(int min, int max){
    // left child: smaller than
    // right child: bigger than
    // This function prints every value in the tree that is between min and max inclusive.

    if( root_ == nullptr)
        cout << "No values found" << endl;
    Node* currNode = root_;

   // check until currNode is a valid node 
    while(currNode != nullptr){
        // print value if currNode's data value is between min and max inclusive,
        if(currNode->data_ > min && currNode->data_ <= max){
            cout << "Value: " << data_ << "," << endl;
            fnd = true;
            // since it falls in the range, have to check both children
            // not sure what to do here??
            if(currNode != nullptr && currNode->left_->data_ > min && currNode->left_->data_ <= max){
                 currNode = currNode->left_;   
            } else if(currNode != nullptr && currNode->right_->data_ > min && currNode->right_->data_ <= max){
                 currNode = currNode->right_; 
            }
        }

        // current node's data is too big, so go to its left child
        if(currNode->data_ > max){
            currNode = currNode->left_;
        } 
        // current node's data is too small, so go to its right child
        else if(currNode->data_ < min){
            currNode = currNode->right_;
        } 
    }
}

Answer 1

首先，＜code＞void printBetween（int min，int max）有一个小问题 int应为T。您还应该考虑将min和maxby

如果左子项和右子项的值都可以介于最小值和最大值之间，我将如何处理？

在这些情况下，您需要同时搜索它们。您可以添加一个递归调用的助手成员函数。在下面的例子中，我称之为< code>printer()。您的< code>printBetween()仅用于调用起始值为< code>root_的< code>printer()。

void printer(const T& min, const T& max, Node* currNode) {
    if(currNode == nullptr) return; // end of branch, return

    if(currNode->data_ >= min && currNode->data_ <= max) {     // [min, max]
        // we got a match, both branches must be followed

        printer(min, max, currNode->left_); // call printer for the smaller values

        std::cout << "Value: " << currNode->data_ << '\n';

        printer(min, max, currNode->right_); // call printer for the greater values

    } else if(currNode->data_ < min) {
        // data is less than min, no need to search the left branch
        printer(min, max, currNode->right_);

    } else {
        // data is greater than max, no need to search the right branch
        printer(min, max, currNode->left_);
    }
}

void printBetween(const T& min, const T& max) {
    printer(min, max, root_);
}

另一个注意事项:如果您打算将BST用于非默认构造的类型，您需要使用< code>Node中的成员初始化列表。

例子：

struct Node {
    T data_;
    Node* left_;
    Node* right_;

    Node(const T& data, Node* left=nullptr, Node* right=nullptr) :
        data_(data),
        left_(left),
        right_(right)
    {
        // empty function body
    }        
};

演示