#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef struct tree
{
int data;
struct tree *left,*right;
int height;
}*Bitree;
int max(int a,int b)
{
return a>b?a:b;
}
int treeheight(Bitree T)
{
return T?T->height:-1;
}
Bitree lrotation(Bitree T)
{
Bitree A=T->left;
T->left=A->right;
A->right=T;
T->height=max(treeheight(T->left),treeheight(T->right))+1;
A->height=max(treeheight(A->left),treeheight(A->right))+1;
return A;
}
Bitree rrotation(Bitree T)
{
Bitree A=T->right;
T->right=A->left;
A->left=T;
T->height=max(treeheight(T->left),treeheight(T->right))+1;
A->height=max(treeheight(A->left),treeheight(A->right))+1;
return A;
}
Bitree lrrotation(Bitree T)
{
T->left=lrotation(T->left);
return rrotation(T);
}
Bitree rlrotation(Bitree T)
{
T->right=rrotation(T->right);
return lrotation(T);
}
void pre(Bitree T)
{
if(T)
{
printf("%d-",T->data);
pre(T->left);
pre(T->right);
}
}
Bitree create(Bitree T,int data)
{
if(T==NULL)
{
T=(struct tree*)malloc(sizeof(struct tree));
T->data=data;
T->left=NULL;
T->right=NULL;
T->height=0;
return T;
}
if(T->data<data)
{
T->right=create(T->right,data);
if(treeheight(T->right)-treeheight(T->left)>1)
{
T=(treeheight(T->right->left)>treeheight(T->right->right))?rlrotation(T):lrotation(T);
}
}
else if(T->data>data)
{
T->left=create(T->left,data);
if(treeheight(T->left)-treeheight(T->right)>1)
{
T=(treeheight(T->left->left)>treeheight(T->left->right))?rrotation(T):rlrotation(T);
}
}
T->height=max(treeheight(T->left),treeheight(T->right))+1;
return T;
}
int main()
{
Bitree T=NULL;
T=create(T,2);
T=create(T,1);
T=create(T,4);
T=create(T,5);
T=create(T,9);
T=create(T,3);
T=create(T,6);
T=create(T,7);
pre(T);
return 0；
｝
- 这里是运行结果
请求高人指点😭
