已经基本实现AVL树插入和查找功能~还差个删除节点(这个以后慢慢弄)~~
记得上次发过一次AVL树~不过那是照着参考代码敲的~

这次和上次不同~虽然有参考过各方面的代码~但大部分内容是原创的~可以看看~~~

感觉高度方面和一些严谨的平衡树差了一些~如果要对比一下可以参考~~
https://bbs.bccn.net/thread-475229-1-1.html
那个贴的代码是我参考网上的~

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<assert.h>

typedef int ElemType;

typedef struct Tree
{

    ElemType Data;
    int height;      //记录树的高度

    struct Tree* l;
    struct Tree* r;
}Tree,*PTree;

void Creat_Node(void** p,size_t size);          //创建一个节点
void Free_Node(void** p);                       //删除一个节点

int Tree_Insert(PTree* t,ElemType data,int (*Comp)(const void* p1,const void* p2));     //创建二叉树(成功插入返回1,否则返回0)
void Tree_Free(PTree* t);                       //释放树

void Tree_Pre_Order_Print(const PTree t,int (*Visit)(const PTree t));             //前序遍历树
void Tree_In_Order_Print(const PTree t,int (*Visit)(const PTree t));              //中序遍历树

int Tree_Get_Max(const PTree t);                      //获取树的最大深度
int Tree_Get_Height(const PTree t);                   //获取树的深度

void Tree_Single_Rotate_With_Right(PTree* t);          //右旋操作
void Tree_Single_Rotate_With_Left(PTree* t);           //左旋操作

void Tree_ByAVL_Single_Rotate_With_Right(PTree* t);          //对于AVL树的右旋操作
void Tree_ByAVL_Single_Rotate_With_Left(PTree* t);           //对于AVL树的左旋操作
void Tree_ByAVL_Double_Rotate_With_Left(PTree* t);           //对于AVL树的双旋操作,先左后右
void Tree_ByAVL_Double_Rotate_With_Right(PTree* t);          //对于AVL树的双旋操作,先右后左

void Tree_Balance(PTree* t,const int l,const ElemType data,int (*Comp)(const void* p1,const void* p2));       //调整平衡
void Tree_ByAVL_Adjust_Right_Height(PTree* t);         //调整右高度
void Tree_ByAVL_Adjust_Left_Height(PTree* t);          //调整左高度

PTree Tree_Find_Node(PTree t,ElemType data,int (*Comp)(const void* p1,const void* p2));         //非递归查找信息

int Tree_Visit(const PTree t);                       //输出函数
int Tree_Comp(const void* p1,const void* p2);                     //比较函数

int main()
{
    PTree t=NULL;
    int i=0;
    int k=0;

    srand((unsigned)time(NULL));

    for (i=0;i<100;++i)
        Tree_Insert(&t,rand()%1000,Tree_Comp);

    puts("中序遍历:");
    Tree_In_Order_Print(t,Tree_Visit);
    puts("");

    puts("二叉树最大深度是:");
    printf("%d\n",Tree_Get_Max(t));

    puts("请输入要查找的数据,EOF结束输入:");
    while (scanf("%d",&k)==1)                 //这里默认查找为int 型,如果要更改数据类型这里输入格式要改改
    {
        PTree pt=NULL;
        if ((pt=Tree_Find_Node(t,k,Tree_Comp))!=NULL)
            puts("找到该数据!");
        else
            puts("没有找到该数据!");
    }
    Tree_Free(&t);

    return 0;
}

void Creat_Node(void** p,size_t size)           //创建一个节点
{
    if (*p!=NULL)
        return ;

    *p=malloc(size);

    assert(*p);

    memset(*p,0,size);
}

void Free_Node(void** p)                       //删除一个节点  
{
    if (*p==NULL)
        return ;

    free(*p);
    *p=NULL;
}

Tree_Insert(PTree* t,ElemType data,int (*Comp)(const void* p1,const void* p2))
{
    int k=0;
    int s=0;
    int l=0;

    if (*t==NULL)
    {
        Creat_Node(t,sizeof(Tree));
        (*t)->Data=data;
        (*t)->height=1;

        return 1;
    }

    k=Comp(&(*t)->Data,&data);

    if (k==1)
        s=Tree_Insert(&(*t)->l,data,Comp);
    else if (k==-1)
        s=Tree_Insert(&(*t)->r,data,Comp);

    if (s&&((*t)->height==Tree_Get_Height((*t)->l)||(*t)->height==Tree_Get_Height((*t)->r)))  //调整二叉树高度
    {
        ++(*t)->height;
        l=Tree_Get_Height((*t)->l)-Tree_Get_Height((*t)->r);
    }

    if (s&&(l==2||l==-2))
        Tree_Balance(t,l,data,Comp);

    return s;
}


int Tree_Get_Max(const PTree t)                     //获取树的最大深度
{
    int l=0;
    int r=0;

    if (t==NULL)
        return 0;

    l=Tree_Get_Max(t->l)+1;
    r=Tree_Get_Max(t->r)+1;

    return l>r?l:r;
}

int Tree_Get_Height(const PTree t)                   //获取树的深度
{
    if (t==NULL)
        return 0;

    return t->height;
}


void Tree_Single_Rotate_With_Right(PTree* t)  //右旋操作
{
    PTree pt=(*t)->l;

    (*t)->l=pt->r;
    pt->r=*t;
    *t=pt;

}

void Tree_Single_Rotate_With_Left(PTree* t) //左旋操作
{
    PTree pt=(*t)->r;

    (*t)->r=pt->l;
    pt->l=*t;
    *t=pt;
}

