c++ में एक बाइनरी सर्च ट्री को संतुलित करें

मान लीजिए कि हमारे पास एक बाइनरी सर्च ट्री है, हमें समान नोड मानों के साथ एक संतुलित बाइनरी सर्च ट्री ढूंढना है। एक बाइनरी सर्च ट्री को संतुलित कहा जाता है यदि और केवल तभी जब प्रत्येक नोड के दो उपप्रकारों की गहराई 1 से अधिक से भिन्न न हो। यदि एक से अधिक परिणाम हैं, तो उनमें से किसी को वापस कर दें। तो अगर पेड़ जैसा है -

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

• इनऑर्डर () विधि को परिभाषित करें, यह क्रम ट्रैवर्सल अनुक्रम में एक सरणी में संग्रहीत करेगा

• निर्माण विधि () को परिभाषित करें, इसमें निम्न और उच्च लगेगा -

• यदि कम> उच्च है तो शून्य पर लौटें

• मध्य:=निम्न + (उच्च-निम्न)/2

• रूट :=न्यू नोड वैल्यू arr[mid]

  . के साथ

• रूट का बायां:=निर्माण (निम्न, मध्य -1) और रूट का दायां:=निर्माण (मध्य + 1, उच्च)

• वापसी जड़

• मुख्य विधि से, इनऑर्डर विधि को कॉल करें और निर्माण वापस करें(0, गिरफ्तारी का आकार -1)

उदाहरण (C++)

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

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = 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;
}
void tree_level_trav(TreeNode*root){
   if (root == NULL) return;
      cout << "[";
      queue<TreeNode *> q;
      TreeNode *curr;
      q.push(root);
      q.push(NULL);
      while (q.size() > 1) {
         curr = q.front();
         q.pop();
         if (curr == NULL){
            q.push(NULL);
      } else {
         if(curr->left)
            q.push(curr->left);
         if(curr->right)
            q.push(curr->right);
         if(curr->val == 0 || curr == NULL){
            cout << "null" << ", ";
         }else{
            cout << curr->val << ", ";
         }
      }
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector <int> arr;
   void inorder(TreeNode* node){
      if(!node || node->val == 0) return;
      inorder(node->left);
      arr.push_back(node->val);
      inorder(node->right);
   }
   TreeNode* construct(int low, int high){
      if(low > high) return NULL;
      int mid = low + (high - low) / 2;
      TreeNode* root = new TreeNode(arr[mid]);
      root->left = construct(low, mid - 1);
      root->right = construct(mid + 1, high);
      return root;
   }
   TreeNode* balanceBST(TreeNode* root) {
      inorder(root);
      return construct(0, (int)arr.size() - 1);
   }
};
main(){
   vector<int> v = {1,NULL,2,NULL,NULL,NULL,3,NULL,NULL,NULL,NULL,NULL,NULL,NULL,4};
   TreeNode *root = make_tree(v);
   Solution ob;
   tree_level_trav(ob.balanceBST(root));
}

इनपुट

[1,NULL,2,NULL,NULL,NULL,3,NULL,NULL,NULL,NULL,NULL,NULL,NULL,4]

आउटपुट

[2, 1, 3, 4, ]