4510: 【例】【入门】二叉树的遍历(2182)

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

题目描述

给出一个 lns="http://www.w3.org/1998/Math/MathML">n 个结点的二叉树，请求出二叉树的前序遍历，中序遍历和后序遍历。

输入

第一行有一个整数 lns="http://www.w3.org/1998/Math/MathML">n (lns="http://www.w3.org/1998/Math/MathML">0<n≤26)，表示二叉树有 lns="http://www.w3.org/1998/Math/MathML">n 个结点；

以下 lns="http://www.w3.org/1998/Math/MathML">n 行，每行第一个为一个大写字母表示结点的值，第 lns="http://www.w3.org/1998/Math/MathML">i+1 行的结点编号为 lns="http://www.w3.org/1998/Math/MathML">i ；

后面为两整数，第一个表示该结点左孩子结点编号，第二个表示该结点右孩子的结点编号，如果该编号为 lns="http://www.w3.org/1998/Math/MathML">0 表示没有；（编号为 lns="http://www.w3.org/1998/Math/MathML">1 的结点是树的根）

输出

共三行，第一行为二叉树的前序遍历，第二行为中序遍历，第三行为后序遍历；

样例输入 复制 

7
F 2 3
C 4 5
E 0 6
A 0 0
D 7 0
G 0 0
B 0 0

样例输出 复制 

FCADBEG
ACBDFEG
ABDCGEF

提示

【样例解释】

样例对应的二叉树如图所示： 

#include<bits/stdc++.h>
using namespace std;
const int N=30;
struct node {
	char c;
	int lc,rc;
}a[N];
int n;
void dfs1(int x) {
	cout<<a[x].c;
	if (a[x].lc) dfs1(a[x].lc);
	if (a[x].rc) dfs1(a[x].rc);
} 

void dfs2(int x) {
	if (a[x].lc) dfs2(a[x].lc);
	cout<<a[x].c;
	if (a[x].rc) dfs2(a[x].rc);
}

void dfs3(int x) {
	if (a[x].lc) dfs3(a[x].lc);
	if (a[x].rc) dfs3(a[x].rc);
	cout<<a[x].c;
} 
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) {
    	cin>>a[i].c>>a[i].lc>>a[i].rc;
	}
	dfs1(1);
	cout<<endl;
	dfs2(1);
	cout<<endl;
	dfs3(1);
	cout<<endl;		
	return 0;
}

来源/分类

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