ค้นหาองค์ประกอบที่เล็กที่สุดที่ k ใน BST (สถิติการสั่งซื้อใน BST) ใน C ++

สมมติว่าเรามีแผนผังการค้นหาแบบไบนารีและมีค่า K เป็นอินพุต เราต้องหาองค์ประกอบที่ K-th น้อยที่สุดในแผนผัง

ดังนั้นหากอินพุตเป็นแบบ

k =3 แล้วผลลัพธ์จะเป็น 15

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน find_kth_smallest() ซึ่งจะทำการรูท นับ k

• ถ้ารูทเป็น NULL ดังนั้น −

  • คืนค่า NULL

• left =find_kth_smallest(ซ้ายของรูท, นับ, k)

• ถ้าเหลือไม่เป็นโมฆะ −

  • กลับซ้าย

• (เพิ่มจำนวนขึ้น 1)

• หากการนับเท่ากับ k แล้ว −

  • คืนค่ารูท

• ส่งคืน find_kth_smallest(ทางขวาของรูท, นับ, k)

• จากวิธีหลัก ให้ทำดังนี้ −

• นับ :=0

• res =find_kth_smallest(root, count, k)

• ถ้า res เป็น NULL แล้ว −

  • ไม่พบการแสดงผล

• มิฉะนั้น

  • แสดงค่าความละเอียด

ตัวอย่าง (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);
}

อินพุต

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

ผลลัพธ์

15