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

C++ में बाइनरी सर्च ट्री में निकटतम तत्व खोजें


मान लीजिए हमारे पास एक बाइनरी सर्च ट्री (BST) और एक लक्ष्य मान है; हमें उस दिए गए BST में k मान खोजने हैं जो लक्ष्य के सबसे निकट हैं। यहां लक्ष्य मान एक फ्लोटिंग-पॉइंट संख्या है। हम मान सकते हैं कि k हमेशा वैध है, और k ≤ कुल नोड्स।

उदाहरण के लिए, यदि इनपुट इस तरह का है:

C++ में बाइनरी सर्च ट्री में निकटतम तत्व खोजें

लक्ष्य = 3.714286, और k = 2, तो आउटपुट [4,3] होगा।

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

  • pushSmaller() फंक्शन परिभाषित करें, जो नोड, स्टैक st, और लक्ष्य लेता है:
    • जब तक नोड मौजूद है:
      • यदि नोड का मान < लक्ष्य, तो नोड को st में डालें, नोड := नोड का दायां
      • अन्यथा नोड := नोड का बायां
  • pushLarger() फंक्शन परिभाषित करें, जो नोड, स्टैक st, लक्ष्य लेता है:
    • जब तक नोड मौजूद है:
      • यदि नोड का मान >= लक्ष्य, तो नोड को st में डालें, नोड := नोड का बायां
      • अन्यथा नोड := नोड का दायां
  • मेन मेथड से:
    • रिट नामक एक ऐरे परिभाषित करें
    • स्मॉलर नामक एक स्टैक परिभाषित करें
    • लार्जर नामक एक स्टैक परिभाषित करें
    • pushLarger(रूट, लार्जर, लक्ष्य)
    • pushSmaller(रूट, स्मॉलर, लक्ष्य)
    • जब तक k शून्येतर है, प्रत्येक चरण में k घटाएं:
      • यदि स्मॉलर खाली नहीं है और (लार्जर खाली है या |लक्ष्य - स्मॉलर के शीर्ष तत्व का मान| < |लक्ष्य - लार्जर के शीर्ष तत्व|):
        • करंट = स्मॉलर का शीर्ष तत्व
        • स्मॉलर से तत्व हटाएं
        • करंट के मान को रिट के अंत में डालें
        • pushSmaller(करंट का बायां, स्मॉलर, लक्ष्य)
      • अन्यथा:
        • करंट = लार्जर का शीर्ष तत्व
        • लार्जर से तत्व हटाएं
        • करंट के मान को रिट के अंत में डालें
        • pushLarger(करंट का दायां, लार्जर, लक्ष्य)
    • रिट लौटाएं

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } class TreeNode{ public: int val; TreeNode *left, *right; TreeNode(int data){ val = data; left = NULL; right = NULL; } }; void insert(TreeNode **root, int val){ queue<TreeNode*> q; q.push(*root); while(q.size()){ TreeNode *temp = q.front(); q.pop(); if(!temp->left){ if(val != NULL) temp->left = new TreeNode(val); else temp->left = new TreeNode(0); return; } else{ q.push(temp->left); } if(!temp->right){ if(val != NULL) temp->right = new TreeNode(val); else temp->right = new TreeNode(0); return; } else{ q.push(temp->right); } } } TreeNode *make_tree(vector<int> v){ TreeNode *root = new TreeNode(v[0]); for(int i = 1; i<v.size(); i++){ insert(&root, v[i]); } return root; } class Solution { public: vector<int> closestKValues(TreeNode* root, double target, int k){ vector<int> ret; stack<TreeNode*> smaller; stack<TreeNode*> larger; pushLarger(root, larger, target); pushSmaller(root, smaller, target); while (k--) { if (!smaller.empty() && (larger.empty() || (abs(target - smaller.top()->val) < abs(target - larger.top()->val)))) { TreeNode* curr = smaller.top(); smaller.pop(); ret.push_back(curr->val); pushSmaller(curr->left, smaller, target); } else { TreeNode* curr = larger.top(); larger.pop(); ret.push_back(curr->val); pushLarger(curr->right, larger, target); } } return ret; } void pushSmaller(TreeNode* node, stack <TreeNode*>& st, double target){ while (node) { if (node->val < target) { st.push(node); node = node->right; } else { node = node->left; } } } void pushLarger(TreeNode* node, stack <TreeNode*>& st, double target){ while (node) { if (node->val >= target) { st.push(node); node = node->left; } else node = node->right; } } }; main(){ Solution ob; vector<int> v = {4,2,5,1,3}; TreeNode *root = make_tree(v); print_vector(ob.closestKValues(root, 3.7142, 2)); }

इनपुट

{4,2,5,1,3}, 3.7142, 2

आउटपुट

[4, 3, ]

  1. C++ में बाइनरी ट्री में निकटतम लीफ ढूंढें C++ में बाइनरी ट्री में निकटतम लीफ ढूंढें

    मान लीजिए, एक बाइनरी ट्री दिया गया है। इसमें अलग-अलग लेवल पर लीफ नोड्स हैं। एक और पॉइंटर दिया गया है, जो एक नोड को इंगित कर रहा है। हमें इंगित नोड से निकटतम लीफ नोड की दूरी ढूंढनी है। ट्री को नीचे जैसा मानें - यहां लीफ नोड्स 2, -2 और 6 हैं। यदि पॉइंटर नोड -5 पर इंगित कर रहा है, तो -5 से निकटतम नोड

  1. C++ में बाइनरी सर्च ट्री में न्यूनतम मान वाला नोड ज्ञात करें C++ में बाइनरी सर्च ट्री में न्यूनतम मान वाला नोड ज्ञात करें

    मान लीजिए हमारे पास एक बाइनरी सर्च ट्री है। हमें बाइनरी सर्च ट्री में न्यूनतम तत्व ढूंढना है। इसलिए यदि BST नीचे की तरह है: न्यूनतम तत्व 1 होगा। जैसा कि हम जानते हैं कि बायां उपट्री हमेशा छोटे तत्वों को धारण करता है। इसलिए यदि हम बाएं उपट्री के माध्यम से तब तक ट्रैवर्स करते हैं जब तक बायां NULL नही

  1. पायथन में बाइनरी सर्च ट्री में Kवां सबसे छोटा तत्व खोजने का प्रोग्राम पायथन में बाइनरी सर्च ट्री में Kवां सबसे छोटा तत्व खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी सर्च ट्री और एक पूर्णांक k है, हमें ट्री में kवां सबसे छोटा मान ढूंढना है। उदाहरण के लिए, यदि इनपुट निम्न ट्री है: k = 3, तो आउटपुट 7 होगा। इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे (इटरेटिव इनऑर्डर ट्रैवर्सल): stack := [], i := 0, ans := -1। जब तक stack खाली