이진 탐색트리_ 탐색, 삽입, 삭제, 전위순회

외부노드라는 개념을 이용해서 만들었음.

노드에 값이 들어있는 것들을 내부노드, 노드에 key값도 없고 자식도 없는 것들을 외부노드.

단말 내부노드에는 자식이 없는 경우에 외부노드를 붙여 놓았음.

논리 짠 부분은 A4용지에 적어놔서 스캔해서 올리기

//이진탐색트리 탐색,삽입,제거,순회

#include 
#include 

typedef struct Node{
	struct Node* P;
	struct Node* L;
	struct Node* R;
	int key;
}NODE;

typedef struct Tree{
	NODE* Root;
}TREE;

NODE* makeNode(NODE* parent ,int k)
{
	NODE* node = (NODE*)malloc(sizeof(NODE));

	node->P = parent;
	node->key = k;
	node->L =NULL;
	node->R =NULL;

	return node;
}

TREE* initTree()
{
	TREE* T = (TREE*)malloc(sizeof(TREE));

	T->Root = makeNode(NULL, NULL);

	return T;
}

NODE* findElement(TREE* t,int k) ;
void insert(TREE* t, int k);
void remove(TREE* t, int k);
NODE* inOrderSucc(NODE* n);
void preOrder(NODE* n);

void main()
{
	
	char st = NULL;
	int k;
	
	TREE* t = initTree();

	NODE* temp = NULL;

	while(st!='q')
	{
		scanf("%c", &st);

		switch (st)
		{
		case 'i':
			scanf("%d", &k);
			insert(t,k);
			break;

		case 'd':
			scanf("%d", &k);
			remove(t,k);
			break;

		case 's' :
			scanf("%d", &k);
			temp = findElement(t,k);
			if(temp->key == NULL)
				printf("X\n");
			else
				printf("%d\n", temp->key);
			break;

		case 'p':
			preOrder(t->Root);
			printf("\n");
			break;

		case 'q':
			st = 'q';
			break;
		}
	}

}


NODE* findElement(TREE* t,int k)        //찾으면 해당노드 반환, 못찾으면 NULL;
{
	NODE* finger;
	finger = t->Root;

	while( finger->key != k && finger->key!=NULL) //멈추는 경우 key = k인 경우 또는 key=NULL인 경우(즉 외부노드인 경우)
	{
		if(finger->key>k)
			finger= finger->L;
		else if(finger->keyR;
	}
	
	return finger;       //사용할 때  노드 자체가 NULL인 경우가 있으니 함부로 노드의 키에 접근하지 않도록
}

//문제 find에서  NULL이 반환되면 해당 위치에 값을 넣는 게 곤란데스요
// 1. 외부노드 개념 적용시키면 해결됨 // 1선택
// 2. 다른거?

void insert(TREE* t, int k)  //삽입시 주의 사항: root에 들어가는 경우, 외부노드 만들기
{
	NODE* a;
	a = findElement(t,k);

	if(a->key == k)
		printf("already have it\n");
	else // a->key가 NULL 즉 외부노드임
	{	
		a->key = k;
		//외부노드 만들어줌
		a->L = makeNode(a,NULL); 
		a->R = makeNode(a,NULL);
	}
}

void remove(TREE* t, int k)
{
	NODE* a;
	a = findElement(t,k);
	NODE* suc = NULL;
	NODE* temp = NULL;

	if(a->key != k)      //입력받은 k가 트리에 없다.
	{
		printf("X\n");
		return;
	}
	else               //k 존재하고 삭제할 때 삭제될 노드가 가지는 경우의 수들 4가지
	{
		printf("%d\n", a->key);

		if(a->L->key!=NULL && a->R->key != NULL)    //자식들이 모두 외부노드가 아님
		{
			suc = inOrderSucc(a);      //중위순회로 다음 바꿔줄 노드의 위치를 찾고

			a->key = suc->key;

			//이제 suc부분을 제거해줘야함
			free(suc->L);
			//-----------------빼먹은 부분 - 부모노드에서 새로 바뀐 자식으로 이어줘야함
			if(suc->P->L == suc)
				suc->P->L = suc->R;
			else
				suc->P->R = suc->R;

			temp = suc->P;
			suc = suc->R; 
			suc->P = temp;
			/*
			suc->key = suc->R->key;
			suc->L = suc->R->L;

			*/
		}
		else if(a->L->key!=NULL && a->L->key == NULL)  //왼쪽은 내부, 오른쪽 자식이 외부노드
		{
			free(a->R);

			if(a->P->L == a)
				a->P->L == a->L;
			else
				a->P->R == a->L;
			//a노드를 왼쪽자식으로 대체해주고 기존 a노드의 부모에게 이어붙임
			temp = a->P;
			a = a->L;       
			a->P = temp;
		}
		else                //왼쪽자식이 외부노드인 경우(오른쪽 노드는 외부일수도 아닐수도)
		{
			free(a->L);

			if(a->P->L == a)
				a->P->L == a->R;
			else
				a->P->R == a->R;
			
			temp = a->P;
			a = a->R;
			a->P = temp;
		}
	}
}


NODE* inOrderSucc(NODE* n)
{
	n = n->R;
	while(n->L->key != NULL)
	{
		n = n->L;
	}
	return n;
}

void preOrder(NODE* n)
{
	printf(" %d",n->key);
	if(n->L->key != NULL)
		preOrder(n->L);
	if(n->R->key != NULL)
		preOrder(n->R);
}