二叉树的四种遍历算法

  1. #include <stdio.h>
  2. #include <malloc.h>
  3. #define MaxSize 100
  4. #define MaxWidth 40
  6. typedef char ElemType;
  8. typedef struct tnode
  9. {
  10.     ElemType data;
  11.     struct tnode *lchild,*rchild;
  12. } BTNode;
  14. void CreateBTree(BTNode * &bt,char *str)    /*由str创建二叉链bt*/
  15. {
  16.     BTNode *St[MaxSize],*p=NULL;
  17.     int top=-1,k,j=0;  
  18.     char ch;
  19.     bt=NULL;            /*建立的二叉树初始时为空*/
  20.     ch=str[j];
  21.     while (ch!='\0')      /*str未扫描完时循环*/
  22.     {
  23.               switch(ch) 
  24.         {
  25.         case '(':top++;St[top]=p;k=1; break;    /*为左孩子结点*/
  26.         case ')':top--;break;
  27.         case ',':k=2; break;                    /*为孩子结点右结点*/
  28.         default:p=(BTNode *)malloc(sizeof(BTNode));
  29.                 p->data=ch;p->lchild=p->rchild=NULL;
  30.                 if (bt==NULL)                   /**p为二叉树的根结点*/
  31.                     bt=p;
  32.                 else                              /*已建立二叉树根结点*/
  33.                 {    switch(k) 
  34.                     {
  35.                     case 1:St[top]->lchild=p;break;
  36.                     case 2:St[top]->rchild=p;break;
  37.                     }
  38.                 }
  39.         }
  40.         j++;
  41.         ch=str[j];
  42.     }
  43. }
  45. void DispBTree(BTNode *bt)    /*以括号表示法输出二叉树*/
  46. {
  47.     if (bt!=NULL)
  48.     {    
  49.         printf("%c",bt->data);
  50.         if (bt->lchild!=NULL || bt->rchild!=NULL)
  51.         {    
  52.             printf("(");
  53.             DispBTree(bt->lchild);        /*递归处理左子树*/
  54.             if (bt->rchild!=NULL) 
  55.                 printf(",");
  56.             DispBTree(bt->rchild);        /*递归处理右子树*/
  57.             printf(")");
  58.         }
  59.     }
  60. }
  62. // 先序遍历序列
  63. void PreOrder(BTNode *bt)
  64. {
  65.     if (bt!=NULL)
  66.     {
  67.         printf("%c ",bt->data);
  68.         PreOrder(bt->lchild);
  69.         PreOrder(bt->rchild);
  70.     }
  71. }
  73. // 中序遍历序列
  74. void InOrder(BTNode *bt)
  75. {
  76.     if (bt!=NULL)
  77.     {    
  78.         InOrder(bt->lchild);
  79.         printf("%c ",bt->data);
  80.         InOrder(bt->rchild);
  81.     }
  82. }
  84. // 后序遍历序列
  85. void PostOrder(BTNode *bt)
  86. {
  87.     if (bt!=NULL)
  88.     {
  89.         PostOrder(bt->lchild);
  90.         PostOrder(bt->rchild);
  91.         printf("%c ",bt->data);
  92.     }
  93. }
  95. // 层次遍历序列
  96. void LevelOrder(BTNode *b)
  97. {
  98.     BTNode *p;
  99.     BTNode *qu[MaxSize];            /*定义环形队列,存放结点指针*/
  100.     int front,rear;                    /*定义队头和队尾指针*/
  101.     front=rear=-1;                    /*置队列为空队列*/
  102.     rear++;
  103.     qu[rear]=b;                        /*根结点指针进入队列*/
  104.     while (front!=rear)                /*队列不为空*/
  105.     {    front=(front+1)%MaxSize;
  106.         p=qu[front];                /*队头出队列*/
  107.         printf("%c ",p->data);        /*访问结点*/
  108.         if (p->lchild!=NULL)        /*有左孩子时将其进队*/
  109.         {    rear=(rear+1)%MaxSize;
  110.             qu[rear]=p->lchild;
  111.         }
  112.         if (p->rchild!=NULL)        /*有右孩子时将其进队*/
  113.         {    rear=(rear+1)%MaxSize;
  114.             qu[rear]=p->rchild;
  115.         }
  116.     } 
  117. }
  119. void main()
  120. {
  121.     BTNode *bt;
  122.     CreateBTree(bt,"A(B(D,E(G,H)),C(,F(I)))");    /*构造图5.10(a)所示的二叉树*/
  123.     printf("二叉树bt:");DispBTree(bt);printf("\n");
  124.     printf("先序遍历序列:");PreOrder(bt);printf("\n");
  125.     printf("中序遍历序列:");InOrder(bt);printf("\n");
  126.     printf("后序遍历序列:");PostOrder(bt);printf("\n");
  127.     printf("层次遍历序列:");LevelOrder(bt);printf("\n");
  128. }