UVA122 树的层次遍历 Trees on the level

    • 167通过
    • 562提交
  • 题目来源 UVA 122
  • 评测方式 RemoteJudge
  • 标签
  • 难度 提高+/省选-
  • 时空限制 3000ms / 0MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

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

    给你一二元树,你的任务是写一个程式来列印依「阶层(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,)。

    Input

    输入含有多组测试资料。每组测试资料为若干节点的集合。各节点间以white space(包含空白、换列等字元)分隔。注意:在各节点内(也就是左刮号到又刮号之间)不会有white space。当遇到一()的节点,代表该组测试资料结束。请参考Sample Input。

    Output

    对每一组测试资料,如果输入的节点可以正常的构成一二元树的话,请输出按「阶层」走访的结果。如果输入的节点无法正常的构成一二元树的话,也就是说有某些该有的节点没有给,或重複给(同一路径有2个节点),请输出not complete。请参考Sample Output。

    感谢原翻译者:lucky

    题目描述

    PDF

    输入输出格式

    输入格式:

    输出格式:

    输入输出样例

    输入样例#1: 复制
    (11,LL) (7,LLL) (8,R)
    (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
    (3,L) (4,R) ()
    输出样例#1: 复制
    5 4 8 11 13 4 7 2 1
    not complete
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。