Falling Leaves
题意翻译
```cpp
上图给出一个字母二叉树的图的表示。熟悉二叉树的读者可以跳过字母二叉树、二叉树树叶和字母二叉搜索树的定义，直接看问题描述。
一棵字母二叉树可以是下述两者之一：
1，它可以是空树；
2，它可以有一个根结点，每个结点以一个字母作为数据，并且有指向左子树和右子树的指针，左右子树也是字母二叉树。
字母二叉树可以用图这样表示：空树忽略不计；每个结点这样标识：结点所包含的字母数据；如果左子树非空，向左下方的线段指向左子树；如果右子树非空，向右下方的线指向右子树。
二叉树的树叶是一个子树都为空的结点。在上图的实例中，有5个树叶结点，数据为B，D，H，P和Y。
字母树的前序遍历定义如下：
如果树为空，则前序遍历也是空的；
如果树不为空，则前序遍历按下述次序组成：访问根结点的数据；前序遍历根的左子树；前序遍历根的右子树。
上图中树的前序遍历是KGCBDHQMPY。
在上图中的树也是字母二叉搜索树。字母二叉搜索树是每个结点满足下述条件的字母二叉树：
按字母序，根结点的数据在左子树的所有结点的数据之后，在右子树的所有结点的数据之前。
请考虑在一棵字母二叉搜索树上的下述的操作序列：
删除树叶，并将被删除的树叶列出；
重复这一过程直到树为空。
从下图中左边的树开始，产生树的序列如图所示，最后产生空树。
移除的树叶数据为
BDHPY
CM
GQ
K
本题给出这样一个字母二叉搜索树的树叶的行的序列，输出树的前序遍历。
输入给出一个或多个测试用例。每个测试用例是一个一行或多行大写字母的序列。
每行给出按上述描述的步骤从二叉搜索树中删除的树叶。每行中给出的字母按字母序升序排列。测试用例之间用一行分隔，该行仅包含一个星号 (‘*’)。
在最后一个测试用例后，给出一行，仅给出一个美元标志 (‘$’)。输入中没有空格或空行。
对于每个输入的测试用例，有唯一的二叉搜索树，产生树叶的序列。输出一行，给出该树的前序遍历，没有空格。
```
帮废龙提交的QWQ
题目描述
[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=448&page=show_problem&problem=4300
[PDF](https://uva.onlinejudge.org/external/15/p1525.pdf)