PAT甲级1123.

目录

A1123

题目

样例

样例1

输入:

5
88 70 61 63 65

输出:

70 63 88 61 65
YES

样例2

输入:

8
88 70 61 96 120 90 65 68

输出:

88 65 96 61 70 90 120 68
NO

思路和坑点

　　思路：
　　先根据AVL树的规则进行建树，建树后进行判定。AVL树的相关操作可以参考算法笔记中的介绍，这里不做详细讲解，或者去看二叉树总结那篇文章中的讲解；完全二叉树的判定使用层序遍历的方法，所以层序序列的遍历输出也可以同时进行。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef struct node{
    int data,high;
    struct node    *lchild,*rchild;
}Node,*Tree; 
//结点相关的函数 
Node * newnode (int x);             //新建结点
int gethigh(Node *root);            //获取树的高度
int getbf(Node *root);              //获取平衡因子
void updatahigh(Node *root);        //更新树的高度
//旋转调整和插入
void L(Node *&root);                //左旋
void R(Node *&root);                //右旋
void Insert(Node *&root,int x);     //插入函数
void Judge(Node *root);             //判断函数，判断树是不是完全二叉树
void layorder(Tree root);           //层序遍历
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    int n;
    scanf("%d",&n);
    Tree root=NULL;                 //一定要初始化，不然野指针有可能导致段错误 
    for(int i=0;i<n;i++){           //进行插入建AVL树
        int temp;
        scanf("%d",&temp);
        Insert(root,temp);
    }
    Judge(root);                    //判定函数
    return 0;    
}
Node * newnode (int x)
{
    Node * root=new node;
    root->data=x;
    root->high=1;
    root->lchild=root->rchild=NULL;
    return root;
}
int gethigh(Node *root){
    if(root==NULL) return 0;
    else    return root->high;
}
int getbf(Node *root){
    return gethigh(root->lchild)-gethigh(root->rchild);
}
void updatahigh(Node *root){
    root->high=max(gethigh(root->lchild),gethigh(root->rchild))+1;
}
void L(Node *&root){
    Node *temp=root->rchild;
    root->rchild=temp->lchild;
    temp->lchild=root;
    updatahigh(root);
    updatahigh(temp);
    root=temp;
}
void R(Node *&root){
    Node *temp=root->lchild;
    root->lchild=temp->rchild;
    temp->rchild=root;
    updatahigh(root);
    updatahigh(temp);
    root=temp;
}
void Insert(Node *&root,int x){
    if(root==NULL){
        root=newnode(x);
        return ;
    }
    if(x<root->data){
        Insert(root->lchild,x);
        updatahigh(root);
        if(getbf(root)==2){
            if(getbf(root->lchild)==1){
                R(root);
            }
            else if(getbf(root->lchild)==-1){
                L(root->lchild);
                R(root);
            }
        }
    }
    else{
        Insert(root->rchild,x);
        updatahigh(root);
        if(getbf(root)==-2){
            if(getbf(root->rchild)==-1){
                L(root);
            }
            else if(getbf(root->rchild)==1){
                R(root->rchild);
                L(root);
            }
        }
    }
}
void Judge(Node *root){                         //判断和层序遍历一起进行，因为完全二叉树的判定本来就通过层序进行的
    int cnt=0;
    bool flag=true;                             //输出格式计数器，falg为判定标记
    queue<Node *> q;
    q.push(root);
    while(!q.empty()){
        Node* now=q.front();
        q.pop();
        if(now!=NULL){                          //如果结点不空，输出并入队
            if(cnt++) putchar(' ');
            printf("%d",now->data);
            q.push(now->lchild);
            q.push(now->rchild);
        }
        else{
            while(!q.empty()){                  //如果遇到一个空结点，则如果后序还有非空结点则不是完全二叉树
                now=q.front();
                q.pop();
                if(now!=NULL){                  //如果后序有非空结点则输出，并修改标记，将其孩子入队
                    flag=false;
                    if(cnt++) putchar(' ');
                    printf("%d",now->data);
                    q.push(now->lchild);
                    q.push(now->rchild);
                }
            }
        }
    }
    putchar('\n');
     puts(flag?"YES":"NO");
}