问题 1758 --算法6-5~6-7:线索二叉树

1758: 算法6-5~6-7:线索二叉树

时间限制: 1 Sec  内存限制: 32 MB
提交: 5  解决: 5
[提交][状态][讨论版][命题人:]

题目描述

在遍历二叉树的过程中,是按照一定的规则将二叉树中的结点排列成一个线性序列,从而得到二叉树中结点的先序序列或中序序列或后序序列。但是,当以二叉链表作为存储结构时,只能找到结点的左右孩子信息,而不能直接得到结点在任意一个序列中的前驱和后继的信息,而这种信息只有在遍历的动态过程中才能够得到。
为了保存这种信息,就需要使用线索链表。其中指向结点的前驱和后继的指针,叫做线索。添加上线索的二叉树称之为线索二叉树。其结点定义如下:
下面给出按照中序遍历将二叉树中序线索化的算法:
在已经线索化的二叉线索树中,进行中序遍历的算法如下所示:
本题中,将会给出一个按照先序遍历得出的字符串,空格代表空的子节点,大写字母代表节点内容。请通过这个字符串建立二叉树,并按照题目描述中算法,中序遍历二叉树并中序线索化二叉树,之后中序遍历输出二叉线索树。

输入

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

输出

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

样例输入

ABC  DE G  F   

样例输出

C B E G D F A 

提示

通过线索化二叉树建立二叉线索树,将给普通二叉树添加更快捷的遍历方式。在线索树上进行遍历,只需要先找到序列中的第一个结点,然后依次找结点后继直至其后继为空时而止。而对于中序线索二叉树,由于其固有的性质,在遍历的过程中虽然时间复杂度依旧为O(n),但常数因子将会比普通的算法减小且不需要栈结构辅助,是一种非常优秀的遍历算法。

来源

[提交][状态]