用二叉链表作存储结构实平衡的二叉排序树

下午茶的芬芳

用二叉链表作存储结构实平衡的二叉排序树。
      1)用数列L，生成平衡的二叉排序树BT：当插入新元素之后，发现
当前的二叉排序树BT不是平衡的二叉排序树，则立即将它转换成新的平
衡的二叉排序树BT；
      2)计算平衡的二叉排序树BT的平均查找长度，输出结果。



真的不知道为什么代码编译不出来
求大神检查，真的十分感谢

#include<stdio.h>
#include<stdlib.h>
#define LH 1
#define EH 0
#define RH -1
typedef struct BSTNode
{
        int key;
        int BF;
        struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

BSTree ll_rotate(BSTree *p)//左左旋转
{
        BSTree *s,*g;
        *s=(*p)->lchild;
        *g=(*s)->lchild;
        (*p)->lchild=(*s)->rchild;
        (*s)->rchild=(*p);
        (*p)->BF=EH;
        (*s)->BF=EH;
        (*p)=*s;
        return (*p);
}

BSTree lr_rotate(BSTree *p)//左右旋转
{
        BSTree *s,*g;
        (*s)=(*p)->lchild;
        (*g)=(*s)->lchild;
        (*s)->rchild=(*g)->lchild;
        (*p)->lchild=(*g)->rchild;
        (*g)->lchild=(*s);
        (*g)->rchild=(*p);
        switch((*g)->BF)
        {
                case LH:
                        (*p)->BF=RH;
                        (*s)->BF=EH;
                        (*g)->BF=EH;
                case EH:
                        (*p)->BF=EH;
                        (*s)->BF=EH;
                        (*g)->BF=EH;
                case RH:
                        (*p)->BF=EH;
                        (*s)->BF=LH;
                        (*g)->BF=EH;
        }
        (*p)=(*g);
        return (*p);
}

BSTree rl_rotate(BSTree *p)//右左旋转
{
        BSTree *s,*g;
        (*s)=(*p)->rchild;
        (*g)=(*p)->lchild;
        (*p)->rchild=(*g)->lchild;
        (*s)->lchild=(*g)->rchild;
        (*s)->lchild=(*p);
        (*g)->rchild=(*s);
        switch((*g)->BF)
        {
                case LH:
                        (*p)->BF=EH;
                        (*s)->BF=RH;
                        (*g)->BF=EH;
                case EH:
                        (*p)->BF=EH;
                        (*s)->BF=EH;
                        (*g)->BF=EH;
                case RH:
                        (*p)->BF=LH;
                        (*s)->BF=EH;
                        (*g)->BF=EH;
        }
        (*p)=(*g);
        return (*p);
}

BSTree rr_rotate(BSTree *p)//右右旋转
{
        BSTree *s,*g;
        (*s)=(*p)->rchild;
        (*g)=(*s)->rchild;
        (*p)->rchild=(*s)->lchild;
        (*s)->lchild=(*p);
        (*p)->BF=EH;
        (*s)->BF=EH;
        (*p)=(*s);
        return (*p);
}
BSTree leftbalance(BSTree *p)//左平衡
{
        BSTree *s;
        (*s)=(*p)->lchild;
        switch((*s)->BF)
        {
                case LH:
                        ll_rotate(p);
                        break;
                case RH:
                        lr_rotate(p);
                        break;
        }
}

BSTree rightbalance(BSTree *p)//右平衡
{
        BSTree *s;
        (*s)=(*p)->rchild;
        switch((*s)->BF)
        {
                case LH:
                        rl_rotate(p);
                        break;
                case RH:
                        rr_rotate(p);
                        break;
        }
}

int compare(int x,int y)
{
        if(x==y)        return 0;
        else
                if(x<y)        return -1;
                else
                        return 1;
}

int InsertAVL(BSTree *T,char e,bool *taller)//插入结点后，数长高，则×taller置为true 
{
        int tmp;
        if(!(*T))
        {
                *T=(BSTree)malloc(sizeof(BSTNode));
                (*T)->key=e;
                (*T)->lchild=NULL;
                (*T)->rchild=NULL;
                *taller=true;
        }
        else
        {
                tmp=compare(e,(*T)->key);
                switch(tmp)
                {
                        case 0:
                                *taller=false;
                                return 0;
                                break;
                        case -1:
                                if(!InsertAVL(&((*T)->lchild),e,taller))
                                        return 0;
                                if(*taller)
                                {
                                        switch((*T)->BF)
                                        {
                                                case LH:
                                                        *T=leftbalance(T);
                                                        *taller=false;
                                                        break;
                                                case EH:
                                                        (*T)->BF=LH;
                                                        *taller=true;
                                                        break;
                                                case RH:
                                                        (*T)->BF=EH;
                                                        *taller=false;
                                                        break;
                                        }
                                }
                                break; 
                        case 1:
                                if(!InsertAVL(&((*T)->rchild),e,taller))
                                        return 0;
                                if(*taller)
                                {
                                        switch((*T)->BF)
                                        {
                                                case LH:
                                                        (*T)->BF=EH;
                                                        *taller=false;
                                                        break;
                                                case EH:
                                                        (*T)->BF=RH;
                                                        *taller=true;
                                                        break;
                                                case RH:
                                                        *T=rightbalance(T);
                                                        *taller=false;
                                                        break;
                                        }
                                }
                                break; 
                                
                }
        }
        return 1;
} 
int CalAveLength(BSTNode *rt,int *s,int *j,int i)
{
        if(rt)
        {
                i++;
                *s=*s+i;
                if(CalAveLength(rt->rchild,s,j,i))
                {
                        i--;
                        return i;
                }
        }
        else
                return 1;
}
bool Find(BSTree T,int key)
{
        if(!T)
                return false;
        else if(T->key==key)
                return true;
        else if(T->key<key)
                return Find(T->rchild,key);
        else
                return Find(T->lchild,key);
}
void Output(BSTree T)
{
        if(T)
        {
                 printf("%d",T->key);
                 if(T->lchild||T->rchild)
                {
                        printf("(");
                           Output(T->lchild);
                           printf(",");
                           Output(T->rchild);
                           printf(")");
                  }
         }
}
int main(int argc,char *argv[])
{
        int i;
        int A[]={3,2,1,4,5,6,7,10,9,8};

        //int A[]={3,2,1};
        BSTree T=NULL;
        bool taller;
        for(i=0;i<sizeof(A)/sizeof(int);i++)
                InsertAVL(&T,A[i],&taller);
        Output(T);
        printf("\n");
        if(Find(T,6))
                printf("6 is find in the AVL tree!\n");
        else 
                printf("6 is not find in the AVL tree!\n");
        int len,j=0,s=0;
        len=CalAveLength(T,&s,&j,i);
        printf("二叉排序树查找成功的平均查找长度为：%d",len);
        return 0;
}

robinmu

报什么错？

下午茶的芬芳

robinmu 发表于 2016-11-10 09:48
报什么错？

编译成功，然而运行不能正确的显示平衡二叉树