PAT程序设计考题——甲级1066（Root of AVL Tree ） C++实现。
#include
#include
#include
#include
#include
struct node{
int num,height;
node *lchild,*rchild;
};
node* newnode(int v)
{ node *root;
root=new node;
root->num=v;
root->height=1;
root->lchild=root->rchild=NULL;
return root;
}
int getheight(node *root)
{ if(root==NULL) return 0;
return root->height;
}
int getbalancefactor(node *root )
{
return getheight(root->lchild)-getheight(root->rchild);
}
void updateheight(node* root)
{
root->height=max(getheight(root->lchild),getheight(root->rchild))+1;
}
void L(node *&root){
node *temp;
temp=root->rchild;
root->rchild=temp->lchild;
temp->lchild=root;
updateheight(root);
updateheight(temp);
root=temp;
}
void R(node *&root)
{
node *temp;
temp=root->lchild;
root->lchild=temp->rchild;
temp->rchild=root;
updateheight(root);
updateheight(temp);
root=temp;
}
void insert(node* &root,int v)
{
if(root==NULL) {
root=newnode(v);
return;}
if(root->num>v)
{
insert(root->lchild,v);
updateheight(root);
if(getbalancefactor(root)==2)
{ if(getbalancefactor(root->lchild)==1)
{ R(root);
}
else if(getbalancefactor(root->lchild)==-1)
{ L(root->lchild);
R(root);
}}}
else{
insert(root->rchild,v);
updateheight(root);
if(getbalancefactor(root)==-2){
if(getbalancefactor(root->rchild)==1)
{
R(root->rchild);
L(root);
}
elseif(getbalancefactor(root->rchild)==-1)
{ L(root);
}
}
}
}
int main(){
int num;
cin>>num;
node *root;
int qw;
for(int i=0;i
{
cin>>qw;
insert(root,qw);
}
cout<
num;
return 0;
}