P1106 - 查找树中的节点
题目描述
给定一棵树，树中的节点是一个字符，由大写字母字符组成的，树的节点数据可以重复出现，比如下面的一棵树：
现在请你编写个程序去输出这棵树的先根遍历、后根遍历、树的高度、以及查找出树中指定的元素x出现的次数和第一次出现的位置
输入样例的数据对应的就是图示中的树
输入格式
输入的第一行包含一个整数 n，表示树的节点数。
接下来的 n 行中，每行提供一个节点 u 的信息，格式如下：
seq data parent
其中 seq 是节点 u 的 序号（序号从1开始，从上往下，从左往右依次编号，每个节点的seq唯一不变）
data 是节点 u 的值域
parent为节点 u 的父节点的seq序号
接下来一行，待查找的字符x
注意：输入的第1个节点不一定是树的根节点信息
输出格式
第1行，树的先根遍历结果，每个值域使用一个空格分隔
第2行，树的后根遍历结果，每个值域使用一个空格分隔
第3行，树的高度（根节点的高度、层次号为1）
第4行，待查找的字符x在这棵树中出现的总次数
第5行，待查找的字符x在这棵树中第一次出现的位置信息：该节点的的序号和该节点所在的层次号，使用空格分隔，如果找不到，输出-1 -1
节点在树中第一次出现的定义：从上往下，从左往右第一次找到的该节点
根节点的高度、层次号为1
输入输出样例
| 输入样例 | 输出样例 |
|---|---|
| 10 1 A -1 2 B 1 3 C 1 4 B 1 5 A 2 6 F 2 7 B 3 8 C 4 9 I 4 10 J 7 B |
A B A F C B J B C I A F B J B C C I B A 4 3 2 2 |
| 10 5 A 2 2 B 1 3 C 1 4 B 1 6 F 2 7 B 3 8 C 4 10 J 7 1 A -1 9 I 4 J |
A B A F C B J B C I A F B J B C C I B A 4 1 10 4 |
数据范围与提示
100%的数据：$1 \le n \le 20$，树的节点中的值域为大写字母
测试点数目
共10个测试点，每个测试点10分
时间与内存限制
每个测试点时间：1000ms（1.0s），内存：256MiB
输入输出模式
本OJ支持两种输入输出模式
1. 标准输入输出模式：
直接从标准输入和标准输出读写数据，不需要使用freopen进行文件输入输出重定向
2. 文件输入输出模式（国内信奥赛输入输出模式）:
从文件中读写数据，需要使用freopen进行输入输出重定向
本题输入文件名为：P1106.in，输出文件名为：P1106.out