一.题目
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.
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, print YES if the tree is complete, or NO if 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;
}
