ch6_traverse.c

本人讲授数据结构课程时的所写的示例程序

/*
树的遍历
author: kk.h
date: 2006.10
http://www.cocoon.org.cn
*/

#include "stdio.h"

typedef char ElemType;
typedef struct BiTNode{
  ElemType data;
  struct BiTNode *lchild,*rchild;
}BiTNode;


/* 先根遍历 */
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)
{   int i=0;
    BiTNode *p,*s[20];
    p=bt;
    do
    {  while(p!=NULL)
       {   s[i++]=p;
           p=p->lchild;
       }
       if(i>0)
       {   p=s[--i];
           printf("%c ",p->data);
           p=p->rchild;
       }
    }while(i>0||p!=NULL);
}

/* 用队列实现层次遍历 */
void lev_traverse(BiTNode* T)
{
  BiTNode *q[100],*p;
  int head,tail, i;
  q[0]=T;head=0;tail=1;
  while(head<tail) { /* 当队列不空 */
    p=q[head++];
    printf("%c ",p->data);

    if(p->lchild!=NULL)
      q[tail++]=p->lchild;

    if(p->rchild!=NULL)
      q[tail++]=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 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("\n\nPreOrder:\n");
  preorder(T);

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

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

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

  printf("\n\nlev_traverse:\n");
  lev_traverse(T);

  freetree(T);

  /*
  printf("\n\nplease input inorder:such as 'abc  de g  f   '\n");
  T = crt_bt_pre();
  printf("\n\nPreOrder:\n");
  preorder(T);
  printf("\n\nInOrder:\n");
  inorder(T);
  freetree(T);
  */

  getch();
}