sy6_1.c

数据结构实验与学习指导

/*二叉树的建立、递归遍历sy6_1.c*/
#include <stdio.h>
#include <alloc.h>
#define MAXSIZE 20
typedef struct btnode
{
   char cdata;
   struct btnode *lchild,*rchild;
}BTNode;
BTNode *Create_BiTree()/*二叉树的建立*/
{/*用辅助数组建立二叉树*/
   int i,j;
   char ch;
   BTNode *s,*t,*p[MAXSIZE];
   printf("输入顶点编号及信息，输入0和#结束:i,ch");
   scanf("%d,%c",&i,&ch);
   while(i!=0 &&ch!='#')/*建立二叉树的存储结构*/
      {s=(BTNode *)malloc(sizeof(BTNode));
       s->cdata=ch;
       s->lchild=s->rchild=NULL;
       p[i]=s;
       if(i==1) t=s;/*判断输入结点是根结点、左孩子还是右孩子*/
       else
         {j=i/2;
          if(i%2==0) p[j]->lchild=s;
          else p[j]->rchild=s;
         }
       printf("输入顶点编号及信息，输入0和#结束:i,ch");
       scanf("%d,%c",&i,&ch);
   }
   return t;
}/* Create_BiTree1*/
void  Preorder(BTNode *bt)
{/*前序递归遍历*/
    if(bt)
    {
          printf("%c",bt->cdata);
          Preorder(bt->lchild);
        Preorder(bt->rchild);
    }
}/* Preorder*/
void  Inorder(BTNode *bt)
{/*中序递归遍历*/
    if(bt)
    {
       Inorder(bt->lchild);
        printf("%c",bt->cdata);
       Inorder(bt->rchild);
    }
}/* Inorder*/
void  Postorder(BTNode *bt)
  {/*后序递归遍历*/
        if(bt)
     {
           Postorder(bt->lchild);
           Postorder(bt->rchild);
            printf("%c",bt->cdata);
     }
   }/* Postorder*/
void LevelOrder(BTNode *bt) /*层次遍历二叉树bt*/    
    { BTNode* queue[MAXSIZE];
      int front,rear;
      if (bt==NULL) return;
      front=0;      /*非循环队列*/
      rear=0;
      queue[rear++]=bt;
      while(front!=rear)
          {printf("%c",queue[front]->cdata);        /*访问队首结点的数据域*/
             if (queue[front]->lchild!=NULL)   /*将队首结点的左孩子指针入队列*/
             {  queue[rear]=queue[front]->lchild;rear++;
             }
            if (queue[front]->rchild!=NULL)   /*将队首结点的右孩子指针入队列*/
            {  queue[rear]=queue[front]->rchild; rear++;
         }
      front++;
   } /* while */
}/* LevelOrder*/
void main()
{
  int i,j=1;
  BTNode *t;
  t=Create_BiTree();
  while(j)
   {
     printf("\n"); /*功能菜单*/
     printf("请选择操作:\n");
     printf("1:  二叉树的前序遍历\n");
     printf("2:  二叉树的中序遍历\n");
     printf("3:  二叉树的后序遍历\n");
     printf("4:  二叉树的层次遍历\n");
     printf("0:  退出程序\n");
     scanf("%d",&j);
     switch(j)
     {
         case 0: printf(" 程序退出!\n ");exit(0);
         case 1: printf("前序遍历结果:\n"); Preorder(t);
                  break;
         case 2: printf("中序遍历结果:\n"); Inorder(t);
                  break;
         case 3: printf("后序遍历结果:\n"); Postorder(t);
                  break;
         case 4: printf("按层遍历结果:\n");
                  LevelOrder(t);break;
         default : printf("\n输入无效，请重新选择操作!\n" );break;
      }
   }
}