以下算法在TC上编译通过：平衡二叉排序树的建立.增加和删除操作，一元多项式的相加和相乘，算法运行界面设计。大家看看，提提意见啊！
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
# define LH 1
# define EH 0
# define RH -1
# define TRUE 1
# define FALSE 0
# define MAX 20
int taller=0; /*taller反映T长高与否*/
int shorter=0; /*shorter反映T变矮与否*/
typedef struct BSTNode
{ /*二叉排序树的类型定义*/
int data;
int bf; /*结点的平衡因子*/
struct BSTNode * lchild, * rchild;
}BSTNode, *BSTree;
BSTree R_Rotate(BSTree p)
{ /*对以p为根的二叉排序树作右旋处理，处理之p指向新的树根结点*/
/*即旋转处理之前的左子树根结点*/
BSTNode *lc;
lc=p->lchild;
p->lchild=lc->rchild;
lc->rchild=p;p=lc;
return p;
} /*R_Rotate*/
BSTree L_Rotate(BSTree p)
{ /*对以p为根的二叉排序树作左旋处理，处理之p指向新的树根结点*/
/*即旋转处理之前的右子树根结点*/
BSTNode *rc;
rc=p->rchild;
p->rchild=rc->lchild;
rc->lchild=p;p=rc;
return p;
}/*L_Rotate*/
BSTree LeftBalance(BSTree T)
{ /*对以指针T所指结点为根的二叉树作左平衡旋转处理，本算法结束时*/
/*指针T指向新的根结点*/
BSTNode *lc,*rd;
lc=T->lchild;
switch(lc->bf)
{
case LH: T->bf=lc->bf=EH;
T=R_Rotate(T);
break;
case RH: rd=lc->rchild;
switch(rd->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;
T->lchild=L_Rotate(T->lchild);
T=R_Rotate(T);
}
return T;
}
BSTree RightBalance(BSTree T)
{ /*对以指针T所指结点为根的二叉树作右平衡旋转处理，本算法结束时*/
/*指针T指向新的根结点*/
BSTree rc,ld;
rc=T->rchild;
switch(rc->bf)
{
case RH:T->bf=rc->bf=EH;
T=L_Rotate(T);
break;
case LH:ld=rc->lchild;
switch(ld->bf)
{
case LH:T->bf=LH;
rc->bf=EH;
break;
case EH:T->bf=rc->bf=EH;
break;
case RH:T->bf=EH;
rc->bf=RH;
break;
}
ld->bf=EH;
T->rchild=R_Rotate(T->rchild);
T=L_Rotate(T);
}
return T;
}
BSTree InsertAVL (BSTree T, int e)
{ /*若在平衡的二叉排序树T中不存在和e有相同关键字的结点,则插入一个
/*数据元素为e的新结点,并返回插入后所建成的平衡二叉排序树,否则返回
/*NULL.若因插入而使二叉数失去平衡,则作平衡旋转处理,布尔变量taller
/*反映T长高与否*/
BSTree p;
if(!T)
{
T=(BSTree)malloc(sizeof(BSTNode));
T->data=e;
T->lchild=T->rchild=NULL;
T->bf=EH;
taller=TRUE;
}
else
{
if(e==T->data)
{
taller=FALSE;
return NULL;
}
if(e < T->data)
{
p=InsertAVL(T->lchild,e);
if(p)
{
T->lchild=p;
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;
}
}
}
else
{
p=InsertAVL(T->rchild,e);
if (p)
{
T->rchild=p;
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;
}
}
}
}
}
return T;
}
BSTree midorder(BSTree T)
{ /*树的中序遍历的递归算法*/
if(T!=NULL)
{
midorder(T->lchild);
printf("%d ",T->data);
midorder(T->rchild);
}
}
BSTree RightBalance1(BSTree p)
{ /*删除结点时对以指针T所指结点为根的二叉树作右平衡旋转处理，本算法结束时*/
/*指针T指向新的根结点*/
BSTree p1,p2;
if(p->bf==-1)
{
p->bf=0;
shorter=1;
}
else if(p->bf==0)
{
p->bf=1;
shorter=0;
}
else
{
p1=p->lchild;
if(p1->bf==0)
{
p->lchild = p1->rchild;
p1->rchild = p;
p1->bf=-1;
p->bf=1;
p=p1;
shorter=0;
}
else if(p1->bf==1)
{
p->lchild=p1->rchild;
p1->rchild=p;
p1->bf=p->bf=0;
p=p1;
shorter=1;
}
else
{
p2=p1->rchild;
p1->rchild = p2->lchild;
p2->lchild = p1;
p->lchild = p2->rchild;
p2->rchild = p;
if(p2->bf == 0)
{
p->bf = 0;
p1->bf = 0;
}
else if(p2->bf == 1)
{
p->bf = -1;
p1->bf = 0;
}
else
{
p->bf=0;
p1->bf=1;
}
p2->bf=0;
p=p2;
shorter=1;
}
}
return p;
}
BSTree LeftBalance1(BSTree p)
{ /*删除结点时对以指针T所指结点为根的二叉树作左平衡旋转处理，本算法结束时*/
/*指针T指向新的根结点*/
BSTree p1,p2;
if(p->bf==1)
{
p->bf=0;
shorter=1;
}
else if(p->bf==0)
{
p->bf=-1;
shorter=0;
}
else
{
p1=p->rchild;
if(p1->bf==0)
{
p->rchild = p1->lchild;
p1->lchild = p;
p1->bf = 1;
p->bf = -1;
p = p1;
shorter = 0;
}
else if(p1->bf==-1)
{
p->rchild=p1->lchild;
p1->lchild=p;
p1->bf=p->bf=0;
p=p1;
shorter=1;
}
else
{
p2=p1->lchild;
p1->lchild=p2->rchild;
p2->rchild=p1;
p->rchild=p2->lchild;
p2->lchild=p;
if(p2->bf==0)
{
p->bf=0;
p1->bf=0;
}
else if(p2->bf==-1)
{
p->bf=1;
p1->bf=0;
}
else
{
p->bf=0;
p1->bf=-1;
}
p2->bf=0;
p=p2;
shorter=1;
}
}
return p;
}
BSTree Delete(BSTree q, BSTree r)
{ /*对结点进行删除处理*/
if(r->rchild==NULL)
{
q->data=r->data;
q=r;
r=r->lchild;
free(q);
shorter=1;
}
else
{
r->rchild=Delete(q,r->rchild);
if(shorter==1)
r=RightBalance1(r);
}
return r;
}
BSTree DeleteAVL(BSTree p, int e)
{ /*找到要删除的结点,并调用删除函数对其进行删除*/
BSTree q;
if(p==NULL)
return NULL;
else if(e < p->data)
{
p->lchild = DeleteAVL(p->lchild,e);
if(shorter==1)
p=LeftBalance1(p);
return p;
}
else if(e > p->data)
{
p->rchild=DeleteAVL(p->rchild,e);
if(shorter==1)
p=RightBalance1(p);
return p;
}
else
{
q=p;
if(p->rchild==NULL)
{
p=p->lchild;
free(q);
shorter=1;
}
else if(p->lchild==NULL)
{
p=p->rchild;
free(q);
shorter=1;
}
else
{
q->lchild=Delete(q,q->lchild);
if(shorter==1)
q=LeftBalance1(q);
p=q;
}
}
return p;
}
/*以上是平衡二叉排序树的建立.增加和删除的函数建立,具体执行在主函数的case 1*/
/*以下是一元多项式的建立输出和相加的函数建立,具体执行在主函数的case 2*/
typedef struct LNode
{ /*多项式的存储结构定义*/
int coef;
int expn;
struct LNode *next;
}LNode,*linklist;
linklist creat()
{ /*一元多项式以链表存储形式的建立*/
linklist head,s,p,pre;
int coef;
int expn;
head=(linklist)malloc(sizeof(LNode));
head->next=NULL;
printf("put in coef and expn:");
scanf("%d %d",&coef,&expn);
while (coef!=0)
{
s=(linklist)malloc(sizeof(LNode));
s->coef=coef;
s->expn=expn;
s->next=NULL;
pre=head;
p=head->next;
while (p&&p->expn>s->expn)
{
pre=p;
p=p->next;
}
s->next=p;
pre->next=s;
printf("put in coef and expn:");
scanf("%d %d",&coef,&expn);
printf("\n");
}
return head;
}
void print(linklist head)
{ /*将建立好的一元多项式输出的函数建立*/
linklist p;
p=head->next;
while (p)
{ if(p->next==NULL)
printf("%dX^%d",p->coef,p->expn);
else
printf("%dX^%d+",p->coef,p->expn);
p=p->next;
}
}
linklist add(linklist La,linklist Lb)
{ /*两个一元多项式的加法运算*/
linklist Lc,pa,pb,pt,pc;
int temp;
Lc=(linklist)malloc(sizeof(LNode));
Lc->next=NULL;
pa=La->next;
pb=Lb->next;
pc=Lc;
while (pa&&pb)
{
if (pa->expn==pb->expn)
{
pt=(linklist)malloc(sizeof(LNode));
pt->expn=pa->expn;
pt->coef=pa->coef+pb->coef;
pt->next=NULL;
pa=pa->next;
pb=pb->next;
}
else if (pa->expn>pb->expn)
{
pt=(linklist)malloc(sizeof(LNode));
pt->expn=pa->expn;
pt->coef=pa->coef;
pt->next=NULL;
pa=pa->next;
}
else
{
pt=(linklist)malloc(sizeof(LNode));
pt->expn=pb->expn;
pt->coef=pb->coef;
pt->next=NULL;
pb=pb->next;
}
pc->next=pt;
pc=pt;
}
if (pa)
pc->next=pa;
else
pc->next=pb;
return Lc;
}
linklist mul(linklist La,linklist Lb)
{ /*两一元多项式的乘法运算*/
linklist Lc,pa,pb,Temp,pt,pl;
Lc=(linklist)malloc(sizeof(LNode));
Lc->next=NULL;
pa=La->next;
while (pa)
{
pb=Lb->next;
Temp=(linklist)malloc(sizeof(LNode));
Temp->next=NULL;
pl=Temp;
while (pb)
{
pt=(linklist)malloc(sizeof(LNode));
pt->coef=pa->coef*pb->coef;
pt->expn=pa->expn+pb->expn;
pt->next=NULL;
pl->next=pt;
pl=pt;
pb=pb->next;
}
Lc=add(Lc,Temp);
pa=pa->next;
}
return Lc;
}
int Window()
{ /*算法运行窗口的建立*/
int i;
textmode(C40);
textbackground(BLUE);
textcolor(YELLOW);
clrscr();
gotoxy(16,4);
printf("M E N U");
gotoxy(5,5);
printf("* * * * * * * * * * * * * * * *");
for (i=0; i<15; i++)
{
gotoxy(5,i+5);
putchar('*');
gotoxy(35,i+5);
putchar('*');
}
gotoxy(5,20);
printf("* * * * * * * * * * * * * * * *");
gotoxy(7,8);
printf("0. Break");
gotoxy(7,12);
printf("1. AVL Tree");
gotoxy(7,16);
printf("2. Unitary Multionmial");
gotoxy(5,22);
printf("Please input your choose:");
scanf("%d",&i);
return i;
}
main()
{
int x,i,n,a[MAX];
char c;
BSTree T;
linklist p, q, r;
x=Window();
while(x>=0)
{
if(x==0)
break;
else if(x==1)
{
clrscr(); /*平衡二叉排序树的建立,增加和删除算法*/
T=NULL;
printf("Input the Number of Node:\n");
scanf("%d",&n);
printf("Input the BSTree Data:\n");
for (i=0; i < n; i++)
{
scanf("%d",&a[i]);
}
for (i=0; i < n; i++)
{
T=InsertAVL (T,a[i]);
}
midorder(T);
printf("\n");
printf("Input the num to insert, input \"0\" to finish!\n");
scanf("%d",&n);
while (n!=0)
{
T=InsertAVL (T, n);
scanf("%d",&n);
}
printf("\n");
midorder(T);
printf("\n");
printf("Input the num to delete, input \"0\" to finish!\n");
scanf("%d",&n);
while (n != 0)
{
T=DeleteAVL (T, n);
scanf("%d",&n);
}
midorder(T);;
scanf("%c",&c);
c=getch();
if(c=='#')
{
x=0;
break;
}
else
x=Window();
}
if(x==2)
{ /*一元多项式建立.相加和相乘并对其结果输出的算法*/
clrscr();
p=creat();
q=creat();
print(p);
printf("\n");
print(q);
r=add(p,q);
printf("\n");
print(r);
r=mul(p,q);
printf("\n");
print(r);
scanf("%c",&c);
c=getch();
if(c=='#')
{
x=0;
break;
}
else
x=Window();
}
}
}
