uva 122 树的层次遍历

#include<iostream> #include<iomanip> #include<algorithm> #include<cstdio> #include<cstdlib> #include<cmath> #include<map> #include<vector> #include<set> #include<queue> #include<cstring> using namespace std; const int maxn =256+10; char s[maxn]; struct Node { int v; bool have_value; Node* left; Node* right; Node():have_value(false),left(NULL),right(NULL) {}; }; Node* root;//根节点，使用前要申请空间 bool failed;//记录是否有误 Node* newnode() {return new Node();} 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;//标记为已经赋值 } bool readin() { failed=false; while(1) { if(scanf("%s",s)!=1) return false;//输入非正常结束 if(!strcmp(s,"()")) break;//输入正常结束 int v; sscanf(&s[1],"%d",&v);//sscanf用法：将字符串s[1]中的整数写道v中； addnode(v,strchr(s,',')+1);//strchr用法：将s中第一次找到','的地址返回； } return true; } bool bfs(vector<int>& ans) { queue<Node*> q;//借助queue进行辅助，这是核心； 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(1) { root=newnode(); if(!readin()) break; vector<int> ans;//用ans存储结果 if(!failed&&bfs(ans)) { int len=ans.size(); for(int i=0;i<len;++i) printf("%d%c",ans[i],i==len-1?'\n':' '); } else puts("not complete"); } return 0; }