/*
 * Binary Search Tree
 * Written by Tomokazu ARITA
 * DATE: 2002/10/01
 */



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

typedef int KEY;
typedef struct node{
	struct node *left, *right;
	KEY key;
} NODE;
static NODE *root;


/* ----------------------------------------------------
 * [ ● 初期化関数 ]
 * ---------------------------------------------------- */
void init(void){
	root = NULL;
}


/* ----------------------------------------------------
 * [ ● 探索関数 ]
 * ---------------------------------------------------- */
void search(KEY key, NODE *node){
	NODE *p;
	
	p = node;
	if(key ==  p->key){
		printf("HIT.\n");
		return;
	}else if(key <  p->key){
		if((p = p->left) != NULL){
			return search(key, p);
		}else{
			printf("NOT HIT.\n");
		}
	}else{
		if((p = p->right) != NULL){
			return search(key, p);
		}else{
			printf("NOT HIT.\n");
		}
	}
}


/* ---------------------------------------------------- 
 * [ ● 挿入関数 ]
 * ---------------------------------------------------- */
void *insert(NODE node){
	NODE **pp, *new_node;
	
	pp = &root;
	while(*pp != NULL){
		if(node.key == (*pp)->key)
			return;
		else if(node.key < (*pp)->key)
			pp = &(*pp)->left;
		else
			pp = &(*pp)->right;
	}
	
	new_node = malloc(sizeof(NODE));
	*new_node = node;
	new_node->left = new_node->right = NULL;
	*pp = new_node;
}


/* ----------------------------------------------------
 * [● 木の生成]
 * ---------------------------------------------------- */
void generate(void){
	int key;
	NODE node;
	
	init();
	printf("木を構\築します．（終了する場合は-1を入力して下さい．）\n");
	while(1){
		printf("整数値(≧0)を入力してください．");
		scanf("%d", &key);
		if(key >= 0){
			node.key = key;
			insert(node);
		}else{
			break;
		}
	}
}



/* ----------------------------------------------------
 * [ □ メイン ]
 * ---------------------------------------------------- */
int main(void){
	int key;

	generate();
	
	printf("キーを探索します．");
	printf("（終了する場合は-1を入力して下さい．）\n");
	while(1){
		printf("キーを入力してください:");
		scanf("%d", &key);
		if(key < 0) break;
		search(key, root);
	}
	return 0;
}