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

Giả sử chúng ta có một cây tìm kiếm nhị phân và giá trị K làm đầu vào, chúng ta phải tìm K phần tử nhỏ nhất trong cây.

Vì vậy, nếu đầu vào giống như

k =3, thì đầu ra sẽ là 15.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm find_kth_smallest (), hàm này sẽ lấy root, count, k,

• nếu gốc là NULL, thì -

  • trả về NULL

• left =find_kth_smallest (left of root, count, k)

• nếu trái không phải là NULL, thì -

  • quay lại bên trái

• (tăng số lượng lên 1)

• nếu số đếm bằng k, thì -

  • trả về thư mục gốc

• trả về find_kth_smallest (bên phải gốc, số đếm, k)

• Từ phương thức chính, thực hiện như sau -

• đếm:=0

• res =find_kth_smallest (root, count, k)

• nếu res là NULL, thì -

  • không tìm thấy màn hình

• Nếu không

  • giá trị hiển thị của res

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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