UVa 122 Trees on the level(二叉树层序遍历)

时间:2022-09-18 22:05:28

Trees are fundamental in many branches of computer science. Current state-of-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.

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.

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.

For example, a level order traversal of the tree

UVa 122 Trees on the level(二叉树层序遍历)

is: 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. 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.

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.

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.

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.

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

题意

把给你的所有结点转成一棵树,并按层次遍历输出

题解

用链表的就不多说了,贴个数组的

代码

 #include<bits/stdc++.h>
using namespace std;
int Left[],Right[],V[],failed,cnt;
vector<int> vec;
void addnode(int v,char *s)
{
int n=strlen(s);//s[0]=','后的一个字符
int u=;
for(int i=;i<n;i++)
{
if(s[i]=='L')
{
if(Left[u]==-)
{
++cnt;
Left[cnt]=Right[cnt]=V[cnt]=-;
Left[u]=cnt;
}
u=Left[u];
}
else if(s[i]=='R')
{
if(Right[u]==-)
{
++cnt;
Left[cnt]=Right[cnt]=V[cnt]=-;
Right[u]=cnt;
}
u=Right[u];
}
else break;
}
if(V[u]!=-)failed=;//节点值已经存在
V[u]=v;
}
int bfs()
{
vec.clear();
queue<int> qu;
qu.push();
while(!qu.empty())
{
int top=qu.front();qu.pop();
if(V[top]==-)return ;//节点没有赋值
vec.push_back(V[top]);
if(Left[top]!=-)qu.push(Left[top]);
if(Right[top]!=-)qu.push(Right[top]);
}
return ;
}
int read()
{
int v;
char s[];
Left[]=Right[]=V[]=-;//0为根节点
failed=;
cnt=;
for(;;)
{
if(scanf("%s",s)!=)return ;
if(!strcmp(s,"()"))break;
sscanf(&s[],"%d",&v);//从s[1]开始读一个数字
addnode(v,strchr(s,',')+);
}
return ;
}
int main()
{
while(read())
{
if(failed==||bfs()==)
printf("not complete\n");
else
for(int i=;i<vec.size();i++)
printf("%d%c",vec[i],i==vec.size()-?'\n':' ');
}
return ;
}

UVa 122 Trees on the level(二叉树层序遍历)的更多相关文章

  1. UVA&period;122 Trees on the level&lpar;二叉树 BFS&rpar;

    UVA.122 Trees on the level(二叉树 BFS) 题意分析 给出节点的关系,按照层序遍历一次输出节点的值,若树不完整,则输出not complete 代码总览 #include ...

  2. UVa 122 Trees on the level &lpar;动态建树 &amp&semi;&amp&semi; 层序遍历二叉树&rpar;

    题意  :输入一棵二叉树,你的任务是按从上到下.从左到右的顺序输出各个结点的值.每个结 点都按照从根结点到它的移动序列给出(L表示左,R表示右).在输入中,每个结点的左 括号和右括号之间没有空格,相邻 ...

  3. UVA 122 -- Trees on the level (二叉树 BFS)

     Trees on the level UVA - 122  解题思路: 首先要解决读数据问题,根据题意,当输入为“()”时,结束该组数据读入,当没有字符串时,整个输入结束.因此可以专门编写一个rea ...

  4. UVa 122 Trees on the level(链式二叉树的建立和层次遍历)

    题目链接: https://cn.vjudge.net/problem/UVA-122 /* 问题 给出每个节点的权值和路线,输出该二叉树的层次遍历序列. 解题思路 根据输入构建链式二叉树,再用广度优 ...

  5. UVA - 122 Trees on the level (二叉树的层次遍历)

    题意:给定结点值和从根结点到该结点的路径,若根到某个叶结点路径上有的结点输入中未给出或给出超过一次,则not complete,否则层次遍历输出所有结点. 分析:先建树,建树的过程中,沿途结点都申请了 ...

  6. uva 122 trees on the level——yhx

    题目如下:Given a sequence of binary trees, you are to write a program that prints a level-order traversa ...

  7. UVa 122 Trees on the level

    题目的意思: 输入很多个节点,包括路径和数值,但是不一定这些全部可以构成一棵树,问题就是判断所给的能否构成一棵树,且没有多余. 网上其他大神已经给出了题目意思:比如我一直很喜欢的小白菜又菜的博客 说一 ...

  8. 【LeetCode-面试算法经典-Java实现】【107-Binary Tree Level Order Traversal II(二叉树层序遍历II)】

    [107-Binary Tree Level Order Traversal II(二叉树层序遍历II)] [LeetCode-面试算法经典-Java实现][全部题目文件夹索引] 原题 Given a ...

  9. &lbrack;LeetCode&rsqb; 107&period; Binary Tree Level Order Traversal II 二叉树层序遍历 II

    Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left ...

随机推荐

  1. 读取一个文件,将其Base64编码,每76个字符加一个换行&lpar;转&rpar;

    echo chunk_split(base64_encode(file_get_contents('base64.txt'))); 例子 1 本例分隔每个字符,并添加 ".": & ...

  2. Java版将EXCEL表数据导入到数据库中

    1.采用第三方控件JXL实现 try { //实例化一个工作簿对象 Workbook workBook=Workbook.getWorkbook(new File("F://qzlx.xls ...

  3. JMeter插件之 BlazeMeter&&num;39&semi;s XMPP----测试Openfire等

    JMeter也可以测试XMPP协议了,之前一直使用Tsung或者是直接写java代码结合Java request来进行,现在可以用BlazeMeter提供的插件来进行XMPP测试,无需过多编码. 首先 ...

  4. Spring Boot缓存应用实践

    缓存是最直接有效提升系统性能的手段之一.个人认为用好用对缓存是优秀程序员的必备基本素质. 本文结合实际开发经验,从简单概念原理和代码入手,一步一步搭建一个简单的二级缓存系统. 一.通用缓存接口 1.缓 ...

  5. &lbrack;Kubernetes&rsqb;容器日志的收集与管理

    在开始这篇文章之前,首先要明确一点: Kubernetes 中对容器日志的处理方式,都叫做 cluster-level-logging ,也就是说,这个日志处理系统,与容器, Pod 以及 Node ...

  6. Maven初窥门径

    Maven项目对象模型,可以使用一小段描述来管理项目的构建,报告和文档的软件项目管理工具. 安装 下载地址:http://maven.apache.org/download.cgi 下载解压,我将它放 ...

  7. Tomcat8源码笔记&lpar;四&rpar;Server和Service初始化

    上一章 简单说明下Tomcat各个组件: Server:服务器,Tomcat服务器,一个Tomcat只有一个Server组件; Service:业务层,是Server下最大的子容器,一个Server可 ...

  8. fork调用的底层实现

    fork调用的内核实现: http://www.cnblogs.com/huangwei/archive/2010/05/21/1740794.html http://blog.csdn.net/he ...

  9. JSON数据的处理中的特殊字符

    JSON现在是很常见的处理数据的方式了.但由于自己使用的是反射获取数据,必须自己处理特殊字符,但总是发现有一些看不见的字符在前台 var obj = jQuery.parseJSON(msg);会转换 ...

  10. BZOJ1226 SDOI2009学校食堂(状压dp)

    由于Bi<=7,考虑状压. 如果考虑前i个位置的话,状态里需要压入前7个人后7个人,显然是跑不动的. 那么改成考虑前i个人.于是设f[i][j][k]表示前i个人都已吃完饭,i+1后面7个人的吃 ...