Kiểm tra tính hoàn chỉnh của cây nhị phân trong C ++

Giả sử chúng ta có một cây nhị phân. Chúng ta phải kiểm tra xem cây có phải là một cây nhị phân hoàn chỉnh hay không. Một cây nhị phân hoàn chỉnh ở mức n, có n-1 mức hoàn chỉnh và tất cả các nút ở mức n, được điền từ bên trái. Vì vậy, nếu cây đầu vào giống như -

Khi đó đầu ra sẽ là true, Vì đây là cây nhị phân hoàn chỉnh.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Nếu cây trống, thì trả về null

• tạo một hàng đợi q và chèn root vào đó

• đặt cờ:=true

• trong khi q có một số phần tử

  • sz:=kích thước của hàng đợi

  • trong khi sz không phải là 0

    • node:=node sau khi xóa khỏi hàng đợi

    • nếu nút có cây con bên trái, thì

      • nếu cờ được đặt, sau đó chèn cây con bên trái của nút vào q, othereise trả về false

    • nếu không thì cờ:=false

    • nếu nút có cây con bên phải thì

      • nếu cờ được đặt, thì hãy chèn cây con bên phải của nút vào q, nếu không thì trả về false

    • cờ:=false

    • sz:=sz - 1

• hoàn trả lại

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

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

Đầu ra

1