AVL树的实现代码
#include"stdio.h"
#include <stdlib.h>
#include"string.h"
typedef struct tree /*树结构*/
{
int i; /*数据区*/
int treehigh; /*存放节点深度*/
struct tree *lift;
struct tree *right;
}tree;
tree *creatjiedian() /*创建节点*/
{
tree *p;
p=(tree*)malloc(sizeof(tree));
if(p==NULL)
printf("地址申请失败");
else
{
p->lift=p->right=NULL;
p->treehigh=0;
}
return p;
}
int ax(int a,int b) /*比较数的大小*/
{
if(a>b)
return a;
else
return b;
}
tree *charujiedian(tree *p,int x) /*将节点插入到AVL树里*/
{
if(p==NULL)
{
p=creatjiedian();
p->i=x;
}
else if(p->i>x)
{
p->lift=charujiedian(p->lift,x);
p->lift->treehigh=p->treehigh+1; /*计算节点的深度*/
}
else if(p->i<x)
{
p->right=charujiedian(p->right,x);
p->right->treehigh=p->treehigh+1; /*计算节点的深度*/
}
return p;
}
tree *zuodanxuan(tree *p) /*在P的左儿子的左子树的插入 左旋转*/
{
tree *p1;
p1=p->lift;
p->lift=p1->right;
p1->right=p;
return p1;
}
tree *youdanxuan(tree *p) /*在p的右儿子的右子树上的插入 右旋转*/
{
tree *p1;
p1=p->right;
p->right=p1->lift;
p1->lift=p;
return p1;
}
tree *zuoshuangxuan(tree *p) /*在P的左儿子的右子树上的插入 右单旋+左单旋转*/
{
tree *p1;
p1=p->lift;
p->lift=youdanxuan(p1);
return zuodanxuan(p);
}
tree *youshuangxuan(tree *p) /*在P的右儿子的左子树上的插入*/
{
tree *p1;
p1=p->right;
p->right=zuodanxuan(p1);
return youdanxuan (p);
}
void zenggengxin(tree *p) /*将P的所有子树深度加1*/
{
if(p!=NULL)
{
p->treehigh++;
zenggengxin(p->lift);
zenggengxin(p->right);
}
}
void jiangengxin(tree *p) /*将P的所有子树深度减1*/
{
if(p!=NULL)
{
p->treehigh--;
jiangengxin(p->lift);
jiangengxin(p->right);
}
}
void dayin(tree *p) /*先序遍历*/
{
if(p!=NULL)
{
printf("%d %d\n",p->i,p->treehigh);
dayin(p->lift);
dayin(p->right);
}
}
int high(tree *p) /*计算P的树高*/
{
int n;
if(p==NULL)
n=-1;
else
{
if(p->lift==NULL&&p->right==NULL)
n=0;
else if(p->lift!=NULL&&p->right==NULL)
n=1+high(p->lift);
else if(p->lift==NULL&&p->right!=NULL)
n=1+high(p->right);
else
n=1+ax(high(p->right),high(p->lift));
}
return n;
}
tree *avlpingheng(tree *p2,int x) /*AVL树的自我平衡*/
{
tree *p;
if(x<p2->i&&x<p2->lift->i)
{
p=zuodanxuan(p2);
if(p->lift!=NULL) /*经过平衡后，重新更新子树的深度*/
jiangengxin(p->lift);
p->right->treehigh++;
if(p->right->right!=NULL)
zenggengxin(p->right->right);
}
else if(x<p2->i&&x>p2->lift->i)
{
p=zuoshuangxuan(p2);
if(p->lift->right!=NULL) /*经过平衡后，重新更新子树的深度*/
jiangengxin(p->lift->right);
if(p->right->lift!=NULL)
jiangengxin(p->right->lift);
if(p->right->right!=NULL)
zenggengxin(p->right->right);
p->right->treehigh++;
}
else if(x>p2->i&&x>p2->right->i)
{
p=youdanxuan(p2);
if(p->right!=NULL)
jiangengxin(p->right); /*经过平衡后，重新更新子树的深度*/
p->lift->treehigh++;
if(p->lift->lift!=NULL)
zenggengxin(p->lift->lift);
}
else
{
p=youshuangxuan(p2);
if(p->right->lift!=NULL) /*经过平衡后，重新更新子树的深度*/
jiangengxin(p->right->lift);
if(p->lift->right!=NULL)
jiangengxin(p->lift->right);
if(p->lift->lift!=NULL)
zenggengxin(p->lift->lift);
p->lift->treehigh++;
}
return p;
}
void main()
{
tree *p,*p1,*p2,*root,*p3,*p4; /*root记录当前树根，P1用来查找从根到插入点的路径，p2记录每次查找的子树的父亲 p3记录失衡点的父亲，p4记录失衡点*/
int i,j; /*i用来标记是否有失衡点（1个或者多个）j用来记录树结构体数据的*/
p=creatjiedian();
root=p;
printf("请输入根节点数据:\n");
scanf("%d",&j);
p->i=j;
i=0;
printf("请输入节点数据:\n");
scanf("%d",&j);
charujiedian(root,j);
p1=root;
while(j!=0) /*创建AVL树约定输入0为结束*/
{
charujiedian(root,j);
while(p1->i!=j) /*遍历从根到插入数据的路径*/
{
if(high(p1->lift)-high(p1->right)==2||high(p1->lift)-high(p1->right)==-2) /*判定是否为失衡点，并找出最接近插入点的失衡点*/
{
i++;
p3=p2;
p4=p1;
if(j>p1->i)
{
p2=p1;
p1=p1->right;
}
else
{
p2=p1;
p1=p1->lift;
}
}
else
{
if(j>p1->i)
{
p2=p1;
p1=p1->right;
}
else
{
p2=p1;
p1=p1->lift;
}
}
}
if(i==1) /*i=1 代表根是不平衡点*/
{
root=avlpingheng(p4,j);
root->treehigh--;
}
else if(i>1) /*代表子树是不平衡点*/
{
p4=avlpingheng(p4,j);
if(p4->i<p3->i)
p3->lift=p4;
else
p3->right=p4;
p4->treehigh=p3->treehigh+1;
}
p1=root; /*p1也必须重置，因为只两个是循环和判断的起始*/
i=0; /*i值必须重置*/
printf("请输入节点数据:\n");
scanf("%d",&j);
}
dayin(root); /*打印*/
}
