现在的位置: 首页 > 综合 > 正文

UVA112

2018年04月05日 ⁄ 综合 ⁄ 共 3220字 ⁄ 字号 评论关闭

链式的二叉树,注意0 ():

#include<stdio.h>
#include<stdlib.h>

struct Node{
	int v;
	struct Node * l;
	struct Node * f;
	struct Node * r;
};

int t,e1,e2,isfind = 0;
struct Node * root = NULL;
struct Node head = {0,NULL,NULL,NULL};

struct Node * Cset(struct Node * fa){
	struct Node * p = (struct Node *)malloc(sizeof(struct Node));
	p ->v = 0;
	p ->f = fa;
	p ->r = NULL;
	p ->l = NULL;
	return p;
}

struct Node * CreatT(){
	int i = 0,cnt = 0,f = 1,val = 0;
	int flag = 0,k = 0;
	char ch,lc = '(',c = '(';
	struct Node * p = &head;
	head.v = 0;
	head.f = head.l = head.r = NULL;
	do
	{
		scanf("%c",&ch);
		if(ch == '(' || ch == ')' || ch == '-' || (ch >= '0' && ch <= '9')){
			if(ch == '('){
				cnt++;
				if(flag){
					p ->v = val * f;
					val = 0;
					f = 1;
					flag = 0;
				}
				if(lc == '('){
					p ->l = Cset(p);
					p = p ->l;
					k = 0;
				}
				else {
					p ->r = Cset(p);
					p = p ->r;
					k = 1;
				}
				lc = ch;
			}
			else if(ch == ')'){
				cnt--;
				p = p ->f;
				if(c == '(' && k == 0){
					free(p ->l);
					p ->l = NULL;
				}
				if(c == '(' && k == 1){
					free(p ->r);
					p ->r = NULL;
				}
				lc = ch;
			}
			else if(ch >= '0' && ch <= '9'){
				val = val * 10 + (ch - '0');
				flag = 1;
			}
			else if(ch == '-'){
				f = -1;
			}
			c = ch;
		}
	}while(cnt);

	return &head;
}

int dfs(struct Node * p,int path_l){
	if(!isfind){
		if(p == NULL)return 1;
		else {
			path_l += p->v;
			e1 = dfs(p->l,path_l);
			e2 = dfs(p->r,path_l);
			if(e1 && e2 && t == path_l){
				isfind = 1;
			}
			return 0;
		}
	}
	return 1;
}

void destoryT(struct Node * p){
	if(p == NULL)return;
	destoryT(p->l);
	destoryT(p->r);
	free(p);
	return;
}

int main(void){
	while(scanf("%d",&t) != EOF){
		getchar();
		isfind = 0;
		root = CreatT();
		dfs(root->l,0);
		printf("%s\n",isfind ? "yes" : "no");
		destoryT(root->l);
	}
	return 0;
}

直接递归的方法:

 

#include<stdio.h>
#include<string.h>

#define Max 10000

char buffer[Max] = {'\0'};
int p = 0,t,e1,e2,isfind = 0;
char si;

char readc(){
	return buffer[p++];
}

int isdig(){
	char ch = buffer[p];
	if(ch == '-' || (ch >= '0' && ch <= '9'))return 1;
	else return 0;
}

int readn(){
	int f = 1,val = 0;
	if(buffer[p] == '-'){
		f = -1;
		p ++;
	}
	while(buffer[p] <= '9' && buffer[p] >= '0')
		val = val * 10 + (buffer[p++] - '0');
	val *= f;
	return val;
}

void input(){
	int cnt = 0;
	char ch,* ptr = buffer;
	do
	{
		scanf("%c",&ch);
		if(ch == '(' || ch == ')' || ch == '-' || (ch >= '0' && ch <= '9')){
			(*ptr++) = ch;
			if(ch == '(')cnt++;
			else if(ch == ')')cnt--;
		}
	}while(cnt);
}

int dfs(int path){ 
	if(!isfind){
		si = readc();
		if(isdig()){
			path += readn();
			e1 = dfs(path);
			e2 = dfs(path);
			if(e1 && e2 && path == t)
				isfind = 1;
			si = readc();
			return 0;
		}
		else{
			si = readc();
			return 1;
		}
	}
	return 0;
}
int main(void){
	while(scanf("%d",&t) != EOF){
		isfind = p = 0;
		getchar();
		input();
		dfs(0);
		printf("%s\n",isfind ? "yes" : "no");
	}
	return 0;
}

poj可以过的二叉堆:

#include<stdio.h>
#include<string.h>

#define Max 1000000
#define Left(n) (2*(n))
#define Right(n) (2*(n)+1)
#define Father(n) (n/2)

int node,t,isfind = 0;
int e1,e2,Max_lf = 0;
int Tree[Max] = {0};
int sign[Max] = {0};

void csigned(int k,int * fl,int * f){
	Tree[k] = (*f) * Tree[k];
	(*fl) = 0;
	(*f) = 1;
}

void slove(){
	int cnt = 0,i = 0,f = 1,flag = 0,k = 1;
	char ch,lc = '(';
	do
	{
		scanf("%c",&ch);
		if(ch == '(' || ch == ')' || (ch >= '0' && ch <= '9') || ch == '-'){	
			if(ch == '('){
				cnt++;
				if(!i)continue;
				if(flag)csigned(k,&flag,&f);
				if(lc == ')')k = Right(k);
				else if(lc == '(')k = Left(k);
				lc = ch;
			}
			else if(ch == ')'){
				cnt--;
				if(flag)csigned(k,&flag,&f);
				k = Father(k);
				lc = ch;
			}
			else if(ch >= '0' && ch <= '9'){
				Tree[k] = Tree[k] * 10 + (ch - '0');
				sign[k] = 1; 
				i = k;
				flag = 1;
			}
			else if(ch == '-'){
				f = - 1;
			}
		}
	}while(cnt);
	Max_lf = i;
}

int dfs(int n,int path_l){
	if(!isfind){
		if(!sign[n])return 1;
		else {
			path_l += Tree[n];
			e1 = dfs(Left(n),path_l);
			if(isfind)return 0;
			e2 = dfs(Right(n),path_l);
			if(isfind)return 0;
			if(e1 && e2 && t == path_l){
				isfind = 1;
			}
			sign[n] = 0;
			Tree[n] = 0;
			return 0;
		}
	}
	return 0;
}

int main(void){
	while(scanf("%d",&t) != EOF){
		isfind = 0;
		memset(sign,0,sizeof(int) * (Max_lf + 1));
		memset(Tree,0,sizeof(int) * (Max_lf + 1));
		getchar();
		slove();
		dfs(1,0);
		printf("%s\n",isfind ? "yes" : "no");
	}
	return 0;
}

 

抱歉!评论已关闭.