#include <stdio.h>

struct Node{
	int number;
	char word;
	struct Node *left;
	struct Node *right;
};


void print_indent(int width){
	while(width !=0){
		printf("     ");
		width--;
		}
}

void print_tree(struct Node *topnode, int level){
	if (topnode !=NULL){
		print_tree(topnode->left, level+1);	/*左ノードに向かう*/
		
		print_indent(level); 	/*レベル分インデント*/
		printf("%c,%d\n", topnode->word,topnode->number);/*文字と数字の表示*/
		
		print_tree(topnode->right, level+1);	/*右ノードに向かう*/
		}
	
}

struct Node *add_node(struct Node *newnode_ptr, struct Node *nownode_ptr){
	

	/*最新ノードの値が注目ノードの値より小さい場合*/
	if (newnode_ptr->number < nownode_ptr->number){
		
		if (nownode_ptr->left == NULL){
		nownode_ptr->left = newnode_ptr;
		}
		else{
		/*注目ノードを一階層下げて再帰*/
		add_node(newnode_ptr,nownode_ptr->left);
		}

	}
			/*最新ノードの値が注目ノードの値と等しい場合*/
	else if (newnode_ptr->number == nownode_ptr->number){
		printf("【同じ数字が既に登録されているため新規登録できません】\n");
	}
		/*最新ノードの値が注目ノードの値より大きいの場合*/
	else{
		
		if (nownode_ptr->right == NULL){
		nownode_ptr->right = newnode_ptr;
		}
		else{
		/*注目ノードを一階層下げて再帰*/
		add_node(newnode_ptr,nownode_ptr->right);
		}
		
	}
		return(nownode_ptr);	
}


void search_node(int num, struct Node *nownode_ptr){
	

	/*検索値が注目ノードの値より小さい場合*/
	if (num < nownode_ptr->number){

		if (nownode_ptr->left == NULL){
		printf("【入力された値は存在しませんでした】\n");
		}
		else{
		/*注目ノードを一階層下げて再帰*/
		search_node(num,nownode_ptr->left);
		}

	}
			/*検索値が注目ノードの値と等しい場合*/
	else if (num == nownode_ptr->number){
		printf("%dと関連付けられているのは%cです。\n", num, nownode_ptr->word);
	}
		/*最新ノードの値が注目ノードの値より大きいの場合*/
	else{
		
		if (nownode_ptr->right == NULL){
		printf("【入力された値は存在しませんでした】\n");
		}
		else{
		/*注目ノードを一階層下げて再帰*/
		search_node(num,nownode_ptr->right);
		}
	}
	
}

main(){
	
	/*変数の定義*/
	char newword;		/*新しい文字*/
	int newnumber;		/*新しい数字*/
	int searchnum;		/*検索する数字*/
	
	/*rootの定義*/
	struct Node *root; 
	 
	/*新しいセルを指すポインタの定義*/
	struct Node *newnode_ptr;
	
	/*rootはとりあえずNULLを指す*/
	root=NULL;
	
	
	/*--------------------*/
	/*ここより、ツリー構築*/
	/*--------------------*/
	
	printf("\n======================\n  ツリーを製作します\n======================\n");
	printf("【注意点】文字の重複は許されますが、数字の重複は禁止しています。\n\n");
	/*なぜ文字重複は許すのか→文字はツリーに無秩序に並んでいるので、一致するかどうかは
	すべてのノードをチェックする必要がある。ツリーの階層が深いとき、すべてのノードを
	チェックするのは非常に時間とメモリーを食うことになる。よってそこのチェックはしない*/
	
	while(1){
		
		
		/*zで終了してるのはわざわざ終了時も文字と数字両方打つのは面倒なので*/
		printf("\n文字（半角英字）を入力してください(小文字のzを入力すると登録終了)\n");
		scanf("%c",&newword);
		
		if(newword==122)break; /*z(アスキーコード122)が入力されたらループ脱出*/
		
		
		/*0で終了してるのはこれが次のサーチ部分の終了条件だから存在するとまずい*/
		printf("数字を入力してください(0を入力すると登録終了)\n");
		scanf("%d",&newnumber);

		if(newnumber==0)break; /*0が入力されたらループ脱出*/
	
		/*構造体変数とポインタの作成*/
		newnode_ptr=(struct Node*)malloc(sizeof(struct Node));
	
		/*作った構造体のポインタにNULLを指させておく*/
		newnode_ptr->left=NULL; newnode_ptr->right=NULL;
	
		/*新しくできた構造体変数内のcharおよびint型変数に、
		入力された値を代入する*/
		newnode_ptr->word=newword;
		newnode_ptr->number=newnumber;
	
	if (root==NULL){
		root=newnode_ptr; /*rootに今作ったノードを指させる*/
		
		}else{
		add_node(newnode_ptr,root); /*新しいノードの場所を探しに行く*/
		}
	printf("-----tree------\n\n");
	print_tree(root,0);
	
	(void)getchar();/*scanfで文字の直後にバッファリングされる\nを捨てる*/
	/*これをやらないとscanf("%c")が２回目以降確保しようとする領域に\n
	が残ってしまうので、scanfがそのまま\nを拾ってしまい、文字入力を
	受け付けようとしなくなる。ちなみに、scanf("%d")の場合バッファリング
	されている\nは無視されるので処置は必要ない。*/
	
	printf("\n====================================================\n");
	}
	
	/*--------------------*/
	/*ここより、サーチ部分*/
	/*--------------------*/
	
	if(root==NULL){ /*ツリーがまったくつくられていない場合は終了へ*/
	
	printf("値が一組も登録されてないため、検索はできません。\n");
	
	}else{
		printf("\n======================\n     検索に移ります\n======================\n");
		while(1){
			printf("\n検索する数字を入力してください(0を入力すると検索終了)\n");
			scanf("%d",&searchnum);

			if(searchnum==0)break; /*0が入力されたらループ脱出*/
			
			printf("-----tree------\n\n");
			print_tree(root,0);
			search_node(searchnum,root);
		
			printf("====================================================\n");
		}
	}
	printf("プログラムを終了させました。\n");
}