转换二叉树

1.2k 词

题目描述

DJ非常痴迷于数据结构,二叉树是他最喜欢的结构模型。这种每个顶点的度不大于2的简单的图总是能激发他的灵感。然而,二叉树的表示方法是一个困扰他已久的问题。如果用链表表示,不直观;画成图形,计算机又难以存储。好在他现在发现了一种既直观,计算机又便于存储的表示方法。该方法定义如下:

1、如果二叉树中节点X是叶子节点,则该节点直接表示为X。
2、如果二叉树中节点X有左子树,则该节点表示为(…)X,括号内为X的左子树。
3、如果二叉树中节点X有右子树,则该节点表示为X(…),括号内为X的右子树。
4、如果二叉树中节点X有左右子树,则该节点表示为(…)X(…),左边括号内为左子树,右边括号内为右子树。

现在DJ有许多二叉树的先序序列和中序序列,DJ要你写个程序帮他把这些二叉树转换为上述表示方法。

输入

输入第一行为一个整数N,表示有N个待转换的二叉树。

接下来有N行,每行由两个字符串组成,中间用空格分开。
每行的第一个字符串为二叉树的先序序列,第二个字符串为二叉树的中序序列。
输入字符串由大写字母组成,每个字母代表二叉树的一个节点,不会有两个相同的字母。
你可以假设不会输入无效数据。

输出

每组数据输出占一行,输出转换后的二叉树。

样例输入

1
2
3
2
AB AB
ABCD BCAD

样例输出

1
2
A(B)
(B(C))A(D)

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100 + 5;
char pre[N], in[N];
void DFS(int ps, int pt, int is, int it){
int pos = is;
while(in[pos] != pre[ps]) pos++;
if(pos != is){
printf("(");
DFS(ps + 1, ps + pos - is, is, pos - 1);
printf(")");
}
printf("%c", pre[ps]);
if(pos != it){
printf("(");
DFS(ps + 1 + pos - is, pt, pos + 1, it);
printf(")");
}
}
int main(){
int T;
scanf("%d", &T);
while(T --){
scanf("%s %s", pre, in);
DFS(0, strlen(pre) - 1, 0, strlen(in) - 1);
printf("\n");
}
return 0;
}