Trees on the level
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 584 Accepted Submission(s): 195
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1622
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
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.
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.
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()
not complete
题意： 输入一棵二叉树，按照从上到下从左到右的顺序输出各个节点的值，每个节点都是按照从根节点到他的移动的序列给出的（L表示左，R表示右）在输入中，每个编号左括号和右括号之间没有空格，相邻的节点之间用一个空格隔开，每棵树的输入用括号（）表示结束，这个括号本身不代表一个节点，注意，当根到某个叶节点的路径上的节点没有在输入中给出，或者给出超过一次，输出not complete 节点个数不超过256
题解：学习紫书上的代码，给出完整的用指针和用数组的方法的代码
一、用指针建树：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define maxn 260
char s[maxn];
struct Node{
bool have_value;//是否被赋值过
int v;
Node *left,*right;
Node():have_value(false),left(NULL),right(NULL){}//构造函数
};
Node *root; Node* newnode(){
return new Node();
} bool failed; void remove_tree(Node *u){//防止内存泄漏
if(u == NULL) return;
remove_tree(u->left);
remove_tree(u->right);
delete(u);
} void addnode(int v, char* s){
int n = strlen(s);
Node* u = root;
for(int i = ; i < n; i++){
if(s[i]=='L'){
if(u->left == NULL) u->left = newnode();
u = u->left;
}else if(s[i] == 'R'){
if(u->right == NULL) u->right = newnode();
u = u->right;
}
}
if(u->have_value) failed = true;//已经赋值过的认为是错误的输入
u->v = v;
u->have_value = true;//记得做标记
} bool read_input(){
failed = false;
remove_tree(root);//释放掉之前建立过得树
root = newnode();
for(;;){
if(scanf("%s",s)!=) return false;//整个输入结束
if(!strcmp(s,"()")) break;//读到结束标志
int v;
sscanf(&s[],"%d",&v);//读入节点值
addnode(v,strchr(s,',')+);//查找逗号，然后插入节点
}
return true;
} vector< int > ans; bool bfs(vector<int> & ans){
queue<Node*> q;
ans.clear(); q.push(root);
while(!q.empty()){
Node* u = q.front(); q.pop();
if(!u->have_value) return false;
ans.push_back(u->v);
if(u->left != NULL) q.push(u->left);
if(u->right != NULL) q.push(u->right);
}
return true;
} int main()
{
while(read_input()==true){
if(!failed&&bfs(ans)){
vector<int>::iterator it;
for(it = ans.begin(); it != ans.end()-; it++)
{
printf("%d ", (*it));
}
printf("%d\n",(*it));
}
else puts("not complete");
}
return ;
}
二、用数组代码：
注意，就算是用数组也要先建立路径中的节点
#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#define N 260
const int root = ; char s[N]; int left[N];
int right[N];
bool have_value[N];
int val[N]; int cnt;
void newtree(){ left[root] = right[root] = ; have_value[root] = false; cnt = root; }
int newnode(){ int u = ++cnt; left[u] = right[u] = ; have_value[u] = false; return u; } bool failed; void addnode(int v, char* s){
int n = strlen(s);
// int u = newnode();
int tm = root;
for(int i = ; i < n; i++){
if(s[i]=='L'){
if(left[tm]==) left[tm] = newnode();
tm = left[tm];
}else if(s[i] == 'R'){
if(right[tm]==) right[tm] = newnode();
tm = right[tm];
}
}
if(have_value[tm]) failed = true;//已经赋值过的认为是错误的输入
val[tm] = v;
have_value[tm] = true;//记得做标记
} bool read_input(){
failed = false;
newtree();
for(;;){
if(scanf("%s",s)!=) return false;//整个输入结束
if(!strcmp(s,"()")) break;//读到结束标志
int v;
sscanf(&s[],"%d",&v);//读入节点值
addnode(v,strchr(s,',')+);//查找逗号，然后插入节点
}
return true;
} std::vector< int > ans; bool bfs(std::vector<int> & ans){
std::queue<int> q;
ans.clear(); q.push(root);
while(!q.empty()){
int u = q.front(); q.pop();
if(!have_value[u]) return false;
ans.push_back(val[u]);
if(left[u] != ) q.push(left[u]);
if(right[u] != ) q.push(right[u]);
}
return true;
} using namespace std;
int main()
{
while(read_input()==true){
if(!failed&&bfs(ans)){
vector<int>::iterator it;
for(it = ans.begin(); it != ans.end()-; it++)
{
printf("%d ", (*it));
}
printf("%d\n",(*it));
}
else puts("not complete");
}
return ;
}