Tìm phần tử nhỏ thứ k trong BST (Thống kê thứ tự trong BST) trong C++

Giả sử có một cây tìm kiếm nhị phân và giá trị K, ta phải tìm phần tử nhỏ thứ K trong cây.

Ví dụ: với cây như hình, K = 3 thì kết quả là 15.

Các bước giải quyết:

• Định nghĩa hàm find_kth_smallest(root, count, k)
• Nếu root là NULL, trả về NULL
• left = find_kth_smallest(left của root, count, k)
• Nếu left khác NULL, trả về left
• Tăng count lên 1
• Nếu count == k, trả về root
• Trả về find_kth_smallest(right của root, count, k)
• Từ main: count = 0, res = find_kth_smallest(root, count, k)
• Nếu res là NULL, in "Not found", ngược lại in giá trị res

Ví dụ (C++)

#include <iostream>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) {
        val = x;
        left = right = NULL;
    }
};
TreeNode* find_kth_smallest(TreeNode* root, int &count, int k) {
    if (root == NULL)
        return NULL;
    TreeNode* left = find_kth_smallest(root->left, count, k);
    if (left != NULL)
        return left;
    count++;
    if (count == k)
        return root;
    return find_kth_smallest(root->right, count, k);
}
void kth_smallest(TreeNode* root, int k) {
    int count = 0;
    TreeNode* res = find_kth_smallest(root, count, k);
    if (res == NULL)
        cout << "Not found";
    else
        cout << res->val;
}
int main() {
    TreeNode* root = new TreeNode(25);
    root->left = new TreeNode(13);
    root->right = new TreeNode(27);
    root->left->left = new TreeNode(9);
    root->left->right = new TreeNode(17);
    root->left->right->left = new TreeNode(15);
    root->left->right->right = new TreeNode(19);
    int k = 3;
    kth_smallest(root, k);
}

Đầu vào

TreeNode* root = new TreeNode(25); root->left = new TreeNode(13); root->right = new TreeNode(27); root->left->left = new TreeNode(9); root->left->right = new TreeNode(17); root->left->right->left = new TreeNode(15); root->left->right->right = new TreeNode(19); k = 3

Đầu ra

15