数据结构-线索二叉树

在遍历二叉树的过程中，是按照一定的规则将二叉树中的结点排列成一个线性序列，从而得到二叉树中结点的先序序列或中序序列或后序序列。但是，当以二叉链表作为存储结构时，只能找到结点的左右孩子信息，而不能直接得到结点在任意一个序列中的前驱和后继的信息，而这种信息只有在遍历的动态过程中才能够得到。

为了保存这种信息，就需要使用线索链表。其中指向结点的前驱和后继的指针，叫做线索。添加上线索的二叉树称之为线索二叉树。其结点定义如下：

下面给出按照中序遍历将二叉树中序线索化的算法：

在已经线索化的二叉线索树中，进行中序遍历的算法如下所示：

本题中，将会给出一个按照先序遍历得出的字符串，空格代表空的子节点，大写字母代表节点内容。请通过这个字符串建立二叉树，并按照题目描述中算法，中序遍历二叉树并中序线索化二叉树，之后中序遍历输出二叉线索树。

输入只有一行，包含一个字符串S，用来建立二叉树。保证S为合法的二叉树先序遍历字符串，节点内容只有大写字母，且S的长度不超过100。

共一行，包含一串字符，表示按中序遍历二叉线索树得出的节点内容，每个字母后输出一个空格。请注意行尾输出换行。