93 lines
2.8 KiB
Markdown
93 lines
2.8 KiB
Markdown
Q1
|
||
```
|
||
通过带空指针信息的先根序列（亦称先序序列）创建二叉树，并进行先根（先序）、中根（中序）、后根（后序）遍历。二叉树结点数据域值为不等于0的整数（可能是正数也可能是负数），空指针用0表示，例如1 5 8 0 0 0 6 0 0表示如下图的二叉树。
|
||
|
||
PA567.jpg
|
||
|
||
输入格式:
|
||
输入为一组用空格间隔的整数，表示带空指针信息的二叉树先根序列。其中空指针信息用0表示。二叉树结点个数不超过150000，高度不超过6000。输入数据保证二叉树各结点数据值互不相等。
|
||
|
||
输出格式:
|
||
输出为3行整数，每个整数后一个空格。第1行为该二叉树的先根序列，第2行为中根序列，第3行为后根序列。
|
||
|
||
输入样例:
|
||
1 5 8 0 0 0 6 0 0
|
||
输出样例:
|
||
1 5 8 6
|
||
8 5 1 6
|
||
8 5 6 1
|
||
代码长度限制
|
||
16 KB
|
||
时间限制
|
||
200 ms
|
||
内存限制
|
||
20 MB
|
||
栈限制
|
||
8192 KB
|
||
```
|
||
|
||
Q2
|
||
```
|
||
编写程序在二叉树中查找给定结点及父结点。二叉树结点的数据域值不等于0的整数。
|
||
|
||
输入格式:
|
||
输入第1行为一组用空格间隔的整数，表示带空指针信息的二叉树先根序列，其中空指针用0表示。例如1 5 8 0 0 0 6 0 0表示如下图的二叉树。第2行为整数m，表示查询个数。接下来m行，每行为一个不等于0的整数K，表示要查找的结点的数据值。m不超过100，二叉树结点个数不超过150000，高度不超过6000。输入数据保证二叉树各结点数据值互不相等。
|
||
|
||
PA567.jpg
|
||
|
||
输出格式:
|
||
输出为m行，每行1个整数，表示被查找结点K的父结点数据值，若二叉树中无结点K或结点K无父结点，则输出0。
|
||
|
||
输入样例:
|
||
1 5 8 0 0 0 6 0 0
|
||
3
|
||
8
|
||
1
|
||
6
|
||
输出样例:
|
||
5
|
||
0
|
||
1
|
||
代码长度限制
|
||
16 KB
|
||
时间限制
|
||
300 ms
|
||
内存限制
|
||
20 MB
|
||
栈限制
|
||
131000 KB
|
||
```
|
||
|
||
Q3
|
||
```
|
||
给定非空二叉树的中根序列和后根序列，请编写程序创建该二叉树，计算其高度和先根序列；如给定的中根和后根序列不合法，则亦能识别。
|
||
|
||
输入格式:
|
||
输入包含多组数据（不超过10组），每组为两行字符串，第一行表示某二叉树的后根序列，第二行表示其中根序列。结点的值均为A-Z的大写字母，故二叉树结点个数不超过26，且保证输入的两个序列都是结点的全排列，但不一定是合法的中根和后根序列。输入保证不是空二叉树。
|
||
|
||
输出格式:
|
||
对于每组数据，如果输入的序列不合法（不是同一棵树的中根序列和后根序列），则输出INVALID；若输入序列合法，输出为两行，第一行为一个整数，表示该二叉树的高度，第二行为一个字符串，表示该二叉树的先根序列。
|
||
|
||
输入样例1:
|
||
CEFDBHGA
|
||
CBEDFAGH
|
||
CBEDFAGH
|
||
CEFDBHGA
|
||
BCA
|
||
CAB
|
||
|
||
输出样例1:
|
||
3
|
||
ABCDEFGH
|
||
INVALID
|
||
INVALID
|
||
|
||
代码长度限制
|
||
16 KB
|
||
时间限制
|
||
50 ms
|
||
内存限制
|
||
64 MB
|
||
栈限制
|
||
8192 KB
|
||
``` |