PID625 / 字符二叉树
题目描述

Stephen最近学习了二叉树的有关内容,他创造了一种树“字符二叉树”。

字符二叉树是这样的:

1) 该二叉树是完全二叉树。

2) 每个节点下面有0~2个孩子。

为了简单化,我们按照层序方式插入。比如说:HEADSHOT,H作为根节点,EA作为H的两个孩子结点。而DS作为E的孩子,HO作为A的孩子。T是D的左孩子。

Stephen想向TX们炫耀,无奈他只会插入操作(笨……),TX们要支持编码,解码,还要支持三种方式的遍历……

Stephen请你编程解决问题。

【来源】

SPOJ HS08 HS08TTC(Tree traversal cipher)

https://hs.spoj.pl/problems/HS08TTC/

输入格式

第一行是一个数字t(t<=10)代表测试数据个数。

接下来t行,每行描述了一组测试数据。每组数据如下格式:

数据的第一行为一个数n(n<=10000),和两个字符串,分别代表所操作字符串长度和两个命令。(第一个命令为:“INORDER”、“PREORDER”或“POSTORDER”,第二个为“ENCODE”或“DECODE”)

第二行为一个长度为n的字符串S,即所操作字符串。(由‘A’到‘Z’组成)

输出格式

输出t行,每行一个字符串。

当第二个命令为“ENCODE”时,即“编码”:将S作为HS08TTC的层序遍历,输出其中序遍历(“INORDER”),前序遍历(“PREORDER”)或后序遍历(“POSTORDER”)。

当第二个命令为“DECODE”时,即“解码”:S作为中序遍历(“INORDER”),前序遍历(“PREORDER”)或后序遍历(“POSTORDER”),求层序遍历。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论