home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

หาองค์ประกอบที่ k-th smallest ใน BST (Order Statistics in BST) ใน C++

สมมติว่าเรามี binary search tree และค่า K เป็น input เราต้องหา K-th smallest element ใน tree

ดังนั้น ถ้า input เป็นแบบ

หาองค์ประกอบที่ k-th smallest ใน BST (Order Statistics in BST) ใน C++

k = 3 แล้ว output จะเป็น 15

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

  • กำหนดฟังก์ชัน find_kth_smallest() ซึ่งจะรับ root, count, k

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

    • คืนค่า NULL

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

  • ถ้า left ไม่ใช่ NULL แล้ว −

    • คืนค่า left

  • (เพิ่ม count ขึ้น 1)

  • ถ้า count เท่ากับ k แล้ว −

    • คืนค่า root

  • คืนค่า find_kth_smallest(right of root, count, k)

  • จาก main method ให้ทำดังนี้ −

  • count := 0

  • res = find_kth_smallest(root, count, k)

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

    • แสดง not found

  • มิฉะนั้น

    • แสดงค่า val ของ res

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