• 二叉树的四种遍历算法

    二叉树的四种遍历算法

    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. }