用二叉链表作存储结构实平衡的二叉排序树
用二叉链表作存储结构实平衡的二叉排序树。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,&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 发表于 2016-11-10 09:48
报什么错？
编译成功，然而运行不能正确的显示平衡二叉树
页:
[1]