/* ispitni zadatak br 15..
Sun Jan  4 23:38:57 CET 1998
Napisati nerekurzivni program za oblikovanje i pretrazivanje sortiranog
binarnog stabla. Osim kljuca pojedninom cvoru treba biti pohranjen barem
josh jedan podatak. */

#include <stdio.h>
#include <stdlib.h>
//some typedefs
typedef struct data_type
{
	char name[14+1];
	int score;
} data;

typedef struct node_type
{
	data element;
	struct node_type *left, *right;
} node;

void fatal(char *msg)
{
	puts(msg);
	puts("exiting..");
	exit(1);
}
//non recursive creation
node *create_tree(node *head, FILE *input)
{
	data element;
	int flag=0;
	node *tmp=head=(node *)malloc(sizeof(node));
	//some init stuff
	fscanf(input, "%s %d", element.name, &element.score);
	tmp->element=element;
	tmp->left=tmp->right=NULL;
	while(fscanf(input, "%s %d", element.name, &element.score)!=EOF)
	{
		do
		{
			if (element.score>tmp->element.score)
			{
				if (tmp->right==NULL) {tmp=tmp->right=(node *)malloc(sizeof(node)); break;}
				else tmp=tmp->right; //allocate space or go right
			}
			else if (element.score<tmp->element.score)
			{
				if (tmp->left==NULL) {tmp=tmp->left=(node *)malloc(sizeof(node)); break;}
				else tmp=tmp->left; //allocate space or go left
			}
			else
			{
				flag=1; //used only for two or more identical ids
				break;
			}
		} while (1);
		if (!flag)
		{
			if (tmp==NULL) fatal ("insufficient memory");
			tmp->element=element;
			tmp->left=tmp->right=NULL;
		}
		else flag=0;
		tmp=head;
	}
	return head;
}
//recursive display
void display_tree(const node *head)
{
	if (head!=NULL)
	{
		display_tree(head->left);
		printf("%s %d\n", head->element.name, head->element.score);
		display_tree(head->right);
	}
}
//non recursive search
node *search_tree(const node *head, const int score)
{
	node *tmp=head;
	while (1)
	{
		if (tmp==NULL) return NULL;
		if (score==tmp->element.score) return tmp;
		else if (score>tmp->element.score) tmp=tmp->right;
		else if (score<tmp->element.score) tmp=tmp->left;
	}
}

void main(void)
{
	int id;
	node *head=0, *tmp;
	FILE *input=fopen("input", "rt");

	if (input==NULL) fatal("data error");
	head=create_tree(head, input);
	fclose(input);
	display_tree(head);
	puts("enter id to search for");
	scanf("%d", &id);
	tmp=search_tree(head, id);
	if (tmp==NULL) puts("not found!");
	else printf("addr %p; value %s %d\n", tmp, tmp->element.name, tmp->element.score);
}