404037 - 落叶

一棵字母二叉搜索树如果不是空树，它的每个结点都以一个字母作为数据，并且根据字母表顺序，左子树上的任意结点字母都在根结点前面，而右子树上的任意结点字母都在根结点后面。 在一棵字母二叉搜索树上删除树叶，并将被删除的树叶列出，重复这一过程，直到树为空。例如，从左边的树开始，产生树的序列直到空树的过程如图 删除的树叶序列如下： BDHPY CM GO K 给定一个字母二叉搜索树的树叶删除序列，输出树的前序遍历。

输入包含多组测试数据。每个测试数据都是一行或多行大写字母序列，每行都给出按上述描述步骤从二叉搜索树中删除的树叶，每行给出的字母都按字母升序排列。在测试用命之间以一行分隔，该行仅包含一个字符“*”。全部测试数据结束以字符“$”表示。

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