程序代码：

#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();
        }
    }
}