题意:

给定一颗树, 按层次遍历输出。

分析:

用数组模拟二叉树, bfs即可实现层次遍历

 #include <bits/stdc++.h>
using namespace std;
struct Node{
bool have_value;
int v, left, right;
void reset(){//用于再次初始化节点
init();
}
void init(){
have_value = ;
v = left = right = ;
}
Node():have_value(false), v(),left(), right(){init();}//构造函数
};
const int maxn = ;
Node tree[maxn];
const int root = ;
int cnt, failed;
char s[maxn];
void newtree(){
cnt = ;
tree[root].reset();
}
void addnode(int v, char* s){ int len = strlen(s) - ;
int u = root;
for(int i = ; i < len; i++){
if(s[i] == 'L'){
if(tree[u].left == )
{
tree[u].left = ++cnt;
tree[cnt].reset();
u = cnt;
}
else { u = tree[u].left;};
}
else if(s[i] == 'R'){
if(tree[u].right == ){
tree[u].right = ++cnt;
tree[cnt].reset();
u = cnt;
}
else u = tree[u].right;
}
}
if(tree[u].have_value) failed = true;
tree[u].v = v;
tree[u].have_value = true;
}
bool input(){
newtree();
failed = false;
for(;;){
if(scanf("%s",s) != ) return false;
if(!strcmp(s,"()")) break;
int v;
sscanf(&s[],"%d",&v);
addnode(v,strchr(s,',')+);//将逗号后的字符串传递
}
return true;
}
bool bfs(vector<int>& ans){//引用传递
queue<int> q;
q.push(root);
while(!q.empty()){
int u = q.front();
q.pop();
if(tree[u].have_value == )
return false;
ans.push_back(tree[u].v);
if(tree[u].left != ){
q.push(tree[u].left);
}
if(tree[u].right != ){
q.push(tree[u].right);
}
}
return true;
}
int main(){ while(input()){
vector<int> ans;
if(!bfs(ans) || failed)
printf("not complete\n");
else {
cout <<ans[];
int alen = ans.size();
for(int i = ; i < alen; i++){
cout << " " << ans[i];
}
puts("");
}
}
return ;
}

最新文章

  1. jQuery-1.9.1源码分析系列(八) 属性操作
  2. C2解题报告合集~
  3. Manhattan distance(for lab)
  4. ServletContextDemo
  5. 法线贴图——Normal Mapping
  6. 取消 EditText 自动聚焦弹出输入法界面
  7. weex-toolkit打包
  8. 11.Linux用户管理
  9. 编程语言 : Java的动态Web解决方案泛谈
  10. MPSOC之4——petalinux提取源码
  11. 【原创】大数据基础之Impala(3)部分调优
  12. 7. mybatis:mapper-locations: 路径放在java路径下报错:org.apache.ibatis.binding.BindingException: Invalid bound statement (not found)
  13. node学习: package.json
  14. C++中的对象初始化
  15. dumpe2fs 命令的使用,转储 ext2/ext3/ext4 文件系统信息
  16. 【Shell】总结&#183;linux shell脚本攻略
  17. Java之集合(二十五)ConcurrentHashMap
  18. pyqt4_应用例子(计算器,对话框,进度条,日历等等)
  19. Jenkins 通过ssh 拷贝文件到远程机器上。
  20. java设计模式简介

热门文章

  1. 【原创】《从0开始学Elasticsearch》—集群健康和索引管理
  2. Intellij IDEA 快捷键整理(史上最全)
  3. c语言程序设计案例教程(第2版)笔记(六)—字符串处理实例
  4. SpringMVC Model,ModelMap ModelAndView
  5. [CTSC2000]丘比特的烦恼
  6. 小心我“DIR”溢出你!
  7. [转]WF事件驱动
  8. ABP Zero最新版源码
  9. hihocoder编程练习赛52-3 部门聚会
  10. ViewPager讲解以及ViewFlipper