[抄题报告][UVA]UVA – 122 Trees on the level – 树的层次遍历

题目地址:

https://cn.vjudge.net/problem/UVA-122

题目描述:

(有道翻译)

Background
背景

s are fundamental in many branches of computer science (Pun definitely intended). Current stateof-the art parallel computers such as Thinking Machines’ CM-5 are based on fat trees. Quad- and octal-trees are fundamental to many algorithms in computer graphics
在计算机科学的许多分支中,树是最基本的(双关语)。目前的艺术并行计算机,比如思维机器的cm-5,都是建立在脂肪树的基础上的。四轴和八叉树是计算机图形学中许多算法的基础。(老乔表示就算翻译了还是看不懂这在写什么,但是好像挺厉害的样子)

This problem involves building and traversing binary trees.
这个问题涉及到构建和遍历二叉树。

Given a sequence of binary trees, you are to write a program that prints a level-order traversal of each tree. In this problem each node of a binary tree contains a positive integer and all binary trees have have fewer than 256 nodes.
给定一组二叉树,您将编写一个程序来打印每棵树的级序遍历。在这个问题中,二叉树的每个节点都包含一个正整数,所有的二叉树都有少于256个节点。

In a level-order traversal of a tree, the data in all nodes at a given level are printed in left-to-right order and all nodes at level k are printed before all nodes at level k + 1.
在树的层次遍历中,在给定级别上的所有节点的数据都以从左到右的顺序打印,在k+1层的所有节点之前,所有节点的所有节点都被打印出来。

For example, a level order traversal of the tree on the right is: 5, 4, 8, 11, 13, 4, 7, 2, 1.
例如,右边的树的水平顺序遍历是:5、4、8、11、13、4、7、2、1。

In this problem a binary tree is specified by a sequence of pairs ‘(n,s)’ where n is the value at the node whose path from the root is given by the string s. A path is given be a sequence of ‘L’s and ‘R’s where ‘L’ indicates a left branch and ‘R’ indicates a right branch.
在这个问题上所指定的二叉树是一个序列(n,s),其中n的值是通过s字符串指定的从根节点出发的路径所指向的节点的值。(这句话该怎么讲比较清楚?)一个路径是一个序列的L和R就是“L”表明左分支和“R”表明右分支。

In the tree diagrammed above, the node containing 13 is specified by (13,RL), and the node containing 2 is specified by (2,LLR). The root node is specified by (5,) where the empty string indicates the path from the root to itself. A binary tree is considered to be completely specified if every node on all root-to-node paths in the tree is given a value exactly once.
在上面的树图中,包含13的节点是由(13,RL)指定的,并且包含2的节点是由(2,LLR)指定的。根节点由(5,)指定,其中空字符串表示从根到自身的路径(头节点)。如果树中所有节点的路径上的每个节点都有一个确切的值,那么就会考虑将二进制树完全指定。

QQ截图20170717212005

The Input
输入

The input is a sequence of binary trees specified as described above. Each tree in a sequence consists of several pairs ‘(n,s)’ as described above separated by whitespace. The last entry in each tree is ‘()’. No whitespace appears between left and right parentheses.
输入是如上所述的一组二叉树。序列中的每棵树都由几对“(n,s)”组成,如上所述,由空格分隔。每棵树的最后一个条目是“()”。左和右括号之间没有空格。

All nodes contain a positive integer. Every tree in the input will consist of at least one node and no more than 256 nodes. Input is terminated by end-of-file.
所有节点都包含一个正整数。输入中的每棵树都至少包含一个节点,而且不超过256个节点。输入以文件结束结束。

The Output
输出

For each completely specified binary tree in the input file, the level order traversal of that tree should be printed. If a tree is not completely specified, i.e., some node in the tree is NOT given a value or a node is given a value more than once, then the string ‘not complete’ should be printed.
对于输入文件中的每一个完全指定的二叉树,应该打印该树的水平顺序遍历。如果树不是完全指定的,也就是说。树中的某个节点没有给出一个值,或者一个节点的值不止一次,因此应该输出字符串“not complete”。

Sample Input
输入示例

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

Sample Output
输出示例

5 4 8 11 13 4 7 2 1
not complete


 

我的分析

我一开始没有摸清题意,以为只有256个节点,所以开了个256 + 10个单元的一位数组,妄图想写这题。但很明显,有256个节点的话,如果都是右节点的话,这个数组将有2的256次方-1那么大,这是不可能的。好不容易通关了Sample Input,想到这玩意就根本不想写了。

那么就要用结构体把链表串起来了吗?可是如果先有了后面的节点,再读取到前面的节点,如此一来,该怎么把这些节点接起来呢?

在看完书上的解答与参考代码后,我才发现自己忽略了一点,那就是如果该树存在,则只要能走到这个相对偏下面的节点的话,它走过的路途的节点也存在;反之,如果走到这个节点之前没有赋值,则这棵树就不符合规则了。

书上的结构体有一个bool型的变量have_value,来判定这个节点是否被赋过值。再用一个全局变量failed去判定本次是否成功。

而半年前学的层次遍历,竟然有些生疏了,惭愧。

另外,本题读取输入的方式很有意思。通过read_input()函数,不断地通过scanf(“%s”,s)去读取字符串,本题的字符串很有意思,每对输入的括号之间都有空格隔开,这很适合使用scanf的%s,因为这个函数遇到回车还是空格都会停止。

本题不能一边遍历一边输出,因为无法判定在后面某个节点没有赋值的情况。所以必须预先存在一个数组里。

最后记得还是把申请的空间返还比较好一些。

代码