程序能运行，但是建的平衡二叉树不正确，不知道什么问题
下面红色的程序部分可能有问题吧，如果用注释掉的那段程序就能显示完整二叉树，但不是平衡二叉树，不用的话，在输入关键字序列的时候都不能形成完整的树，麻烦帮忙改一下，好急的，谢谢！#include <stdio.h>
#include <malloc.h>
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)>(b))
#define LH +1 //左高
#define EH 0 //等高
#define RH -1 //右高
typedef struct BTNode
{
int data;
int bf; //平衡因子
struct BTNode *lchild,*rchild; //左右孩子
}BTNode,*BTree;
/*需要的函数声明*/
void PreOrder(BTree T);
void InOrder(BTree T);
void Right_Balance(BTree &p);
void Left_Balance(BTree &p);
void Left_Root_Balance(BTree &T);
void Right_Root_Balance(BTree &T);
bool InsertAVL(BTree &T,int i,bool &taller);
void PrintBT(BTree T,int m);
void CreatBT(BTree &T);
/*主函数*/
void main()
{
int input,search,m;
bool taller=false;
int shorter=0;
BTree T;
T=(BTree)malloc(sizeof(BTNode));
T=NULL;
while(1)
{
printf("\n请选择需要的二叉树操作:1.创建二叉树 0.退出\n");
scanf("%d",&input);
getchar();
switch(input)
{
case 1:
CreatBT(T);
break;
case 0:
break;
default:
printf("输入错误，请重新选择。");
break;
}
if(input==0)
break;
printf("按任意键和回车继续：");
getchar();
}
}
/*先序遍历二叉树*/
void PreOrder(BTree T)
{ //递归先序遍历二叉树
if(!T)
return;
else
{
printf("%d ",T->data); //根结点
PreOrder(T->lchild); //左子树
PreOrder(T->rchild); //右子树
}
}
/*中序遍历二叉树*/
void InOrder(BTree T)
{
if(T) //如果二叉树非空
{
InOrder(T->lchild);
printf("%d ",T->data); //访问节点
InOrder(T->rchild);
}
}
/*创建二叉树，以输入-1为建立的结束*/
void CreatBT(BTree &T)
{
int m;
int i;
bool taller=false;
T=NULL;
printf("\n数列由以下关键字组成:\n");
printf("\n请输入关键字(以-1结束建立二叉树):");
scanf("%d",&i);
getchar();
while(i!=-1)
{
InsertAVL(T,i,taller);
printf("\n请输入关键字（以-1结束建立二叉树):");
scanf("%d",&i);
getchar();
taller=false;
}
m=0;
printf("您创建的二叉树为：\n");
PrintBT(T,m);
printf("先序遍历为:");
PreOrder(T);
printf("\n中序遍历为:");
InOrder(T);
printf("\n\n");
}
/*插入节点i,若T中存在和i相同关键字的节点，则插入一个数据元素为i的新节点，并返回1，否则返回0*/
bool InsertAVL(BTree &T,int i,bool &taller)
{
if(!T) //插入新节点，树“长高”，置taller为true
{
T=(BTree)malloc(sizeof(BTNode));
T->data=i;
T->lchild=T->rchild=NULL;
T->bf=EH;
taller=true;
}
else
{
if(EQ(i,T->data)) //树中已存在和有相同关键字的节点
{
taller=false;
printf("已存在相同关键字的节点\n");
return 0;
}
if(LT(i,T->data)) //应继续在*T的左子树中进行搜索
{
if(!InsertAVL(T->lchild,i,taller))
return 0;
if(taller)
switch(T->bf){
case LH:
Left_Root_Balance(T);
taller=false;
break;
case EH:
T->bf=LH;
taller=true;
break;
case RH:
T->bf=EH;
taller=false;
break;
}
else{
if(!InsertAVL(T->rchild,i,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:
Right_Root_Balance(T);
taller=false;
break;
}
}
}
/*else
{
if(!InsertAVL(T->rchild,i,taller))
return 0;
}*/
}
return 1;
}
/*按树状打印输出二叉树的元素，m表示节点所在层次*/
void PrintBT(BTree T,int m)
{
if(T)
{
int i;
if(T->rchild)
PrintBT(T->rchild,m+1);
for(i=1;i<=m;i++)
printf(" "); //打印出i个空格以表示出层次
printf("%d\n",T->data);//打印T元素，换行
if(T->lchild)
PrintBT(T->lchild,m+1);
}
else
{
printf("这是一棵空树!\n");
getchar();
}
}
/*对以*p为根的二叉排序珊瑚作右旋处理*/
void Right_Balance(BTree &p)
{
BTree lc;
lc=p->lchild; //lc指向的*p左子树根节点
p->lchild=lc->rchild; //rc的右子树挂接为*p的左子树
lc->rchild=p;
p=lc; //p指向新的节点
}
/*对以*p为根的二叉排序树作左旋处理*/
void Left_Balance(BTree &p)
{
BTree rc;
rc=p->rchild; //指向*p的右子树根节点
p->rchild=rc->lchild; //rc左子树挂接到*p的右子树
rc->lchild=p;
p=rc; //p指向新节点
}
/*对以指针T所指节点为根的二叉树作左平衡旋转处理*/
void Left_Root_Balance(BTree &T)
{
BTree lc,rd;
lc=T->lchild; //指向T的左子树根节点
switch(lc->bf) //检查*T的左子树的平衡度并作相应处理
{
case LH: //新节点插入在*T的左孩子的左子树上，要作单右旋处理
T->bf=lc->bf=EH;
Right_Balance(T);
break;
case RH: //新节点插入在*T的左孩子的右子树上，要作双旋处理
rd=lc->rchild; //rd指向*T的左孩子的右子树根
switch(rd->bf) //修改*T及其左孩子的平衡因子
{
case LH:
T->bf=RH;
lc->bf=EH;
break;
case EH:
T->bf=lc->bf=EH;
break;
case RH:
T->bf=EH;
lc->bf=LH;
break;
}
rd->bf=EH;
Left_Balance(T->lchild); //对*T的左子树作左旋平衡处理
Right_Balance(T); //对*T作右旋处理
}
}
/*对以指针T所指节点为根的二叉树作右平衡旋转处理*/
void Right_Root_Balance(BTree &T)
{
BTree rc,ld;
rc=T->rchild; //指向T的左子树根节点
switch(rc->bf) //检查*T的左子树的平衡度并作相应处理
{
case RH: //新节点插入在*T的左孩子的右子树上，要作单左旋处理
T->bf=rc->bf=EH;
Left_Balance(T);
break;
case LH: //新节点插入在*T的左孩子的右子树上，要作双旋处理
ld=rc->lchild; //ld指向*T的右孩子的左子树根
switch(ld->bf) //修改*T及其右孩子的平衡因子
{
case LH:
T->bf=EH;
rc->bf=RH;
break;
case EH:
T->bf=rc->bf=EH;
break;
case RH:
T->bf=LH;
rc->bf=EH;
break;
}
ld->bf=EH;
Right_Balance(T->rchild); //对*T的右子树作左旋平衡处理
Left_Balance(T); //对*T作左旋处理
}
}
