当前位置: 代码迷 >> 综合 >> uva 122 Trees on the level
  详细解决方案

uva 122 Trees on the level

热度:40   发布时间:2023-12-06 08:47:03.0

题目:Trees on the level


题意:输入一棵树上的节点,形如(n,s),指从根节点经过路径s可以走到节点n。要求按bfs需输出树上的所有节点。


思路:

1、定义一个结构Node存储树上每个节点的名字和左右子节点。

2、每次读入一个字符串,拆分后添加到树中。

3、bfs遍历输出。


代码:

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<deque>
using namespace std;struct Node {int left,right;string Name;Node() {Name="";left=right=-1;}Node(string N,int one,int two) {Name=N,left=one,right=two;}
};vector<Node> vec;
bool flag;void init() {flag=true;vec.clear();vec.push_back(Node());
}bool add(string Name,string Go) {int now=0;for(int i=0; i<Go.size(); i++) {if(Go[i]=='L') {if(vec[now].left==-1) {vec.push_back(Node());vec[now].left=vec.size()-1;}now=vec[now].left;}if(Go[i]=='R') {if(vec[now].right==-1) {vec.push_back(Node());vec[now].right=vec.size()-1;}now=vec[now].right;}}if(vec[now].Name!="") return false;vec[now].Name=Name;return true;
}void bfs(){for(int i=0;i<vec.size();i++){if(vec[i].Name=="") flag=false;}if(flag==false){ printf("not complete\n");return ;}vector<int> que;int head=0;que.push_back(0);while(head<que.size()){Node x=vec[que[head]];head++;if(x.left!=-1) que.push_back(x.left);if(x.right!=-1) que.push_back(x.right);}cout<<vec[que[0]].Name;for(int i=1;i<que.size();i++){cout<<' '<<vec[que[i]].Name;}cout<<endl;return ;
}int main() {string x;init();while(cin>>x) {if(x.size()==2) {bfs();init();continue;} else {if(!flag) continue;int p=x.find(',');string Name=x.substr(1,p-1);string Go=x.substr(p+1,x.size()-Name.size()-3);flag=add(Name,Go);}}return 0;
}


  相关解决方案