2.c

2叉树建立以及遍历 2叉树建立以及遍历

#include<stdio.h>
#include<malloc.h>
#define maxsize 100
typedef struct Btreenode
{
  char data;
  struct Btreenode *lchild;
  struct Btreenode *rchild;
}Btree;
typedef struct
{
  Btree *A[maxsize];
  int top;
}Stack;
Stack *creatstack()
{
   Stack *s;
   s=(Stack *)malloc(sizeof(Stack));
   s->top=0;
   return s;
}
int empty(Stack *s)
{
    if(s->top<0)return 1;
    else return 0;
}
void push(Stack *s,Btree *p)
{
  s->A[s->top]=p;
  s->top++;
}
Btree *pop(Stack *s)
{
  s->top--;
  return s->A[s->top];
}
Btree *creatbtree()
{
   Stack *s;
   Btree *p,*q,*t;
   char ch;
   s=creatstack();
   printf("按前序输入2叉树，以@代表空,最后一个以#结束\n");
   scanf("%c",&ch);
   p=(Btree *)malloc(sizeof(Btree));
   p->data=ch;
   p->lchild=NULL;
   p->rchild=NULL;
   push(s,p);
   t=p;
   scanf("%c",&ch);
   while(ch!='#'&&!empty(s))
   {
     if(ch!='@')
     {
      q=(Btree *)malloc(sizeof(Btree));
      q->data=ch;
      q->lchild=NULL;
      q->rchild=NULL;
      p->lchild=q;
      push(s,q);
      p=q;
     }
     else
     {
      p=pop(s);
      scanf("%c",&ch);
        while(ch=='@')
        {
         p=pop(s);
         scanf("%c",&ch);
        }
         q=(Btree *)malloc(sizeof(Btree));
         q->data=ch;
         q->lchild=NULL;
         q->rchild=NULL;
         p->rchild=q;
         push(s,q);
         p=q;
     }
     scanf("%c",&ch);
   }
 return t;
}
void visit(Btree *s)
{
  printf("%c",s->data);
}
void preord(Btree *t)//前序 
{
    Stack *s;
    s=creatstack();
    Btree *p=t;
    while (p!=NULL||!empty(s))
    {
        if(p!=NULL)             
        {
            visit(p);
            push(s,p);
            p=p->lchild;  
        }
        else         
        {
            p=pop(s);
            p=p->rchild;        
        }
                
    } 
} 
void inord(Btree *t)//中序 
{
    Stack *s;
    s=creatstack();
    Btree *p=t;
    while (p!=NULL||!empty(s))
    {
        if(p!=NULL)             
        {
            push(s,p);
            p=p->lchild;  
        }
        else        
        {
            p=pop(s);
            visit(p);
            p=p->rchild;        
        }
                
    } 
} 
/*void preord(Btree *p)//前序   根-左-右 
{
    if(p)
     {
      printf("%c",p->data);//访问根结点 
      preord(p->lchild);
      preord(p->rchild);
     }
}
void inord(Btree *p)//中序  左-根-右 
{
    if(p)
     {
      inord(p->lchild);
      printf("%c",p->data);//访问左孩子 
      inord(p->rchild);
     }
}
void postord(Btree *p)//后序 左-右-根 
{
     if(p)
     {
      postord(p->lchild);
      postord(p->rchild);
      printf("%c",p->data);//访问右孩子 
      }    
}*/
int main()
{
//    int sign,flag=1;
    Btree *T;
    T=creatbtree();
  /*  while(flag==1)
    { 
      printf("  请选择选项0-3\n"); 
      printf("1.按前序遍历输出\n");
      printf("2.按中序遍历输出\n");
      printf("3.按后序遍历输出\n");
      printf("0.退出\n");
        scanf("%d",&sign);
         switch(sign)
		{
		case 1:if(T)
				 {
                  printf("前序遍历输出:");
                  preord(T);
                  printf("\n");
				 }
                else 
		          printf("2叉树为空!\n");
                break;
        case 2:if(T)
				 {
                  printf("中序遍历输出:");
                  inord(T);
                  printf("\n");
				 }
                 else 
				 printf("2叉树为空!\n");
                 break;
      /*  case 3:if(T)
				 {
                  printf("后序遍历输出:");
                  postord(T);
                  printf("\n");
				 }
                 else 
				 printf("2叉树为空!\n");
                 break;
        default:{flag=0;}
        }
   }*/
   //preord(T);
   inord(T);
   system("pause");
   return 0;
}