J7 实践-7 落叶

题目描述

一棵字母二叉树如下图所示。熟悉二叉树的读者可以跳过字母二叉树、二叉树树叶和字母二叉搜索树的定义，直接看问题描述。

一棵字母二叉树可以是两者之一：①空树：②有一个根节点，每个节点都以一个学母作为，并且有指向左子树和右子树的指针，左右子树也是字母二叉树。

二叉树的树叶是一个左右子树都为空的节点。在上图的实例中有 $5$ 个树叶节点，分别为 $B$、$D$、$H$、$P$ 和 $Y$。

字母二叉搜索树是每个节点满足下述条件的字母二叉树：

（1）按字母序，根节点的数据在左子树的所有节点的数据之后；

（2）根节点的数据在右子树的所有节点的数据之前。

在一棵字母二叉搜索树上删除树叶，并将被删除的树叶列出；重复这一过程，直到树为空。制如，从左边的树开始，产生树的序列如下图所示，最后产生空树。

删除的树叶序列如下：

BDHPY
CM
GQ
K

给定一个字母二叉搜索树的树叶删除序列，输出树的先序遍历。

输入格式

输入包含多个测试用例。每个测试用例都是一行或多行大写字母序列，每行都给出按上述描述步骤从二叉搜索树中删除的树叶，每行给出的字母都按字母升序排列。在测试用例之间以一行分隔，该行仅包含一个星号*。在最后一个测试用例后给出一行，该行仅给出一个符号$。在输入中没有空格或空行。

输出格式

对于每个测试用例，都有唯一的二叉搜索树，单行输出该树的先序遍历。

样例输入

BDHPY
CM
GQ
K
*
AC
B
$

样例输出

KGCBDHQMPY
BAC

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$1 \le n\leq 100$。