binary tree.c

利用随机函数产生100个(不大于100且各不相同的)随机整数

 }

 Status DestroyStack(SqStack *S)
 { /* 销毁栈S，S不再存在 */
   free((*S).base);
   (*S).base=NULL;/* 在栈构造之前和销毁之后，base的值为NULL */
   (*S).top=NULL;
   (*S).stacksize=0;
   return OK;
 }

 Status ClearStack(SqStack *S)
 { /* 把S置为空栈 */
   (*S).top=(*S).base;
   return OK;
 }

 Status StackEmpty(SqStack S)
 { /* 若栈S为空栈，则返回TRUE，否则返回FALSE */
   if(S.top==S.base)
     return TRUE;
   else
     return FALSE;
 }

 int StackLength(SqStack S)
 { /* 返回S的元素个数，即栈的长度 */
   return S.top-S.base;/*指针运算*/
 }

 Status GetTop(SqStack S,SElemType *e)
 { /* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */
   if(S.top==S.base) return ERROR;
   *e=*(S.top-1);
   return OK;
 }

 Status Push(SqStack *S,SElemType e)
 { /* 插入元素e为新的栈顶元素 */
   if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */
   {
     (*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));
     if(!(*S).base)
       exit(OVERFLOW); /* 存储分配失败 */
     (*S).top=(*S).base+(*S).stacksize;
     (*S).stacksize+=STACKINCREMENT;
   }
   *((*S).top)++=e;
   return OK;
 }

 Status Pop(SqStack *S,SElemType *e)
 { /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
   if((*S).top==(*S).base)
     return ERROR;
   *e=*--(*S).top;
   return OK;
 }

 Status StackTraverse(SqStack S,Status(*visit)(SElemType))
 { /* 从栈底到栈顶依次对栈中每个元素调用函数visit()。 */
   /* 一旦visit()失败，则操作失败 */
   while(S.top>S.base)
     visit(*S.base++);
   printf("\n");
   return OK;
 }


/*模块五：遍历功能模块*/
void PreOrderTraverse(BSTree T,Status(*Visit)(ElemType e))
/*非递归先序遍历二叉树 */
{
    BSTree p,e ;
    SqStack S ;
    InitStack(&S);
    p=T ;
    while(p||!StackEmpty(S))
    {
        /*遍历左子树*/
        while(p)
        {
            (*Visit)(p->data);
            Push(&S,p);
            p=p->lchild ;
        }
        
        /*通过下一次循环中的内嵌while实现右子树遍历*/
        if(!StackEmpty(S))
        {
            Pop(&S,&e);
            p=e->rchild ;
        }
        
    }
}


void InOrderTraverse(BSTree T,Status(*Visit)(ElemType e))
/*中序遍历二叉树*/
{
    /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数 */
    /* 操作结果: 中序递归遍历T,对每个结点调用函数Visit一次且仅一次 */
    if(T)
    {
        InOrderTraverse(T->lchild,(*Visit));
        /* 先中序遍历左子树 */
        (*Visit)(T->data);
        /* 再访问根结点 */
        InOrderTraverse(T->rchild,(*Visit));
        /* 最后中序遍历右子树 */
    }
}

void PostOrderTraverse(BSTree T,Status(*Visit)(ElemType e))
/*后序遍历二叉树*/
{
    /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数 */
    /* 操作结果: 后序递归遍历T,对每个结点调用函数Visit一次且仅一次 */
    /* T不空 */
    if(T)
    {
        PostOrderTraverse(T->lchild,(*Visit));
        /* 先后序遍历左子树 */
        PostOrderTraverse(T->rchild,(*Visit));
        /* 再后序遍历右子树 */
        (*Visit)(T->data);
        /* 最后访问根结点 */
    }
}

Status PrintElement(ElemType e) 
/*输出元素*/
{
    printf(FORMAT,e);
    return OK ;
}


void menushow()
 {
  puts("\n");
  puts("<1>---Produce 100 random integers.\n ");
  puts("<2>---create a balance binary tree.\n ");
  puts("<3>---Show the content of the tree after proorder.\n");
  puts("<4>---Show the content of the tree after midorder.\n");
  puts("<5>---Show the content of the tree after postorder.\n");
  puts("<6>---Check the times of produce random integer.\n");
  puts("<7>---Exit the program!\n");
  puts("\n\n");
  printf("Select one for running[1...7]:");
 }

void main()
{
    BSTree T=NULL;
    int i,j,data[100],choice,flag,value,rdtime=0;
    /*j为计数器，data数组用于存放从RandomHundred函数随机得来的1－100 */
    /*rdtime用以记录产生随机整数的次数，如果没有产生随机整数就进行建立平衡二叉树会提示错误*/
    Status taller;
    /*长高与否标志，可以不初始化*/
    flag=1;        /*signed the status of the while circle*/
    clrscr();
  while(flag)
  {
   Home: menushow();
   scanf("%d",&choice);

   if(choice>7||choice<1)
    {
     printf("Error!What you select is not exist!Please try again!\n");
     getchar();
     goto Home;
    }

   while(choice!=10)
   {
    switch(choice)
    {
     case 1 :
                 printf("Produce 100 random integer:\n");
                 RandomHundred(data);
                 for(j=0;j<100;++j)printf(FORMAT,data[j]);
                 printf("\n\n");
                 rdtime++;
                 choice=10;
                 break;

     case 2 :
                 if(rdtime==0)
                   {
                   printf("\nIt is error!No element!\n");
                   choice=10;
                   break;
                   }
                 else
                   {
                   for(i=0;i<100;++i)InsertAVL(&T,data[i],&taller);
                   printf("Have created a balance binary tree.\n");
                   printf("\n\n");
                   choice=10;
                   break;
                   }

     case 3 :
                 if(T==NULL) /*若没有建立二叉树提示错误无法进行遍历排序*/
                   {
                   printf("\nIt is error!No element!\n");
                   choice=10;
                   break;
                   }
                 else
                   {
                   printf("The Previous_order of the tree are:\n");
                   PreOrderTraverse(T,PrintElement);
                   printf("\n");
                   choice=10;
                   break;
                   }

     case 4 :    if(T==NULL) /*若没有建立二叉树提示错误无法进行遍历排序*/
                   {
                   printf("\nIt is error!No element!\n");
                   choice=10;
                   break;
                   }
                 else
                   {
                   printf("The Middle_order of the tree are:\n");
                   InOrderTraverse(T,PrintElement);
                   printf("\n");
                   choice=10;
                   break;
                   }

     case 5 :    if(T==NULL) /*若没有建立二叉树提示错误无法进行遍历排序*/
                   {
                   printf("\nIt is error!No element!\n");
                   choice=10;
                   break;
                   }
                 else
                   {
                   printf("The Post_order of the tree are:\n");
                   PostOrderTraverse(T,PrintElement);
                   printf("\n\n");
                   choice=10;
                   break;
                   }

     case 6 :    printf("Randomtimes=%d.\n",rdtime);
                 choice=10;
                 break;

     case 7 :    exit(1);
     }/*switch circle ends*/
   }/*while circle ends */

  }/*the bigger while circle enends*/
}