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

Question

我有以下BST供参考。 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;
        }        
    };

如果左 child 和右 child 的值都介于最小值和最大值之间，我该怎么办？

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

首先，void printBetween(int min, int max); 有一个小问题。 int 应该是 T。您还应该考虑在 const& 之前使用 min 和 max，以防您的 BST 与复制成本很高的类型一起使用。

How would I go about if both the left child and the right child could have a value between min and max?

在这些情况下，您需要同时搜索它们。您可以添加递归调用的辅助成员函数。我在下面的示例中将其称为 printer()。您的 printBetween() 将仅用于以起始值 root_.

调用 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 与不是默认构造的类型一起使用，则需要使用 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
    }        
};

Demo

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

How to print ALL BST nodes with values between min and max

c++

binary-search-tree