4400: 【例16-5】二叉树深度优先遍历

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：4 解决：2

题目描述

有一个 �(�≤106) 个结点的二叉树。给出每个结点的两个子结点编号（均不超过 �），建立一棵二叉树（根节点的编号为 1），如果是叶子结点，则输入 0 0。

建好这棵二叉树之后，请求出它的深度。二叉树的深度是指从根节点到叶子结点时，最多经过了几层。

输入

第一行一个整数 �，表示结点数。

之后 � 行，第 � 行两个整数 �、�，分别表示结点 � 的左右子结点编号。若 �=0 则表示无左子结点，�=0 同理。

输出

第1行输出前序遍历结果。

第2行输出中序遍历结果。

第3行输出后序遍历结果。

样例输入 复制 

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

样例输出 复制 

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

提示

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 7;
struct Node {
	int left, right;
} t[MAXN];
int n;
void build(){
	for (int i = 1; i<=n; i++)
	    scanf("%d %d",&t[i].left, & t[i].right);
}
void pre_order(int x) {
	printf("%d ",x);
	if(t[x].left) pre_order(t[x].left);
	if(t[x].right) pre_order(t[x].right);
}
void in_order(int x) {
	if(t[x].left) in_order(t[x].left);
	printf("%d ",x);
	if(t[x].right) in_order(t[x].right);
}
void post_order(int x) {
	if(t[x].left) post_order(t[x].left);
	if(t[x].right) post_order(t[x].right);
	printf("%d ",x);
}
int main(){
    cin >> n;
    build();
    pre_order(1);
    printf("\n");
    in_order(1);
    printf("\n");
    post_order(1);
	return 0;
}

来源/分类

提交提交记录统计露一手!