12.二叉树的序遍历

时间限制: 1 s

 空间限制: 32000 KB

 题目等级 : 白银 Silver

 查看运行结果

题目描述 Description

求一棵二叉树的前序遍历，中序遍历和后序遍历

输入描述 Input Description

第一行一个整数n，表示这棵树的节点个数。

接下来n行每行2个整数L和R。第i行的两个整数Li和Ri代表编号为i的节点的左儿子编号和右儿子编号。

输出描述 Output Description

输出一共三行，分别为前序遍历，中序遍历和后序遍历。编号之间用空格隔开。

样例输入 Sample Input

5

2 3

4 5

0 0

0 0

0 0

样例输出 Sample Output

1 2 4 5 3

4 2 5 1 3

4 5 2 3 1

数据范围及提示 Data Size & Hint

n <= 16

代码：

#include

using namespace std;

#include

struct Tree{

       int data,child[3];

};

Tree tree[17];

void xx(int i)

{

              printf("%d ",tree[i].data);

              for(int j=1;j<=2;++j)

              if(tree[i].child[j]!=0)

              xx(tree[i].child[j]);

}

void hx(int i)

{

              for(int j=1;j<=2;++j)

              if(tree[i].child[j]!=0)

              hx(tree[i].child[j]);

              printf("%d ",tree[i].data);

}

void zx(int i)

{

       if(tree[i].child[1]!=0)//如果有左孩子，就一直找。

       zx(tree[i].child[1]);

       printf("%d ",tree[i].data);//如果没有左孩子，就输出当前点标号，

    if(tree[i].child[2]!=0)

    zx(tree[i].child[2]);//再去访问右孩子，访问右孩子时，也是先访问它的左孩子

       return ;

}

int main()

{

       int n;

       scanf("%d",&n);

       for(int i=1;i<=n;++i)

       {

              tree[i].data=i;

              scanf("%d%d",&tree[i].child[1],&tree[i].child[2]);

       }

       xx(1);

       printf(" ");

       zx(1);

       printf(" ");

       hx(1);

       printf(" ");

       return 0;

}