Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में BST में k-वां सबसे छोटा तत्व खोजें (BST में ऑर्डर स्टैटिस्टिक्स)


मान लीजिए हमारे पास एक बाइनरी सर्च ट्री और एक मान K इनपुट के रूप में है, हमें ट्री में K-वां सबसे छोटा तत्व ढूंढना है।

तो, यदि इनपुट इस तरह है

C++ में BST में k-वां सबसे छोटा तत्व खोजें (BST में ऑर्डर स्टैटिस्टिक्स)

k = 3, तो आउटपुट 15 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −

  • एक फ़ंक्शन find_kth_smallest() परिभाषित करें, यह रूट, काउंट, k लेगा,

  • यदि रूट NULL है, तो −

    • NULL लौटाएं

  • left = find_kth_smallest(रूट का बायां, काउंट, k)

  • यदि left NULL नहीं है, तो −

    • left लौटाएं

  • (काउंट को 1 से बढ़ाएं)

  • यदि काउंट k के समान है, तो −

    • रूट लौटाएं

  • find_kth_smallest(रूट का दायां, काउंट, k) लौटाएं

  • मुख्य विधि से, निम्नलिखित करें −

  • काउंट := 0

  • res = find_kth_smallest(रूट, काउंट, k)

  • यदि res NULL है, तो −

    • नहीं मिला प्रदर्शित करें

  • अन्यथा

    • 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

  1. - C++ प्रोग्राम: O(n) जटिलता के साथ दूसरा सबसे छोटा तत्व खोजना

    यह C++ प्रोग्राम एक ऐरे में दूसरा सबसे छोटा (Second Smallest) तत्व O(n) समय जटिलता में खोजता है। यह सिंगल पास में दो वेरिएबल्स (सबसे छोटा और दूसरा सबसे छोटा) को मेंटेन करता है। एल्गोरिदम शुरुआत 1. फंक्शन SecondSmallest(): आर्गुमेंट्स: ऐरे पॉइंटर a, तत्वों की संख्या n बॉडी: - s1 (स

  1. - C++ प्रोग्राम: सरणी के पार्टीशन विधि से kवां सबसे छोटा तत्व खोजें

    एल्गोरिदमCreatePartition() फ़ंक्शन बनाएं जिसमें सरणी a, निचली सीमा l और ऊपरी सीमा h हो। in := l और pi := h सेट करें। l से h तक लूप चलाएं, यदि a[i] < a[pi] तो a[i] और a[in] को स्वैप करें और in बढ़ाएं। अंत में a[pi] और a[in] को स्वैप करें और in लौटाएं। Partition() फ़ंक्शन में: यदि low k-1 तो Partitio

  1. - C++ में सरणी का सबसे बड़ा एलिमेंट खोजने का प्रोग्राम

    एक सरणी में कई एलिमेंट्स होते हैं और सरणी में सबसे बड़ा एलिमेंट वह होता है जो अन्य एलिमेंट्स से बड़ा होता है। उदाहरण के लिए। 5 1 7 2 4 उपरोक्त सरणी में, 7 सबसे बड़ा एलिमेंट है और यह इंडेक्स 2 पर है। सरणी का सबसे बड़ा एलिमेंट खोजने का एक प्रोग्राम निम्नलिखित है। उदाहरण #include <iostream>