UVA122 树的层次遍历 Trees on the level
程序员文章站
2022-03-11 20:58:35
...
题目描述
输入格式
输出格式
输入
(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()
输出
5 4 8 11 13 4 7 2 1
not complete
#include<bits/stdc++.h>
#define read() freopen("input.txt","r",stdin);
#define write() freopen("output.txt","w",stdout);
using namespace std;
const int maxn = 105;
struct node{
bool have_value;
int v;
node* left,* right;
node():have_value(false),v(0),left(NULL),right(NULL){}
};
void remove_tree(node *p) {
if(p == NULL) return ;
remove_tree(p->left);
remove_tree(p->right);
delete p;
}
node* newnode(){ return new node();}
node* root;
bool failed;
void addnode(int v,char* s){
int n=strlen(s);
node* u=root;
for( int i=0; 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;
}
char s[maxn];
bool readinput(){
failed=false;
remove_tree(root);
root=newnode();
for(;;){
if(scanf("%s",s)!=1) return false;
if(!strcmp(s,"()")) break;
int v;
sscanf(&s[1],"%d",&v);
addnode(v,strchr(s,',')+1);
}
return true;
}
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;
}
vector<int>ans;
int main()
{
read();write();
while(readinput()) {
if(failed || !bfs(ans)) {
printf("not complete");
}else {
for( int i=0; i<ans.size(); i++ ){
if(i) printf(" ");printf("%d",ans[i]);
}
}
printf("\n");
}
return 0;
}
上一篇: HTML5程序员需要学习的技能总结
下一篇: url完整结构以及同源跨域处理的介绍