UVa122 Trees on the level [二叉树]

题目链接:https://vjudge.net/problem/UVA-548

数组版

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

const int maxn=300;

char str[maxn];
int failed,cnt,cans,ans[maxn];
int Left[maxn],Right[maxn],hv[maxn],v[maxn];

void ad_no(int val,char* ss){
	int len=strlen(ss),pos=1;
	for(int i=0;i<len;i++)
		if(ss[i]=='L'){
			if(Left[pos]==0)
				Left[pos]=++cnt;
			pos=Left[pos];
		}
		else  if(ss[i]=='R'){
			if(Right[pos]==0)
				Right[pos]=++cnt;
			pos=Right[pos];
		}
	if(hv[pos])  failed=1;
	v[pos]=val;
	hv[pos]=1;
}

int init(){
	memset(Left,0,sizeof Left);
	memset(Right,0,sizeof Right);
	memset(hv,0,sizeof hv);
	memset(v,0,sizeof v);
	failed=0,cnt=1;
	while(1){
		if(scanf("%s",str)!=1)  return 0;
		if(!strcmp(str,"()"))  break;
		int vv;
		sscanf(&str[1],"%d",&vv);
		ad_no(vv,strchr(str,',')+1);
	}
	return 1;
}

int bfs(){
	queue<int> q;
	cans=0;
	q.push(1);
	int pos;
	while(!q.empty()){
		pos=q.front(),q.pop();
		if(!hv[pos])  return 0;
		ans[++cans]=pos;
		if(Left[pos])  q.push(Left[pos]);
		if(Right[pos])  q.push(Right[pos]);
	}
	return 1;
}

int main(){
//	freopen("temp.in","r",stdin);
	while(init()){
		if(failed||!bfs()){
			puts("not complete");
			continue;
		}
		printf("%d",v[ans[1]]);
		for(int i=2;i<=cans;i++)
			printf(" %d",v[ans[i]]);
		putchar('\n');
	}
	return 0;
}

指针版

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

const int maxn=300;

char str[maxn];
int failed,cnt,cans,ans[maxn];
int Left[maxn],Right[maxn],hv[maxn],v[maxn];

void ad_no(int val,char* ss){
	int len=strlen(ss),pos=1;
	for(int i=0;i<len;i++)
		if(ss[i]=='L'){
			if(Left[pos]==0)
				Left[pos]=++cnt;
			pos=Left[pos];
		}
		else  if(ss[i]=='R'){
			if(Right[pos]==0)
				Right[pos]=++cnt;
			pos=Right[pos];
		}
	if(hv[pos])  failed=1;
	v[pos]=val;
	hv[pos]=1;
}

int init(){
	memset(Left,0,sizeof Left);
	memset(Right,0,sizeof Right);
	memset(hv,0,sizeof hv);
	memset(v,0,sizeof v);
	failed=0,cnt=1;
	while(1){
		if(scanf("%s",str)!=1)  return 0;
		if(!strcmp(str,"()"))  break;
		int vv;
		sscanf(&str[1],"%d",&vv);
		ad_no(vv,strchr(str,',')+1);
	}
	return 1;
}

int bfs(){
	queue<int> q;
	cans=0;
	q.push(1);
	int pos;
	while(!q.empty()){
		pos=q.front(),q.pop();
		if(!hv[pos])  return 0;
		ans[++cans]=pos;
		if(Left[pos])  q.push(Left[pos]);
		if(Right[pos])  q.push(Right[pos]);
	}
	return 1;
}

int main(){
//	freopen("temp.in","r",stdin);
	while(init()){
		if(failed||!bfs()){
			puts("not complete");
			continue;
		}
		printf("%d",v[ans[1]]);
		for(int i=2;i<=cans;i++)
			printf(" %d",v[ans[i]]);
		putchar('\n');
	}
	return 0;
}

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

您正在使用您的 WordPress.com 账号评论。 注销 /  更改 )

Google photo

您正在使用您的 Google 账号评论。 注销 /  更改 )

Twitter picture

您正在使用您的 Twitter 账号评论。 注销 /  更改 )

Facebook photo

您正在使用您的 Facebook 账号评论。 注销 /  更改 )

Connecting to %s

%d 博主赞过: