树的层次遍历

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file vlevel.in Output file vlevel.out

【题目描述】




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

给你一个两叉树,你的任务是写一个程序来排列印依照“阶层(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

【提示】

在此键入。

【来源】

在此键入。