OI题库

【题目描述】

树状结构在电脑科学的许多领域中都相当重要。本问题牵涉到建立树和访问树。

给你一个两叉树，你的任务是写一个程序来排列印依照“阶层（level-order）」去访问的结果。在本问题中，二叉树的每一个节点包含有一个正整数，并且节点的数目最少1个，最多256个。

在“阶层”访问中，按照从低到高阶层，同阶层从左到右的顺序来打印。例如以下的二叉树阶层访问的结果是：5，4，8，11，13，4，7，2，1

在本问题中，二叉树以节点来表示。每一个节点以一对（n，s）来表示。n代表这节点的值，s为一字串，代表从根节点到达这节点的道路。其中L代表往左，R代表往右。所以在上方的图中值为13的节点的表示为（13，RL），而值为2的节点的表示法为（2，LLR），而根节点为（5，）。

【输入格式】

输入包含有多组测试数据。每个组测试数据为若干节点的集合。各节点之间以white space（包含空白、换行等字符）分离。注意：在各节点内（也就是左刮号到又刮号之间）也会有white space。当遭遇到一个（）的节点，代表该组测试资料结束。请参考Sample Input。

【输出格式】

对每一组测试数据，如果输入的节点可以正常的构成二叉树的话，请输出按“阶层“访问的结果。如果输入的节点无法正常的构成二叉树的话，也就是说有某些该有的节点没有给，或者重复给（同一路有二个节点），请输出not complete。请参考Sample Output。

【样例输入】

(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()
(11,LL) (7,LLL) (2,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()

【样例输出】

5 4 8 11 13 4 7 2 1
not complete
not complete

【提示】

在此键入。

【来源】

在此键入。