U260684 二叉树的遍历

题目描述

给出一个n个结点的二叉树，求出这棵树的前中后序遍历。

输入格式

输入共n行。

每行三个整数ai,bi,ci,表示编号为ai的结点的左儿子的编号为bi，右儿子的编号为ci，若编号为0表示不存在该结点。

(ai，bi，ci<=n<=100000)

输出格式

输出共三行。

第一行为先序遍历的输出结果，每两个结点的编号间输出一个空格。

第二行为中序遍历的输出结果，每两个结点的编号间输出一个空格。

第三行为后序遍历的输出结果，每两个结点的编号间输出一个空格。

输入输出样例

输入 #1复制

7
1 2 3
2 4 5
3 6 7
4 0 0
5 0 0
6 0 0
7 0 0

输出 #1复制

1 2 4 5 3 6 7
4 2 5 1 6 3 7
4 5 2 6 7 3 1

三序遍历 

#include <iostream>
 
using namespace std;
 
int n,l[100010],r[100010],fa[100010],a,b,c,root=1;
 
void ssortf(int x){
    printf("%d ",x);
     if(l[x]) ssortf(l[x]);
     if(r[x]) ssortf(r[x]);
}
void ssortm(int x){
    if(l[x]) ssortm(l[x]);
    printf("%d ",x);
    if(r[x]) ssortm(r[x]);
}
void ssortl(int x){
    if(l[x]) ssortl(l[x]);
    if(r[x]) ssortl(r[x]);
    printf("%d ",x);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&a,&b,&c);
        l[a]=b;
        r[a]=c;
        fa[b]=fa[c]=a;
    }
    for(int i=1;i<=n;i++){
        if(!fa[i])
            root=i;
    }
    ssortf(root);
    printf("\n");
    ssortm(root);
    printf("\n");
    ssortl(root);
    printf("\n");
    return 0;
}