C++ में दूषित बाइनरी ट्री में तत्वों का पता लगाएं

मान लीजिए कि हमारे पास एक बाइनरी ट्री है। उस पेड़ के नियम इस प्रकार हैं -

• root.val ==0

• अगर treeNode.val x है और treeNode.left शून्य नहीं है, तो treeNode.left.val =2 * x + 1

• अगर treeNode.val x है और treeNode.right शून्य नहीं है, तो treeNode.right.val =2 * x + 2

अब जैसा कि बाइनरी ट्री दूषित है। यह इंगित करता है कि ट्री नोड के सभी वैल को -1 में बदल दिया गया है। हमें पहले बाइनरी ट्री को रिकवर करना होगा और फिर FindElements क्लास को इस प्रकार लागू करना होगा -

• FindElements(TreeNode* root) दूषित बाइनरी ट्री के साथ ऑब्जेक्ट को इनिशियलाइज़ करता है, हमें पहले इसे रिकवर करना होगा।

• बूल खोज (इंट लक्ष्य)। यदि पुनर्प्राप्त बाइनरी ट्री में लक्ष्य मान मौजूद है, तो यह वापस आ जाएगा।

तो अगर पेड़ जैसा है -

तो ठीक होने के बाद, अगर हम 1, 3 और 5 को खोजने की कोशिश करते हैं, तो परिणाम सही, सही और गलत होंगे।

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

• एक सेट को परिभाषित करें एक

• एक dfs() विधि को परिभाषित करें, यह रूट लेगा, और rootVal. rootVal प्रारंभ में -1

  . है

• यदि रूट शून्य है, तो वापस लौटें

• यदि रूटवैल -1 है, तो रूट का मान 0 के रूप में सेट करें, अन्यथा इसे रूटवैल के रूप में सेट करें

• रूट का मान डालें

• कॉल dfs (रूट के बाएँ, 2* रूट का मान + 1), dfs (रूट का दाएँ, 2* रूट का मान + 2)

• आरंभीकरण, (या पुनर्निर्माण) के लिए, हम dfs(root, -1)

  . को कॉल करेंगे

• किसी तत्व को खोजने के लिए, जांचें कि क्या तत्व एक में होगा या नहीं, यदि ऐसा है तो यह सही है, अन्यथा गलत है।

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;
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 FindElements {
   public:
   set <int> a;
   void dfs(TreeNode* root,int rootVal=-1){
      if(!root)return;
      root->val = rootVal == -1?0:rootVal;
      a.insert(root->val);
      dfs(root->left,2*root->val + 1);
      dfs(root->right, 2*root->val + 2);
   }
   FindElements(TreeNode* root) {
      dfs(root);
   }
   bool find(int t) {
      return a.find(t)!=a.end();
   }
};
main(){
   vector<int> v = {-1,-1,-1,-1,-1};
   TreeNode *root = make_tree(v);
   FindElements ob(root);
   cout << (ob.find(1)) << endl;
   cout << (ob.find(3)) << endl;
   cout << (ob.find(5)) << endl;
}

इनपुट

Initialize the tree with [-1,-1,-1,-1,-1], then call find(1), find(3) and find(5)

आउटपुट

1
1
0