ตรวจสอบความสมบูรณ์ของไบนารีทรีใน C++

สมมติว่าเรามีต้นไม้ไบนารี เราต้องตรวจสอบว่าต้นไม้นั้นเป็นต้นไม้ไบนารีที่สมบูรณ์หรือไม่ ต้นไม้ไบนารีที่สมบูรณ์ของระดับ n มีระดับที่สมบูรณ์ n-1 และโหนดทั้งหมดที่ระดับ n ถูกเติมจากด้านซ้าย ดังนั้นหากแผนผังอินพุตเป็น −

จากนั้นผลลัพธ์จะเป็นจริง เนื่องจากเป็นไบนารีทรีที่สมบูรณ์

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• หากต้นไม้ว่างเปล่า ให้คืนค่า null

• สร้างคิว q และแทรกรูทเข้าไป

• ตั้งค่าสถานะ :=true

• ในขณะที่ q มีองค์ประกอบบางอย่าง

  • sz :=ขนาดของคิว

  • ในขณะที่ sz ไม่ใช่ 0

    • โหนด :=โหนดหลังจากลบออกจากคิว

    • หากโหนดออกจากทรีย่อยแล้ว

      • หากตั้งค่าสถานะไว้ ให้แทรกทรีย่อยด้านซ้ายของโหนดลงใน q มิฉะนั้นจะคืนค่าเท็จ

    • มิฉะนั้น flag :=false

    • ถ้าโหนดมีทรีย่อยที่ถูกต้องแล้ว

      • หากตั้งค่าสถานะไว้ ให้แทรกแผนผังย่อยด้านขวาของโหนดลงใน 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}

ผลลัพธ์

1