C++ में एक बाइनरी ट्री की पूर्णता की जाँच करें

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

तब आउटपुट सही होगा, क्योंकि यह पूर्ण बाइनरी ट्री है।

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

अगर पेड़ खाली है, तो अशक्त लौटें
एक कतार q बनाएं और उसमें रूट डालें
ध्वज सेट करें:=सत्य
जबकि q में कुछ तत्व होते हैं
- sz :=कतार का आकार
- जबकि sz 0 नहीं है
  - नोड:=कतार से हटाने के बाद नोड
  - अगर नोड ने सबट्री छोड़ दिया है, तो
    - यदि ध्वज सेट किया गया है, तो नोड के बाएं उपट्री को q में डालें, अन्य रिटर्न गलत है
  - अन्यथा झंडा :=झूठा
  - अगर नोड में सही सबट्री है, तो
    - यदि ध्वज सेट है, तो q में नोड का दायां उपप्रकार डालें, अन्यथा झूठी वापसी करें
  - झंडा :=झूठा
  - sz :=sz – 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 Solution {
   public:
   bool isCompleteTree(TreeNode* root) {
      if(!root)return true;
      queue <TreeNode*> q;
      q.push(root);
      bool isComplete = true;
      while(!q.empty()){
         int sz = q.size();
         while(sz--){
            TreeNode* node = q.front();
            q.pop();
            if(node->left){
               if(isComplete){
                  q.push(node->left);
               }else return false;
            }else{
               isComplete = false;
            }
            if(node->right){
               if(isComplete){
                  q.push(node->right);
               }else return false;
            }else{
               isComplete = false;
            }
         }  
      }
      return true;
   }
};
main(){
   vector<int> v = {1,2,3,4,5,6};
   TreeNode *r1 = make_tree(v);
   Solution ob;
   cout << (ob.isCompleteTree(r1));
}

इनपुट

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