#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);                          /*打印*/

}

送给伸手党

shang