描述

给定一棵有n（n≤1000）个元素的完全二叉树，分别对其进行先序、中序和后序遍历，输出对应的遍历序列。

例如给定完全二叉树：1 2 3 4 5 6

先序序列：1 2 4 5 3 6

中序序列：4 2 5 1 6 3

后序序列：4 5 2 6 3 1

格式

输入格式

第一行一个整数n，表示这棵完全二叉树的元素数目；第二行是n个整数，分别表示这棵二叉树上的元素值。

输出格式

输出为三行，第一行是先序遍历序列，第二行是中序遍历序列，第三行是后序遍历序列。数值之间用空格分隔

样例

输入样例

8
246 53 520 879 865 388 745 477

输出样例

246 53 879 477 865 520 388 745
477 879 53 865 246 388 520 745
477 879 865 53 388 745 520 246

限制

时间限制：300 ms
内存限制：16384 KB

代码

  1. #include<stdio.h>
  2. #include<stdlib.h>
  4. typedef struct bitree
  5. {
  6.     int data;
  7.     struct bitree *lchild,*rchild;
  8. } BiTNode;
  10. BiTNode* CreateBiTree(int *,int);
  11. void PreOderTraverse(BiTNode *);
  12. void PreOderTraverse_hou(BiTNode *);
  13. void PreOderTraverse_zhong(BiTNode *);
  15. int main()
  16. {
  17.     BiTNode *t;
  18.     int n,i;
  19.     scanf("%d",&n);
  20.     int a[1001];
  21.     for(i=0; i<n; i++)
  22.     {
  23.         scanf("%d",&a[i]);
  24.     }
  25.     //int a[10] = {1,2,3,4,5,6,7,8,9};                 //树中结点的数据
  27.     t = CreateBiTree(a,n);
  29.     PreOderTraverse(t);
  30.     printf("\n");
  31.     PreOderTraverse_zhong(t);
  32.     printf("\n");
  33.     PreOderTraverse_hou(t);
  35.     return 0;
  36. }
  38. //创建二叉树
  39. BiTNode* CreateBiTree(int *a,int n)
  40. {
  41.     BiTNode *root,*p;
  42.     BiTNode *bitQueue[n];                        //定义一个队列用来存放完全二叉树
  43.     int front=1,rear=1;                          //初始化队列
  44. //生成结点并入队
  45.     int i;
  46.     for(i=0; i<n; i++)
  47.     {
  48.         if(*(a+i) == 0)
  49.             p = NULL;
  50.         else
  51.         {
  52.             p = (BiTNode *)malloc(sizeof(BiTNode));
  53.             p->data = *(a+i);
  54.             p->lchild = p->rchild = NULL;
  55.         }
  56.         bitQueue[rear++] = p;                    //p结点入队,队尾指针加 1
  57.         if(i==0) root = p;                       //初始化根节点
  58.     }
  59. //找出结点间的父子关系
  60.     while(front != rear)                         //如果队列不为空
  61.     {
  62.         p = bitQueue[front];                    //当前要找关系的结点
  63.         if(p != NULL)
  64.         {
  65.             if(2*front <= n)    p->lchild = bitQueue[2*front];
  66.             if(2*front+1 <= n)  p->rchild = bitQueue[2*front+1];
  67.         }
  68.         front++;                               //队头指针加 1，指向下一个结点
  69.     }
  71.     return root;
  72. }
  74. //前序遍历
  75. void PreOderTraverse(BiTNode *t)
  76. {
  77.     if(t)                   //如果树不为空
  78.     {
  79.         printf("%d ",t->data);
  80.         PreOderTraverse(t->lchild);
  81.         PreOderTraverse(t->rchild);
  82.     }
  83. }
  84. //中序遍历
  85. void PreOderTraverse_zhong(BiTNode *t)
  86. {
  87.     if(t)                   //如果树不为空
  88.     {
  89.         PreOderTraverse_zhong(t->lchild);
  90.         printf("%d ",t->data);
  91.         PreOderTraverse_zhong(t->rchild);
  92.     }
  93. }
  94. //后序遍历
  95. void PreOderTraverse_hou(BiTNode *t)
  96. {
  97.     if(t)                   //如果树不为空
  98.     {
  99.         PreOderTraverse_hou(t->lchild);
  101.         PreOderTraverse_hou(t->rchild);
  102.          printf("%d ",t->data);
  103.     }
  104. }