LG#P1305. 新二叉树

新二叉树

题目描述

\hspace{15pt}给定一棵有 nn 个节点的二叉树,每个节点用一个互不相同的小写字母表示。每个节点至多有一个左子节点和一个右子节点。输入第一条节点记录中的节点是根节点。

\hspace{15pt}请输出这棵树的前序遍历。前序遍历的顺序是:先访问当前节点,再前序遍历左子树,最后前序遍历右子树;空子树不输出任何字符。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦26)n\left(1\leqq n\leqq26\right),代表节点数量。

\hspace{15pt}此后 nn 行,每行输入一个长度为 33 的字符串。第一个字符为当前节点,第二、三个字符分别为它的左、右子节点。节点字符均为小写字母,字符 ‘*’\texttt{`*'} 表示对应子节点不存在。

\hspace{15pt}保证这些记录恰好构成一棵二叉树,第一条记录对应根节点,其余记录的顺序不作要求。

输出格式

\hspace{15pt}输出一行字符串,代表前序遍历中依次访问的节点字母,中间不加空格。

测试样例

6
abc
bdi
cj*
d**
i**
j**
abdicj

样例 1 解释

\hspace{15pt}先访问根节点 ‘a’\texttt{`a'},然后依次访问左子树中的 ‘b’,‘d’,‘i’\texttt{`b'},\texttt{`d'},\texttt{`i'},最后访问右子树中的 ‘c’,‘j’\texttt{`c'},\texttt{`j'},得到 "abdicj"\texttt{"abdicj"}。

3
z*a
a*b
b**
zab