In khóa BST trong khoảng [k1, k2] C++

Cho cây tìm kiếm nhị phân (BST) và hai giá trị k1, k2. In tất cả khóa trong khoảng [k1, k2] theo thứ tự tăng dần. Sử dụng tính chất BST: duyệt in-order, chỉ đi vào nhánh có thể chứa giá trị trong khoảng.

Duyệt in-order có điều kiện

• Nếu root->data > k1: duyệt cây con trái
• Nếu k1 ≤ root->data ≤ k2: in root->data
• Nếu root->data < k2: duyệt cây con phải

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
};

void printRange(Node* root, int k1, int k2) {
    if (!root) return;
    if (k1 < root->data) printRange(root->left, k1, k2);
    if (k1 <= root->data && root->data <= k2) cout << root->data << '\t';
    if (k2 > root->data) printRange(root->right, k1, k2);
}

Node* insert(Node* root, int key) {
    if (!root) {
        Node* n = new Node();
        n->data = key; n->left = n->right = nullptr;
        return n;
    }
    if (key < root->data) root->left = insert(root->left, key);
    else if (key > root->data) root->right = insert(root->right, key);
    return root;
}

int main() {
    Node* root = nullptr;
    root = insert(root, 20);
    root = insert(root, 10);
    root = insert(root, 24);
    root = insert(root, 8);
    root = insert(root, 15);
    root = insert(root, 32);
    
    int k1 = 12, k2 = 25;
    cout << "Cac khoa trong [" << k1 << "," << k2 << "]: ";
    printRange(root, k1, k2);
    return 0;
}

Kết quả

Cac khoa trong [12,25]: 15 20 24