判断一棵树是否是完全二叉树

r囧r小猫 2022-04-18 01:46 229阅读 0赞

首先要知道完全二叉树的定义： 前n-1层都是满的，第n层如有空缺，则是右边有空缺，即第n层的右边的某个节点开始有空缺，它的左边是满的，右边是空的。

以二叉搜索树举例。

#include <bits/stdc++.h>
    using namespace std;
    typedef struct BNode* BTree;
    struct BNode
    {
        
        int data;
        BTree left;
        BTree right;
    };
    
    void Insert(BTree &t,int data){
        
        if(!t){
        
            BTree p=(BTree)malloc(sizeof(BTree));
            p->data=data;
            p->left=NULL;
            p->right=NULL;
            t=p;
        }
        else if(data<t->data)Insert(t->left,data);
        else if(data>=t->data)Insert(t->right,data);
    }
    
    bool IsComplateTree(BTree root){
        
            queue<BTree> q;
            if (root){
        
                q.push(root);
            }
            bool f = true;
            while (!q.empty()){
        
                BTree front = q.front();
                q.pop();
                if (front->left){
        
                    if (f == false){
        
                        return false;
                    }
                    q.push(front->left);
                }
                else  f = false;
                if (front->right){
        
                    if (f == false){
        
                        return false;
                    }
                    q.push(front->right);
                }
                else f = false;
            }
            return true;
        }
    int main()
    {
        
        int n;
        int a[1001];
        cin>>n;
        BTree t=NULL;
        for(int i=0;i<n;i++){
        
            cin>>a[i];
            Insert(t,a[i]);
        }
        if(IsComplateTree(t))cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }