怎么训练手指灵活度:二叉树的按层遍历

/*  二叉树应用 */

#include "stdio.h"
#include "stdlib.h"

typedef char ElemType;  /* 结点数据的类型 */
typedef struct BiTNode{
  ElemType data;
  struct BiTNode *lchild,*rchild;
}BiTNode;       /* 树结点类型 */

/*栈的定义及基本操作*/
#define MaxSize 100
typedef BiTNode* SElemType;       /* 栈和队列的结点类型，用于存放树结点 */
typedef struct {
  SElemType elem[MaxSize];
  int top;
}SqStack;       /* 栈 */

void InitStack(SqStack *pS)         /* 初始化栈,开始时栈为空 */
{
  pS->top=0; /* top指向栈顶的上一个元素 */
}

int Push(SqStack *pS,SElemType e)     /* 进栈 */
{
  if (pS->top==MaxSize-1)   /* 栈满 */
    return 0;

  pS->elem[pS->top]=e;
  pS->top=pS->top+1;
  return 1;
}

int Pop(SqStack *pS,SElemType *pe)    /* 出栈 */
{
  if (pS->top==0)  /* 栈空 */
    return 0;

  pS->top = pS->top - 1;
  *pe = pS->elem[pS->top];
  return 1;
}

/*队列（循环队列）的定义及基本操作*/

typedef struct {
  SElemType elem[MaxSize];
  int front,rear;
}SqQueue;      /* 队列 */

void InitQueue(SqQueue* pQ)   /* 初始化队列,开始时队列为空 */
{
  pQ->front=pQ->rear=0;
}

int EnQueue(SqQueue* pQ,SElemType e)       /* 进队 */
{
  if ((pQ->rear+1)%MaxSize == pQ->front) /* 队满 */
    return 0;
  pQ->elem[pQ->rear] = e;
  pQ->rear = (pQ->rear+1)%MaxSize;
  return 1;
}

int DeQueue(SqQueue* pQ,SElemType* pe)      /* 出队 */
{
  if (pQ->rear == pQ->front)    /* 队空 */
    return 0;
  *pe = pQ->elem[pQ->front];
  pQ->front = (pQ->front+1)%MaxSize;
  return 1;
}

/* 先根遍历 */
void preorder(BiTNode *bt)
{  if(bt!=NULL)
   {  printf("%c ",bt->data);
      preorder(bt->lchild);
      preorder(bt->rchild);
   }
}

/* 中根遍历 */
void inorder(BiTNode *bt)
{  if(bt!=NULL)
   {  inorder(bt->lchild);
      printf("%c ",bt->data);
      inorder(bt->rchild);
   }
}

/* 后根遍历 */
void postorder(BiTNode *bt)
{  if(bt!=NULL)
   {  postorder(bt->lchild);
      postorder(bt->rchild);
      printf("%c ",bt->data);
   }
}

/* 非递归算法的中根遍历（后进先出，用了栈的思想） */
void inorder_fdg(BiTNode *bt)
{
    BiTNode *p;
    SqStack s;
    InitStack(&s);
    p=bt;
    do
    {  while(p!=NULL)
       {   Push(&s,p);
           p=p->lchild;
       }
       if(s.top!=0)
       {   Pop(&s,&p);
           printf("%c ",p->data);
           p=p->rchild;
       }
    }while(s.top!=0||p!=NULL);
}

/* 用队列实现层次遍历 */
void lev_traverse(BiTNode* bt)
{
  SqQueue  q;
  BiTNode *p;
  p=bt;
  InitQueue(&q);
  EnQueue(&q,p);
  while(!(q.rear==q.front)) { /* 当队列不空 */
    DeQueue(&q,&p);
    printf("%c ",p->data);

    if(p->lchild!=NULL)
      EnQueue(&q,p->lchild);

    if(p->rchild!=NULL)
       EnQueue(&q,p->rchild);
  }
}

/* 利用先根序列建立二叉树，空的子树也要输入，用空格表示,建立的树通过函数返回,避免使用指针的指针 */
BiTNode *crt_bt_pre()
{  char ch;
   BiTNode *bt;
   scanf("%c",&ch);

   if(ch==' ')  bt=NULL;
   else
   {   bt=(BiTNode *)malloc(sizeof(BiTNode));
       bt->data=ch;
       bt->lchild=crt_bt_pre();
       bt->rchild=crt_bt_pre();
   }
   return(bt);
}

