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