1123 Is It a Complete AVL Tree（30 分）

AVL树建立模板写好，之后层序遍历
判断是否为完全二叉树：在出现空子节点之后仍有非空子节点出现则不为完全二叉树

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int n;
struct node {
    int data;
    node *lchild, *rchild;
};
node* Newnode(int x)
{
    node* newnode = new node;
    newnode->data = x;
    newnode->lchild = newnode->rchild = NULL;
    return newnode;
}
int getheight(node* root)
{
    if (root == NULL)return 0;
    else return max(getheight(root->lchild), getheight(root->rchild)) + 1;
}
int getbalance(node* root)
{
    return getheight(root->lchild) - getheight(root->rchild);
}
void R(node* &root)
{
    node *temp = root->lchild;
    root->lchild = temp->rchild;
    temp->rchild = root;
    root = temp;
}
void L(node* &root)
{
    node* temp = root->rchild;
    root->rchild = temp->lchild;
    temp->lchild = root;
    root = temp;
}
void insert(node*&root, int x)
{
    if (root == NULL)
    {
        root = Newnode(x);
    }
    else
    {
        if (x < root->data)
        {
            insert(root->lchild, x);
            if (getbalance(root) == 2)
            {
                if (getbalance(root->lchild) == 1)
                {
                    R(root);
                }
                else if (getbalance(root->lchild) == -1)
                {
                    L(root->lchild);
                    R(root);
                }
            }
        }
        else
        {
            insert(root->rchild, x);
            if (getbalance(root) == -2)
            {
                if (getbalance(root->rchild) == -1)L(root);
                else if (getbalance(root->rchild) == 1)
                {
                    R(root->rchild);
                    L(root);
                }
            }
        }
    }
}
vector<int>ans;
bool iscomplete = true;
int f = 0;
void layerorder(node* root)
{
    queue<node*>q;
    q.push(root);
    while (!q.empty())
    {
        node* front = q.front();
        q.pop();
        ans.push_back(front->data);
        if (front->lchild)
        {
            if (f == 1)iscomplete = false;
            q.push(front->lchild);
        }
        else f = 1;
        if (front->rchild)
        {
            if (f == 1)iscomplete = false;
            q.push(front->rchild);
        }
        else f = 1;
    }
}
int main()
{
    node *root = NULL;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        insert(root, x);
    }
    layerorder(root);
    int valid = 0;
    for (int i = 0; i < ans.size(); i++)if (ans[i] != -1)valid++;
    int k = valid;
    for (int i = 0; i < ans.size(); i++)
    {
        if (ans[i] != -1)
        {
            printf("%d", ans[i]);
            valid--;
            if (valid)printf(" ");
        }
    }
    printf("\n");
    if (iscomplete)printf("YES");
    else printf("NO");
    return 0;
}