/* 利用先根序列建立二叉树，空的子树也要输入，用空格表示,建立的树通过参数返回,注意和上述方法比较，想想还有什么办法？ */
void crt_bt_pre_2(BiTNode **bt)
{  char ch;
   scanf("%c",&ch);

   if(ch==' ')  (*bt)=NULL;
   else
   {   (*bt)=(BiTNode *)malloc(sizeof(BiTNode));
       (*bt)->data=ch;
       crt_bt_pre_2(&(*bt)->lchild);
       crt_bt_pre_2(&(*bt)->rchild);
   }
}

/* 求叶子数 */
int leaf(BiTNode *bt)
{
   if (bt==NULL) return 0;
   else {
     if (bt->lchild==NULL&&bt->rchild==NULL)  return 1;
       else
       return leaf(bt->lchild)+leaf(bt->rchild);
     }

}

/* 求树的高度 */
int high(BiTNode *bt)
{
   if (bt==NULL) return 0;
   else {
       return max(high(bt->lchild),high(bt->rchild))+1;
     }

}

/* 二叉树的释放*/
void freetree(BiTNode *bt)
{  if(bt!=NULL)
   {  freetree(bt->lchild);
      freetree(bt->rchild);
      free(bt);
      bt=NULL;
   }
}

main()
{
   BiTNode *T,*temp[20];

  /* 笨方法建立二叉树 */
 /* temp[0]=(BiTNode*)malloc(sizeof(BiTNode));
  temp[0]->data = '-';

  temp[1]=(BiTNode*)malloc(sizeof(BiTNode));
  temp[1]->data = '+';
  temp[0]->lchild = temp[1];

  temp[2]=(BiTNode*)malloc(sizeof(BiTNode));
  temp[2]->data = '/';
  temp[0]->rchild = temp[2];

  temp[3]=(BiTNode*)malloc(sizeof(BiTNode));
  temp[3]->data = 'a';
  temp[3]->lchild=NULL; temp[3]->rchild=NULL;
  temp[1]->lchild = temp[3];

  temp[4]=(BiTNode*)malloc(sizeof(BiTNode));
  temp[4]->data = '*';
  temp[1]->rchild = temp[4];

  temp[5]=(BiTNode*)malloc(sizeof(BiTNode));
  temp[5]->data = 'e';
  temp[5]->lchild=NULL; temp[5]->rchild=NULL;
  temp[2]->lchild = temp[5];

  temp[6]=(BiTNode*)malloc(sizeof(BiTNode));
  temp[6]->data = 'f';
  temp[6]->lchild=NULL; temp[6]->rchild=NULL;
  temp[2]->rchild = temp[6];

  temp[7]=(BiTNode*)malloc(sizeof(BiTNode));
  temp[7]->data = 'b';
  temp[7]->lchild=NULL; temp[7]->rchild=NULL;
  temp[4]->lchild = temp[7];

  temp[8]=(BiTNode*)malloc(sizeof(BiTNode));
  temp[8]->data = '-';
  temp[4]->rchild = temp[8];

  temp[9]=(BiTNode*)malloc(sizeof(BiTNode));
  temp[9]->data = 'c';
  temp[9]->lchild=NULL; temp[9]->rchild=NULL;
  temp[8]->lchild = temp[9];

  temp[10]=(BiTNode*)malloc(sizeof(BiTNode));
  temp[10]->data = 'd';
  temp[10]->lchild=NULL; temp[10]->rchild=NULL;
  temp[8]->rchild = temp[10];

  T=temp[0];    */
  /*输出树和各种遍历、叶子数、树的高度*/
  /*printf("\ntree:\n");
  printf("       -\n");
  printf("  +        /\n");
  printf(" a  *    e  f\n");
  printf("0 0b  - 0 00 0\n");
  printf("  0 0c  d\n");

  printf("\n\nPreOrder:\n");
  preorder(T);

  printf("\nInOrder:\n");
  inorder(T);

  printf("\nPostOrder:\n");
  postorder(T);

  printf("\ninorder_fdg:\n");
  inorder_fdg(T);

  printf("\nlev_traverse:\n");
  lev_traverse(T);
  printf("\nleaf num:%d",leaf(T));
  printf("\nTree high:%d",high(T));
  freetree(T);  */

  /* 按先序列建树，用空格表示空子树*/

  printf("\n\nplease input inorder:such as 'abc  de g  f   '\n");
 /*T = crt_bt_pre();*/
   crt_bt_pre_2(&T);

  printf("\n\nPreOrder:\n");
  preorder(T);

  printf("\nInOrder:\n");
  inorder(T);

  printf("\nPostOrder:\n");
  postorder(T);

  printf("\ninorder_fdg:\n");
  inorder_fdg(T);

  printf("\nlev_traverse:\n");
  lev_traverse(T);
  printf("\nleaf num:%d",leaf(T));
  printf("\nTree high:%d",high(T));
  freetree(T);