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

struct node{
	int val;
	struct node * lnext;
	struct node * rnext;
};

void insert(struct node * target, int newval)
{
	struct node * newnode = (struct node *)malloc(sizeof(struct node));
	int lr=0;
	newnode->lnext=NULL,newnode->rnext=NULL,newnode->val=newval;
	while(1)
	{
		if(target->val>=newval)
		{
			if(target->lnext==NULL)
			{
				lr=-1;
				break;
			}
			target=target->lnext;
		}
		else
		{
			if(target->rnext==NULL)
			{
				lr=1;
				break;
			}
			target=target->rnext;
		}
	}
	if(lr==-1) target->lnext=newnode;
	else target->rnext=newnode;
}

int del(struct node * target, int find)
{
	struct node * tlnode;
	struct node *trnode;
	struct node * ta;
	while(1)
	{
		if(target->val>find)
		{
			if(target->lnext==NULL) return 0;
			target=target->lnext;
		}
		else if(target->val<find)
		{
			if(target->rnext==NULL) return 0;
			target=target->rnext;
		}
		else if(target->val==find) break;
		else return 0;
	}
	tlnode=target->lnext;
	trnode=target->rnext;
	ta=target;
	if(target->rnext==NULL)
	{
		if(target->lnext==NULL)
		{
			free(ta);
			return 1;
		}
		else target=tlnode;
	}
	else
	{
		target=trnode;
		while(target->lnext!=NULL)
			target=target->lnext;
		tlnode=target;
	}
	ta->lnext=NULL,ta->rnext=NULL;
	free(ta);
	return 1;
}

int main()
{
	struct node * head=(struct node *)malloc(sizeof(struct node));
	int ind,t;
	char ch[10],a;
	printf("초기값 설정 ㄱㄱ : ");
	scanf("%d",&ind);
	head->val=ind;
	head->lnext=NULL;
	head->rnext=NULL;
	while(1)
	{
		printf("\ninsert(i)나 delete(d)나 exit(e)를 입력하세요 : ");
		scanf("%s",ch);
		a=ch[0];
		if(a=='I' || a=='i')
		{
			printf("머 집어넣을꺼임? : ");
			scanf("%d",&ind);
			insert(head,ind);
		}
		else if(a=='D' || a=='d')
		{
				printf("머 뺄꺼임? : ");
				scanf("%d",&ind);
				if(del(head,ind)) printf("잘 빼짐\n");
				else printf("값 없어\n");
		}
		else if(a=='E' || a=='e') break;
		else printf("제대로 입력하라고\n");
	}
	return 0;
}