PAT甲级1123 Is It a Complete AVL Tree完全AVL树

小鱼儿 2023-03-13 13:02 83阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]  
在AVL树的基础上增加了层次遍历，对于是否时完全二叉树的判别，采用方法是当读到某个结点的左孩子或者右孩子为空的时候退出循环，如果不为空，则递增cnt，最后判断cnt是否等于n,如果等于表明已经全部读完，是完全二叉树

#include<iostream>
    #include<vector>
    #include<algorithm>
    #include<queue>
    using namespace std;
    struct node{ 
        int data,height;
        node *l,*r;
    };
    int cnt=1;
    bool flag=true;
    vector<node*> levelorder;
    int getheight(node* root)
    { 
        if(root==NULL)return 0;
        else return root->height;
    }
    int getbalancefactor(node* root)
    { 
        return getheight(root->l)-getheight(root->r);
    }
    void updataheight(node* &root)
    { 
        root->height=max(getheight(root->l),getheight(root->r))+1;
    }
    void left_rotation(node* &root)
    { 
        node* temp=root->r;
        root->r=temp->l;
        temp->l=root;
        updataheight(root);
        updataheight(temp);
        root=temp;
    }
    void right_rotation(node* &root)
    { 
        node* temp=root->l;
        root->l=temp->r;
        temp->r=root;
        updataheight(root);
        updataheight(temp);
        root=temp;
    }
    void insert(node* &root,int x)
    { 
        if(root==NULL)
        { 
            root=new node;
            root->data=x;
            root->height=1;
            root->l=root->r=NULL;
            return;
        }
        if(x<root->data)
        { 
            insert(root->l,x);
            updataheight(root);
            if(getbalancefactor(root)==2)
            { 
                if(getbalancefactor(root->l)==1)
                { 
                    right_rotation(root);
                }
                else
                { 
                    left_rotation(root->l);
                    right_rotation(root);
                }
            }
        }
        else
        { 
            insert(root->r,x);
            updataheight(root);
            if(getbalancefactor(root)==-2)
            { 
                if(getbalancefactor(root->r)==-1)left_rotation(root);
                else
                { 
                    right_rotation(root->r);
                    left_rotation(root);
                }
            }
        }
    }
    void level_order(node* root)
    { 
        queue<node*> q;
        q.push(root);
        levelorder.push_back(root);
        while(!q.empty())
        { 
            node* it=q.front();
            q.pop();
            if(it->l!=NULL)
            { 
                q.push(it->l);
                levelorder.push_back(it->l);
            }
            if(it->r!=NULL)
            { 
                q.push(it->r);
                levelorder.push_back(it->r);
            }
        }
    }
    void judge(node* root)
    { 
    	queue<node*> q;
        q.push(root);
        while(!q.empty())
        { 
            node* it=q.front();
            q.pop();
            if(it->l!=NULL)
            { 
                q.push(it->l);
                cnt++;
            }
            else break;
            if(it->r!=NULL)
            { 
                q.push(it->r);
                cnt++;
            }
            else break;
        }
    }
    int main()
    { 
        int n,temp;
        cin>>n;
        node* rot=NULL;
        for(int i=0;i<n;i++)
        { 
            cin>>temp;
            insert(rot,temp);
        }
        level_order(rot);
        for(int i=0;i<n;i++)
        { 
            cout<<levelorder[i]->data;
            if(i!=n-1)cout<<" ";
            else cout<<endl;
        }
        judge(rot);
        if(cnt==n)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]: /images/20230312/4e3f25eebfba401fb7e7fc6c77f712cf.png