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

题目链接:

https://cn.vjudge.net/problem/UVA-122

 /*
问题
给出每个节点的权值和路线,输出该二叉树的层次遍历序列。 解题思路
根据输入构建链式二叉树,再用广度优先遍历保存权值最后输出。
*/
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=;
bool failed; struct NODE{
bool have_value;
int v;
NODE *left,*right;
NODE() : have_value(false),left(NULL),right(NULL){};
};
NODE* newnode(){
return new NODE();
}
NODE* root; bool read_input();
void addnode(int v,char *s);
bool bfs(vector<int> &ans);
void remove_tree(NODE* u){
if(u == NULL) return;
remove_tree(u->left);
remove_tree(u->right);
delete u;
} int main()
{
//freopen("E:\\testin.txt","r",stdin);
vector<int> ans;
while(read_input()){
if(failed || !bfs(ans))
printf("not complete\n");
else{
int i;
for(i=;i<ans.size()-;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[i]);
}
}
return ;
} 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;
}
void addnode(int v,char *s){
int len=strlen(s); NODE* u= root;
for(int i=;i<len;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(){
char s[maxn];
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;
}
上一篇:关于click的多次触发问题(冒泡事件)


下一篇:数论 - Pairs(数字对)