求！！建立平衡二叉树的源程序1

来源：百度文库 编辑：神马文学网 时间：2024/04/30 03:42:09
主题：求！！建立平衡二叉树的源程序
作者：lyuandong      发表时间：2005-1-11 20:51:00
楼主   求：
建立平衡二叉树的源程序，我做了，但是不行啊！
求解！！！
#include
#include
#include
#define EQ(a,b) ((a)==(b))
#define LT(a,b)  ((a)<(b))
#define LQ(a,b)  ((a)>(b))
#define LH +1   //left high
#define EH  0   //equal
#define RH -1   //right high
#define true 1
#define false 0
/*****************************define a struct ******************************************/
typedef int KeyType;
typedef struct BSTNode
{
KeyType data;   //data of boot
struct BSTNode *lchild, *rchild;  //pointer to right and left child
int bf;  //balance factor
} BSTNode,*BSTree; //define a node and a pointer who pointer to a struct
/**********************************  right  rotate  *********************************/
void R_Rotate(BSTree p)
{
BSTree lc;
lc=p->lchild;  //lc pointer to *P left child
p->lchild=lc->rchild; //let lc right child to be *p left child
lc->rchild=p;  //the boot become lc right child
p=lc;//p pointer to new boot
}
/***************************************  left rotate  ********************************/
void L_Rotate(BSTree p)
{
BSTree rc;
rc=p->rchild;  //rc pointer to *P right child
p->rchild=rc->lchild; //let rc left child to be *P left child
rc->lchild=p;    //the boot become rc left child
p=rc;   //p pointer to new boot
}
/*****************************  Rotation  Left then  Right  ******************************************/
void LeftBalance(BSTree T)
{
BSTree lc,rd;
lc=T->lchild;   //lc pointe to T left child
switch(lc->bf){
case LH: T->bf=lc->bf=EH;
R_Rotate(T); break;  //left high
case RH: rd=lc->rchild;  //rd pionter to lc right child
switch(rd->bf){//lc right child bf
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;
L_Rotate(T->lchild);
R_Rotate(T);//right high
}
}
/*********************************   Rotation  Right then  Left  ***********************************************/
void RightBalance(BSTree T)
{
BSTree rc,ld;
rc=T->rchild;
switch(rc->bf){
case LH: T->bf=rc->bf=EH;
L_Rotate(T); break;
case RH: ld=rc->lchild;
switch(ld->bf){
case LH: T->bf=RH; rc->bf=EH; break;
case EH: T->bf=rc->bf=EH; break;
case RH: T->bf = EH; rc->bf=LH; break; }
ld->bf=EH;
R_Rotate(T->rchild);
L_Rotate(T);
}
}
/**************************************  insert avl number ***************************************/
int InsertAVL(BSTree T, KeyType e,int taller)
{
if(!T){  printf("T unexistence!\n");
T=(BSTree *)malloc(sizeof(BSTNode));
T->data=e;
T->lchild=T->rchild=NULL;
T->bf=EH;
taller=true;//if unexistence make one
printf("OK!%d\n",T->data);
//return(T);
}
else{
printf("sadvfnklmm,\n");
if(EQ(e,T->data)){taller=false;return 0;}//if equal return 0
if(LT(e,T->data)){//little tham boot
if(!InsertAVL(T->lchild,e,taller)) return 0;
if(taller)
switch(T->bf){
case LH:
LeftBalance(T);taller=false;  printf("lt\n");break;
case EH:
T->bf=LH;taller=true;printf("lt\n");break;
T->bf=EH;taller=false;
printf("lt\n");break;
}//switch
}//if
else{
if(!InsertAVL(T->rchild,e,taller)) return 0;
if(taller)
switch(T->bf){
case LH:
T->bf=EH;taller=false;
printf("lq\n");  break;
case EH:
T->bf=LH;taller=true;
printf("lq\n");  break;
case RH:
RightBalance(T);taller=false; printf("lq\n");  break;
}
}
}
return 1;
}
void inorder(BSTree bt)
{
if (bt!=NULL){
inorder(bt->lchild);
printf("%5d",bt->data);
inorder(bt->rchild);
}
else printf("bt = null!\n");
}
/*********************************  main fun **********************************************/
#include
#include
#include
void RightBalance(BSTree );
void LeftBalance(BSTree );
int InsertAVL(BSTree , KeyType ,int );
void R_Rotate(BSTree );
void L_Rotate(BSTree );
void inorder(BSTree );
void main()
{
//char ch;
KeyType key;
BSTree bt;
int i=0;
printf("\nPlease input data(-1:end)\n");
scanf("%d",&key);
bt=NULL;
do{
InsertAVL(&bt,key ,i ) ;
// printf("s.data=%d",s->data);
printf("\nPlease input data(-1:end)\n");
scanf("%d",&key);
printf("t.data%d\n",bt->data);
}while(key!=-1);
printf("\nCreate is complete\n");
printf("t.data%d\n",bt->data);
inorder(bt);
}
主题：求！！建立平衡二叉树的源程序
作者：lyuandong      发表时间：2005-1-11 20:51:00
楼主   求：
建立平衡二叉树的源程序，我做了，但是不行啊！
求解！！！
#include
#include
#include
#define EQ(a,b) ((a)==(b))
#define LT(a,b)  ((a)<(b))
#define LQ(a,b)  ((a)>(b))
#define LH +1   //left high
#define EH  0   //equal
#define RH -1   //right high
#define true 1
#define false 0
/*****************************define a struct ******************************************/
typedef int KeyType;
typedef struct BSTNode
{
KeyType data;   //data of boot
struct BSTNode *lchild, *rchild;  //pointer to right and left child
int bf;  //balance factor
} BSTNode,*BSTree; //define a node and a pointer who pointer to a struct
/**********************************  right  rotate  *********************************/
void R_Rotate(BSTree p)
{
BSTree lc;
lc=p->lchild;  //lc pointer to *P left child
p->lchild=lc->rchild; //let lc right child to be *p left child
lc->rchild=p;  //the boot become lc right child
p=lc;//p pointer to new boot
}
/***************************************  left rotate  ********************************/
void L_Rotate(BSTree p)
{
BSTree rc;
rc=p->rchild;  //rc pointer to *P right child
p->rchild=rc->lchild; //let rc left child to be *P left child
rc->lchild=p;    //the boot become rc left child
p=rc;   //p pointer to new boot
}
/*****************************  Rotation  Left then  Right  ******************************************/
void LeftBalance(BSTree T)
{
BSTree lc,rd;
lc=T->lchild;   //lc pointe to T left child
switch(lc->bf){
case LH: T->bf=lc->bf=EH;
R_Rotate(T); break;  //left high
case RH: rd=lc->rchild;  //rd pionter to lc right child
switch(rd->bf){//lc right child bf
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;
L_Rotate(T->lchild);
R_Rotate(T);//right high
}
}
/*********************************   Rotation  Right then  Left  ***********************************************/
void RightBalance(BSTree T)
{
BSTree rc,ld;
rc=T->rchild;
switch(rc->bf){
case LH: T->bf=rc->bf=EH;
L_Rotate(T); break;
case RH: ld=rc->lchild;
switch(ld->bf){
case LH: T->bf=RH; rc->bf=EH; break;
case EH: T->bf=rc->bf=EH; break;
case RH: T->bf = EH; rc->bf=LH; break; }
ld->bf=EH;
R_Rotate(T->rchild);
L_Rotate(T);
}
}
/**************************************  insert avl number ***************************************/
int InsertAVL(BSTree T, KeyType e,int taller)
{
if(!T){  printf("T unexistence!\n");
T=(BSTree *)malloc(sizeof(BSTNode));
T->data=e;
T->lchild=T->rchild=NULL;
T->bf=EH;
taller=true;//if unexistence make one
printf("OK!%d\n",T->data);
//return(T);
}
else{
printf("sadvfnklmm,\n");
if(EQ(e,T->data)){taller=false;return 0;}//if equal return 0
if(LT(e,T->data)){//little tham boot
if(!InsertAVL(T->lchild,e,taller)) return 0;
if(taller)
switch(T->bf){
case LH:
LeftBalance(T);taller=false;  printf("lt\n");break;
case EH:
T->bf=LH;taller=true;printf("lt\n");break;
T->bf=EH;taller=false;
printf("lt\n");break;
}//switch
}//if
else{
if(!InsertAVL(T->rchild,e,taller)) return 0;
if(taller)
switch(T->bf){
case LH:
T->bf=EH;taller=false;
printf("lq\n");  break;
case EH:
T->bf=LH;taller=true;
printf("lq\n");  break;
case RH:
RightBalance(T);taller=false; printf("lq\n");  break;
}
}
}
return 1;
}
void inorder(BSTree bt)
{
if (bt!=NULL){
inorder(bt->lchild);
printf("%5d",bt->data);
inorder(bt->rchild);
}
else printf("bt = null!\n");
}
/*********************************  main fun **********************************************/
#include
#include
#include
void RightBalance(BSTree );
void LeftBalance(BSTree );
int InsertAVL(BSTree , KeyType ,int );
void R_Rotate(BSTree );
void L_Rotate(BSTree );
void inorder(BSTree );
void main()
{
//char ch;
KeyType key;
BSTree bt;
int i=0;
printf("\nPlease input data(-1:end)\n");
scanf("%d",&key);
bt=NULL;
do{
InsertAVL(&bt,key ,i ) ;
// printf("s.data=%d",s->data);
printf("\nPlease input data(-1:end)\n");
scanf("%d",&key);
printf("t.data%d\n",bt->data);
}while(key!=-1);
printf("\nCreate is complete\n");
printf("t.data%d\n",bt->data);
inorder(bt);
}
求！！建立平衡二叉树的源程序1 编程论坛-平衡二叉树[原创] 编程论坛-关于平衡二叉树 编程论坛-平衡二叉树[原创] 二叉树的遍历 二叉树及其遍历 第五章 二叉树 二叉树及其遍历 汇编实现简单二叉树 第六章 树和二叉树 第二十四课 遍历二叉树 金鸡独立－最简单有效的平衡健身法 (求医不如求己 - 中里巴人) 第二十七课 实验六 二叉树实验 在潜规则与高尚之间求平衡？ 30 个最好的随身携带的 开源程序 软件 整型int和字符数组byte相互转换的源程序 重求：建立社会主义人民当家做主思想体系 管理是平衡的艺术1 平衡的智慧 平衡的艺术 必要的平衡 平衡的艺术 教育的平衡性 教育的平衡性