void Tree_ByAVL_Adjust_Right_Height(PTree* t)         //调整右高度
{

    int lh=Tree_Get_Height((*t)->r->l);
    int rh=Tree_Get_Height((*t)->r->r);

    (*t)->r->height=lh>rh?lh+1:rh+1;
    (*t)->height=Tree_Get_Height((*t)->r)+1;
}

void Tree_ByAVL_Adjust_Left_Height(PTree* t)          //调整左高度
{
    int lh=Tree_Get_Height((*t)->l->l);
    int rh=Tree_Get_Height((*t)->l->r);

    (*t)->l->height=lh>rh?lh+1:rh+1;
    (*t)->height=Tree_Get_Height((*t)->l)+1;
}

void Tree_ByAVL_Single_Rotate_With_Right(PTree* t)          //对于AVL树的右旋操作
{
    Tree_Single_Rotate_With_Right(t);
    Tree_ByAVL_Adjust_Right_Height(t);
}

void Tree_ByAVL_Single_Rotate_With_Left(PTree* t)           //对于AVL树的左旋操作
{
    Tree_Single_Rotate_With_Left(t);
    Tree_ByAVL_Adjust_Left_Height(t);
}
void Tree_ByAVL_Double_Rotate_With_Left(PTree* t)           //对于AVL树的双旋操作,先左后右
{
    Tree_Single_Rotate_With_Left(&(*t)->l);
    Tree_ByAVL_Adjust_Left_Height(&(*t)->l);

    Tree_Single_Rotate_With_Right(t);
    Tree_ByAVL_Adjust_Right_Height(t);
}
void Tree_ByAVL_Double_Rotate_With_Right(PTree* t)          //对于AVL树的双旋操作,先右后左
{
    Tree_Single_Rotate_With_Right(&(*t)->r);
    Tree_ByAVL_Adjust_Right_Height(&(*t)->r);

    Tree_Single_Rotate_With_Left(t);
    Tree_ByAVL_Adjust_Left_Height(t);

}

void Tree_Balance(PTree* t,const int l,const ElemType data,int (*Comp)(const void* p1,const void* p2))        //调整平衡
{ 
    if (l==2&&Comp(&(*t)->l->Data,&data)==1)
        Tree_ByAVL_Single_Rotate_With_Right(t);
    else if (l==2&&Comp(&(*t)->l->Data,&data)==-1)
        Tree_ByAVL_Double_Rotate_With_Left(t);
    else if (Comp(&(*t)->r->Data,&data)==-1)
        Tree_ByAVL_Single_Rotate_With_Left(t);
    else
        Tree_ByAVL_Double_Rotate_With_Right(t);

}

int Tree_IsBalance(const PTree t)                    //判断二叉树平衡情况
{
    return Tree_Get_Max(t);
}

void Tree_Pre_Order_Print(const PTree t,int (*Visit)(const PTree t))             //前序遍历树
{
    if (t==NULL)
        return ;

    Tree_Visit(t);

    Tree_Pre_Order_Print(t->l,Visit);
    Tree_Pre_Order_Print(t->r,Visit);
}

void Tree_In_Order_Print(const PTree t,int (*Visit)(const PTree t))              //中序遍历树
{
    if (t==NULL)
        return ;

    Tree_In_Order_Print(t->l,Visit);

    Tree_Visit(t);

    Tree_In_Order_Print(t->r,Visit);
}

void Tree_Free(PTree* t)                       //释放树
{
    if (*t==NULL)
        return ;

    Tree_Free(&(*t)->l);
    Tree_Free(&(*t)->r);

    Free_Node((void** )t);
}

int Tree_Visit(const PTree t)                       //输出函数
{
    if (t==NULL)
        return 0;

    printf("%-8d",t->Data);
    return 1;
}

PTree Tree_Find_Node(PTree t,ElemType data,int (*Comp)(const void* p1,const void* p2))         //非递归查找信息
{
    int k=0;

    while (t!=NULL&&(k=Comp(&t->Data,&data)))
        if (k==1)
            t=t->l;
        else 
            t=t->r;

    return t;
}

int Tree_Comp(const void* p1,const void* p2)   //比较函数
{
    ElemType a=*(ElemType*)p1;
    ElemType b=*(ElemType*)p2;

    if (a>b)
        return 1;

    if (a<b)
        return -1;
    
    return 0;
}

[此贴子已经被作者于2017-6-12 20:47编辑过]

https://bbs.bccn.net/thread-475229-1-1.html
有兴趣的可以来看看~和这个链接相比~
觉得哪个插入效率和搜索效率谁高一些呢?~~~~~

有时间弄个非递归操作试试~不知道非递归操作效率和递归相比效率如何~~

跌代比递归快是肯定的，但是好难，我到现在都还有个问题没解决。

今天又要上一整天的班，今天彻底看不了代码了。

我也来顶一下~原来我把前序遍历函数里面内容写成中序遍历了~我没啥输出调用没发现~现在已经改正~~

我看了几次你的代码，每次都会看到这个函数，我一直都没发现你在调用中序遍历，而不是在递归前序遍历。

[此贴子已经被作者于2017-6-12 21:08编辑过]

我明白了~原来高度计算正常~对比过两个贴的先序遍历没啥问题~高度偏差是因为一个是叶子节点以-1计算我那个以0来计算~
至于我和你那个前序遍历还是有差别的~原因是旋转的节点不同~再深挖是因为你是从根节点开始查找的~我是从底部回溯的~所以你那个代码节点和我那个会有不同~