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

typedef struct btree{
	int data;
	struct btree *left;
	struct btree *right;
} TREE;

TREE *new_bt(int x, TREE *y, TREE *z);
TREE *find_bt(int x, TREE *y);
TREE *insert_bt(int x, TREE *y);
TREE *delete_bt(int x, TREE *y);
void display_bt(TREE *y);

TREE *root;
int non=0,i=0,j;

void main(){
	int a,add,del;
	root=NULL;

	while(1){

		printf("\n\n    ┌--------------------┐\n");
		printf("    │                    │\n");
		printf("    │     コマンド       │\n");
		printf("    │                    │\n");
		printf("    │  0 : 二分木の表示  │\n");
		printf("    │  1 : 数値の追加    │\n");
		printf("    │  2 : 数値の削除    │\n");
		printf("    │                    │\n");
		printf("    └--------------------┘\n\nｺﾏﾝﾄﾞ>");

		scanf("%d",&a);

		if(a==0){
			display_bt(root);

		}else if(a==1){

			printf("\n追加する数字は？\n\n");
			scanf("%d",&add);
			root=insert_bt(add,root);
			printf("\n%d を追加しました！",add);

		}else if(a==2){

			printf("\n削除する数字は？\n\n");
			scanf("%d",&del);
			delete_bt(del,root);
			if(non==0){
				printf("\n%d を削除しました！\n\n",del);
			}else if(non==1){
				printf("\nその数字は二分木上に存在しません！");
				non=0;
			}

		}

	}
}

TREE *new_bt(int x, TREE *y, TREE *z){

	TREE *w = (TREE *)malloc(sizeof(TREE));

	w->data = x;
	w->left = y;
	w->right = z;

	return w;

}

TREE *find_bt(int x, TREE *y){

	while (y!=NULL && x!= y->data){
		if (x < y->data) y = y->left;
		else y = y->right;
	}

	return y;

}


TREE *insert_bt(int x, TREE *y){
	TREE* node = y;

	/* NULLが渡された場合 */
	if(y==NULL){
		return new_bt(x, NULL, NULL);
	}
	/* xが入る位置を探して挿入 */
	/* nodeを終了フラグ代わりに使っている */
	while(node != NULL){
		if(x < node->data){
			if(node->left != NULL){
				node = node->left;
			}else{
				node->left = new_bt(x, NULL, NULL);
				node = NULL;
			}
		}else{
			if(node->right != NULL){
				node = node->right;
			}else{
				node->right = new_bt(x, NULL, NULL);
				node = NULL;
			}
		}
	}
	return y;
}

/* 部分木を再接続する関数 */
TREE *reconnect_bt(TREE* x, TREE* y){
	TREE* node = y;

	/* NULLが渡された場合 */
	if(x==NULL){ return y; }
	if(y==NULL){ return x; }
	/* xが入る位置を探して挿入 */
	/* nodeを終了フラグ代わりに使っている */
	while(node != NULL){
		if(x->data < node->data){
			if(node->left != NULL){
				node = node->left;
			}else{
				node->left = x;
				node = NULL;
			}
		}else{
			if(node->right != NULL){
				node = node->right;
			}else{
				node->right = x;
				node = NULL;
			}
		}
	}
	return y;
}


TREE *delete_bt(int x,TREE *y){
	/* 削除するノードの親 */
	TREE* parent = NULL;
	/* 削除するノード */
	TREE* target = y;

	non = 0;

	/* まず、削除するノードを探す */
	while(target != NULL && target->data != x){
		parent = target;
		if (x < target->data) target = target->left;
		else target = target->right;
	}
	/* ノードがなければグローバル変数 non = 1にして終了 */
	if(target == NULL){
		non = 1;
		return y;
	}

	/* ノードのつなぎ換え */
	if(parent == NULL){
		/* ルートを削除する場合。
		 * rootの値を変えないといけないので
		 * グローバル変数を書き換える
		 */
		root = reconnect_bt(root->right, root->left);
		/* 返すべき値はroot */
		y = root;
	}else{
		/* それ以外の場合 */
		/* 親から切り離す */
		if(parent->left && parent->left->data == target->data) parent->left = NULL;
		else parent->right = NULL;
		/* 子を親にくっつける */
		reconnect_bt(target->left, parent);
		reconnect_bt(target->right, parent);
	}

	/* 削除対象の解放 */
	free(target);
	return y;
}


void display_bt(TREE *y){

	i++;

	if(y==NULL){
		i--;
		return;
	}

	display_bt(y->right);

	j=i;
	while(j>1){
		printf("………");
		j--;
	}

	printf("%i\n", y->data);

	display_bt(y->left);

	i--;

}