/****************************/
/* 二分探索木               */
/*      coded by Y.Suganuma */
/****************************/
#include <stdio.h>
#include <string.h>

/********************/
/* クラスListの定義 */
/********************/
class List
{
		char *st;
		List *left, *right;

	public :
				// コンストラクタ
		List ()
		{
			st    = NULL;
			left  = NULL;
			right = NULL;
		}

		List (char *s)
		{
			left  = NULL;
			right = NULL;
			st    = new char [strlen(s)+1];
			strcpy(st, s);
		}
				// デストラクタ
		~List ()
		{
			if (st != NULL)
				delete [] st;
		}

		int add(List *);   // データの追加
		int del(char *);   // データの削除
		int search(char *);   // データの探索
		void output();   // 出力
};

/***************************************/
/* データの追加                        */
/*      dt : Listクラスのオブジェクト  */
/*      return : =1 : 追加             */
/*               =0 : 同じデータが存在 */
/***************************************/
int List::add(List *dt)
{
	List *lt = this;
	int k, sw = -1;
					// トップ
	if (lt->st == NULL) {
		lt->st = new char [strlen(dt->st)+1];
		strcpy(lt->st, dt->st);
		sw = 1;
	}
					// トップでない
	else {
		while (sw < 0) {
			k = strcmp(dt->st, lt->st);
							// 同じデータがある
			if (k == 0)
				sw = 0;
							// 大きい
			else if (k > 0) {
				if (lt->right == NULL) {
					lt->right = dt;
					sw        = 1;
				}
				else
					lt = lt->right;
			}
							// 小さい
			else {
				if (lt->left == NULL) {
					lt->left = dt;
					sw        = 1;
				}
				else
					lt = lt->left;
			}
		}
	}

	return sw;
}

/***************************************/
/* データの削除                        */
/*      st : 文字列                    */
/*      return : =1 : 削除した         */
/*               =0 : 削除できなかった */
/***************************************/
int List::del(char *st)
{
	List *lt, *lt1 = this, *lt2 = this, *dt;
	int k, rl = 0, sw = 0;

	if (lt2->st != NULL) {
		while (sw == 0 && lt2 != NULL) {
			k = strcmp(st, lt2->st);
					// 削除
			if (k == 0) {
				sw = 1;
				if (lt2->right == NULL) {
							// 子供無し
					if (lt2->left == NULL) {
						if (rl == 0)
							lt2->st = NULL;
						else {
							if (rl > 0)
								lt1->right = NULL;
							else
								lt1->left = NULL;
						}
					}
							// 右無し
					else {
						if (rl == 0) {
							lt2->st    = (lt2->left)->st;
							lt2->right = (lt2->left)->right;
							lt2->left  = (lt2->left)->left;
						}
						else {
							if (rl > 0)
								lt1->right = lt2->left;
							else
								lt1->left = lt2->left;
						}
					}
				}

				else {
							// 左無し
					if (lt2->left == NULL) {
						if (rl == 0) {
							lt2->st    = (lt2->right)->st;
							lt2->left  = (lt2->right)->left;
							lt2->right = (lt2->right)->right;
						}
						else {
							if (rl > 0)
								lt1->right = lt2->right;
							else
								lt1->left = lt2->right;
						}
					}
							// 左右あり
					else {
						dt = lt2->left;
						if (rl == 0) {
							lt         = lt2->right;
							lt2->st    = lt->st;
							lt2->right = lt->right;
							lt2->left  = lt->left;
						}
						else {
							if (rl > 0)
								lt1->right = lt2->right;
							else
								lt1->left = lt2->right;
						}
						lt1->add(dt);
					}
				}
			}
					// 次のデータ
			else {
				lt1 = lt2;
				if (k > 0) {
					lt2 = lt2->right;
					rl  = 1;
				}
				else {
					lt2 = lt2->left;
					rl  = -1;
				}
			}
		}
	}

	return sw;
}

/***********************************/
/* データの探索                    */
/*      st : 文字列                */
/*      return : =1 : 見つかった   */
/*               =0 : 見つからない */
/***********************************/
int List::search(char *st)
{
	List *lt = this;
	int k, sw = 0;

	if (lt->st != NULL) {
		while (sw == 0 && lt != NULL) {
			k = strcmp(st, lt->st);
					// 見つかった
			if (k == 0)
				sw = 1;
					// 次のデータ
			else if (k > 0)
				lt = lt->right;
			else
				lt = lt->left;
		}
	}

	return sw;
}

/**********************/
/* リストデータの出力 */
/**********************/
void List::output()
{
	List *nt = this;
					// 出力
	if (nt->st != NULL) {
		printf("%s", nt->st);
		if (nt->right != NULL)
			printf(" right %s", (nt->right)->st);
		if (nt->left != NULL)
			printf(" left %s", (nt->left)->st);
		printf("\n");
					// 次の出力
		if (nt->right != NULL)
			(nt->right)->output();
		if (nt->left != NULL)
			(nt->left)->output();
	}
}

/****************/
/* main program */
/****************/
int main ()
{
	int k, sw = 1;
	char st[100];
	List base, *lt;

	while (sw > 0) {
		printf("1:追加，2:削除，3:探索，4:出力，0:終了？ ");
		scanf("%d", &sw);
		switch (sw) {
			case 1:   // 追加
				printf("   データを入力してください ");
				scanf("%s", st);
				lt = new List(st);
				k  = base.add(lt);
				if (k > 0)
					printf("      %s を追加しました\n", st);
				else
					printf("      既に同じデータが存在します\n");
				break;
			case 2:   // 削除
				printf("   データを入力してください ");
				scanf("%s", st);
				k = base.del(st);
				if (k > 0)
					printf("      %s を削除しました\n", st);
				else
					printf("      %s を削除できませんでした\n", st);
				break;
			case 3:   // 探索
				printf("   データを入力してください ");
				scanf("%s", st);
				k = base.search(st);
				if (k > 0)
					printf("      %s が見つかりました\n", st);
				else
					printf("      %s は見つかりませんでした\n", st);
				break;
			case 4:   // 出力
				base.output();
				break;
			default :
				sw = 0;
				break;
		}
	}

	return 0;
}