zz8255 发布留言 2005-1-19 10:49
有关平衡二叉树的问题！谢谢了！
我根据严蔚敏遍的《数据结构》里有关平衡二叉树的算法写了程序。
/*插入节点的算法*/
int InsertAVL(BSTree T,int e,int *taller)
{
if(T==NULL)
{
T=(BSTree)malloc(sizeof(BSTNode));
T->data=e;
T->lchild=T->rchild=NULL;
T->bf=EH;
*taller=TRUE;
}
else
{
if(e<T->data)
{
if(!InsertAVL(T->lchild,e,taller))
return 0;
if(taller)
{
switch(T->bf)
{
case LH:
LeftBalance(T);*taller=FALSE;break;
case EH:
T->bf=LH;*taller=TRUE;break;
case RH:
T->bf=EH;*taller=FALSE;break;
}
}
}
else
{
if(!InsertAVL(T->lchild,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:
RightBalance(T);*taller=FALSE;break;
}
}
}
}
return 1;
}
树的结构：
struct Tree
{
int data;
int bf;
struct Tree *lchild,*rchild;
};
typedef struct Tree BSTNode;
typedef BSTNode *BSTree;
相关宏：
#define LH +1
#define EH 0
#define RH -1
#define TRUE 1
#define FALSE 0
我现在的主函数
void main()
{
BSTree root=NULL;/*根节点*/
int nodelist[5]={4,3,5,2,6};
int taller,i=0;
while(i<5)
{
if(InsertAVL(root,nodelist;
int data, ret;
for(ret = 0; ret < 11; ret++)
insert_node( ret);
travesal_mid();
while(1)
{
/*
printf("\n\n\nenter data =");
scanf("%s", str);
if(strncmp(str, "ok", 2) == 0)
break;
ret = sscanf(str, "%d", &data);
if(ret == 1)
{
travesal_mid();
ret = insert_node( data);
if(ret != -1)
printf("\n insert data=%d successful", data);
travesal_mid();
}
*/
printf("\n\n\ndel data =");
scanf("%s", str);
if(strncmp(str, "ok", 2) == 0)
break;
ret = sscanf(str, "%d", &data);
if(ret == 1)
{
travesal_mid();
ret = del_node( data);
if(ret != -1)
printf("\n del data=%d successful", data);
travesal_mid();
}
}
free_tab();
}
int main(int argc , char **argv)
{
input_data();
return 0;
}
页: [1]
