程序代码.txt

程序中的数据采用“树形结构”作为其数据结构。具体的

#include<stdio.h>
typedef struct Tnode
 {
   int   data; /*输入的数据*/
   struct Tnode *lchild,*rchild; /*结点的左右指针，分别指向结点的左右孩子*/
 }*node,BSTnode;
searchBST(node t,int key,node f,node *p) /*查找函数*/
{
    if(!t)  {*p=f;return (0);} /*查找不成功*/
    else    if(key==t->data)
    {
     *p=t;return (1);
    } /*查找成功*/
    else    if(key<t->data)
    searchBST(t->lchild,key,t,p); /*在左子树中继续查找*/
    else
    searchBST(t->rchild,key,t,p);/*在右子树中继续查找*/
}
insertBST(node *t,int key)  /*插入函数*/
{
    node p=NULL,s=NULL;
    if(!searchBST(*t,key,NULL,&p)) /*查找不成功*/
    {
       s=(node)malloc(sizeof(BSTnode));
       s->data=key;
       s->lchild=s->rchild=NULL;
       if(!p)  *t=s; /*被插结点*s为新的根结点*/
       else    if(key<p->data)   p->lchild=s;/*被插结点*s为左孩子*/
       else    p->rchild=s;/*被插结点*s为右孩子*/
       return (1);
    }
   else  return (0);/*树中已有关键字相同的结点，不再插入*/
}
inorderTraverse(node *t)  /*中序遍历函数*/
{
    if(*t)
    {
       if(inorderTraverse(&(*t)->lchild))  /*中序遍历根的左子树*/
    {
       printf("%d  ",(*t)->data);/*输出根结点*/
       if(inorderTraverse(&(*t)->rchild));/*中序遍历根的右子树*/
    }
  }
      else    return(1);
}
calculateASL(node *t,int *s,int *j,int i)/*计算平均查找长度*/
{
   if(*t)
   {  i++;   /*i记录当前结点的在当前树中的深度*/
      *s=*s+i;   /*s记录已遍历过的点的深度之和*/
     if(calculateASL(&(*t)->lchild,s,j,i)) /*计算左子树的ASL*/
   {
           (*j)++;   /*j记录树中结点的数目*/
           if(calculateASL(&(*t)->rchild,s,j,i)) /*计算右子树的ASL*/
           {i--; return(1);}
           }
    }
  else    return(1);
}
node Delete(node t,int  key) /*删除函数*/
{
  node    p=t,q=NULL,s,f;
  while(p!=NULL)   /*查找要删除的点*/
    {
        if(p->data==key)  break;
        q=p;
        if(p->data>key)
        p=p->lchild;
        else
        p=p->rchild;
    }
    if(p==NULL)
    return  t; /*查找失败*/
    if(p->lchild==NULL) /*p指向当前要删除的结点*/
    {
        if(q==NULL)
        t=p->rchild;  /*q指向要删结点的父母*/
        else    if(q->lchild==p)
        q->lchild=p->rchild; /*p为q的左孩子*/
        else
        q->rchild=p->rchild;/*p为q的右孩子*/
        free(p);
    }
   else{ /*p的左孩子不为空*/
        f=p;
        s=p->lchild;
        while(s->rchild)/*左拐后向右走到底*/
        {
          f=s;
          s=s->rchild;
        }
        if(f==p)
        f->lchild=s->lchild; /*重接f的左子树*/
        else
        f->rchild=s->lchild; /*重接f的右子树*/
        p->data=s->data;
        free (s);
        }
    return  t;
}
int balanceBST(node t,int *i) /*判断是否为平衡二叉树的函数*/
{
    int   dep1,dep2;
    if(!t)  return(0);
    else
    {
        dep1=balanceBST(t->lchild,i);
        dep2=balanceBST(t->rchild,i);
    }
    if((dep1-dep2)>1||(dep1-dep2)<-1)
    *i=dep1-dep2;/*用i值记录是否存在不平衡现象*/
    if(dep1>dep2) return(dep1+1);
    else   return(dep2+1);
}
void main()
{
    node  T=NULL;
    int   num;
    int   s=0,j=0,i=0;
    int   ch=0;
    node  p=NULL;
    printf("please input a list of numbers end with zero:");
    do
    {
        scanf("%d",&num);
        if(!num)
        printf("you have finished your input!\n");
        else    insertBST(&T,num);
    }while(num);
    printf("\\n\\n---the menu of the opperation---\\n\\n\n"); /*主程序菜单*/
    printf("0:  exit\n");
    printf("1:  inorder travel the tree\n");
    printf("2:  the average search length for the tree\n");
    printf("3:  delete");
    printf("4:  judge the balance\n");
    while(ch==ch)
    {
        printf("choose the opperation to continue:");
        scanf("%d",&ch);
        switch(ch){
          case 0:   exit(0);    /*0－－退出*/
            case 1:   printf("The result of the inorder traverse is:\n");
            inorderTraverse(&T);/*1－－中序遍历*/
            break;
            case 2:   s=0;j=0;i=0;
            calculateASL(&T,&s,&j,i);/*2－－计算平均查找长度*/
                      printf("   ASL=%d/%d",s,j);
                      break;
            case 3:   printf("Please input the number you want to delete:");
                      scanf("%d",&num);/*3－－删除某个结点*/
                      if(searchBST(T,num,NULL,&p))
                      {
                        T=Delete(T,num);
                     printf("You have delete the number successfully!\n");
                        inorderTraverse(&T);
                      }
                   else  printf("   No node %d you want to delete!",num);
                      break;
            case 4:   i=0;
 balanceBST(T,&i);/*判断是否为平衡二插树*/
 if(i==0)   
printf("OK!The tree is a balanced tree!");
 else
 printf("   NO!");
 break; 
default: printf("Your input is wrong!please input again!\n");
       break;   /*输入无效字符*/
        }
        printf("\n");
    }
}