PAT甲级1123-Is It a Complete AVL Tree（AVL树，层序遍历））

一.题目

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.

F1.jpg

F2.jpg

F3.jpg

F4.jpg

Now given a sequence of insertions, you are supposed to output the level-order traversal sequence of the resulting AVL tree, and to tell if it is a complete binary tree.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤ 20). Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, insert the keys one by one into an initially empty AVL tree. Then first print in a line the level-order traversal sequence of the resulting AVL tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line. Then in the next line, printYESif the tree is complete, orNOif not.

Sample Input 1:

5
88 70 61 63 65

Sample Output 1:

70 63 88 61 65
YES

Sample Input 2:

8
88 70 61 96 120 90 65 68

Sample Output 2:

88 65 96 61 70 90 120 68
NO

二.题意

给定一个插入序列，判断是不是完全二叉树

三.代码部分

#include<bits/stdc++.h>
using namespace std;
struct node{//定义树形节点
    int val;
    struct node *left,*right;
};
node* leftRotate(node *tree){//左旋部分
    node *temp=tree->right;
    tree->right=temp->left;
    temp->left=tree;
    return temp;
}
node* rightRotate(node *tree){//右旋部分
    node *temp=tree->left;
    tree->left=temp->right;
    temp->right=tree;
    return temp;
}
node* LeftRightRotate(node *tree){//左右旋
    tree->left=leftRotate(tree->left);
    return rightRotate(tree);
}
node *RightLeftRotate(node *tree){//右左旋
    tree->right=rightRotate(tree->right);
    return leftRotate(tree);
}
int getHeight(node *tree){//得到树的高度
    if(tree==NULL)
        return 0;
    int l=getHeight(tree->left);
    int r=getHeight(tree->right);
    return max(l,r)+1;
}
node* insert(node *tree,int val){//树的插入部分
    if(tree==NULL){//树为空的情况
        tree=new node();
        tree->val=val;
    }else if(tree->val>val){//左子树进行插入
        tree->left=insert(tree->left,val);
        int l=getHeight(tree->left),r=getHeight(tree->right);
        if(l-r>=2){//如果左右高度相差为2
            if(val<tree->left->val)//如果小于树的左孩子，则进行右旋
                tree=rightRotate(tree);
            else//否则进行左右旋
                tree=LeftRightRotate(tree);
        }
    }else{//右孩子进行插入
        tree->right=insert(tree->right,val);
        int l=getHeight(tree->left),r=getHeight(tree->right);
        if(r-l>=2){//如果左右高度相差为2
            if(val>tree->right->val)//如果大于树的右孩子，则进行左旋
                tree=leftRotate(tree);
            else//否则进行右左旋
                tree=RightLeftRotate(tree);
        }
    }
    return tree;//返回树的结点
}
int isComplete=1,after=0;//iscomplete为标记是否是完全二叉树，after为标记左右情况
vector<int> levelOrder(node *tree){//层序遍历
    vector<int> v;
    queue<node *> queue;
    queue.push(tree);
    while(!queue.empty()){
        node *temp=queue.front();
        queue.pop();
        v.push_back(temp->val);
        if(temp->left!=NULL){//确保从上到下，从左到右为满树
            if(after)
                isComplete=0;
            queue.push(temp->left);
        }else{
            after=1;
        }
        if(temp->right!=NULL){
            if(after)
                isComplete=0;
            queue.push(temp->right);
        }else{
            after=1;
        }
    }
    return v;
}
int main(){
    int n,temp;
    cin>>n;
    node *tree=NULL;
    for(int i=0;i<n;i++){
        cin>>temp;
        tree=insert(tree,temp);//每次读入之后进行插入
    }
    vector<int> v=levelOrder(tree);//使用vector存储树的信息
    for(int i=0;i<v.size();i++){
        if(i!=0)
            cout<<" ";
        cout<<v[i];
    }
    printf("\n%s",isComplete?"YES":"NO");//是否是完全二叉树，进行输出
    return 0;
}