Juan Céspedes - Programas 

Problemas resueltos del Juez Online de la UVa 

Trees on the level

122.c

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

int num_nodes;
struct node {
	int init;
	int value;
	struct node * left;
	struct node * right;
} * nodes;

void
init(void)
{
	nodes = malloc(sizeof(struct node));
	num_nodes=1;
	nodes->init=0;
	nodes->left = NULL;
	nodes->right = NULL;
}

int
print_nodes(struct node * nod, int h)
{
	int a=0,b=0;

	if (h==0) {
		printf(" %d", nod->value);
		return 1;
	} else {
		if (nod->left!=NULL) {
			a = print_nodes(nod->left, h-1);
		}
		if (nod->right!=NULL) {
			b = print_nodes(nod->right, h-1);
		}
	}
	return (a || b);
}

int
recorre(struct node * nod)
{
	if (!nod) {
		return 1;
	} else if (!nod->init) {
		return 0;
	} else {
		return recorre(nod->left) && recorre(nod->right);
	}
}

void
calc(void)
{
	int i;

	if (num_nodes==1 && !nodes->init && !nodes->left && !nodes->right) {
		printf("\n");
		init();
		return;
	} else if (num_nodes==-1 || !recorre(nodes)) {
		printf("not complete\n");
		init();
		return;
	}

	printf("%d", nodes->value);
	for(i=1; print_nodes(nodes, i); i++);
	printf("\n");
	init();
}

void
add_node_1(struct node * nod, int value, char * str)
{
	struct node * tmp;

	if (!*str) {
		if (nod->init) {
			num_nodes=-1;
			return;
		}
		nod->init=1;
		nod->value=value;
		return;
	}
	if (str[0]=='L') {
		if (nod->left != NULL) {
			add_node_1(nod->left, value, str+1);
			return;
		} else {
			tmp = nod->left = malloc(sizeof(struct node));
		}
	} else {
		if (nod->right != NULL) {
			add_node_1(nod->right, value, str+1);
			return;
		} else {
			tmp = nod->right = malloc(sizeof(struct node));
		}
	}
	tmp->left = NULL;
	tmp->right = NULL;
	tmp->init = 0;
	num_nodes++;
	add_node_1(tmp, value, str+1);
}

void
add_node(int value, char * str)
{
	if (num_nodes==-1) {
		return;
	}
	add_node_1(nodes, value, str);
}

int
main(void)
{
	int i;
	char str[1024];
	char *tmp;

	init();
	while(1) {
		if (scanf("%s", str)!=1) {
			break;
		}
		if (!strcmp(str,"()")) {
			calc();
			continue;
		}
		i = strtol(str+1, NULL, 10);
		tmp = strchr(str, ',')+1;
		str[strlen(str)-1]=0;
		add_node(i, tmp);
	}

	exit(0);
}