[자료구조] 이원탐색트리 (이진탐색트리) 코드

=연결리스트를 이용한 다항식연산=
채진석교수님 강의 - 자료구조 2학년 1학기 코딩과제

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

typedef struct treeNode *node_t;

struct treeNode {
	int key;
	node_t left;
	node_t right;
};

node_t B = NULL;

node_t insertBST(node_t B, int key);
node_t deleteBST(node_t B, int key);
node_t searchBST(node_t B, int key, node_t *parent);
node_t maxNode(node_t B);
node_t minNode(node_t B);

void printBST(node_t B);

node_t insertBST(node_t B, int x)
{
	node_t p, parent;
	node_t newNode;
	p = searchBST(B, x, &parent);
	if ( p != NULL ) {
		printf("\n중복된 키 값이 있음.\n\n");
		return B;
	}
	newNode = (node_t)malloc(sizeof(struct treeNode));
	newNode->key = x;
	newNode->right = NULL;
	newNode->left = NULL;
	if ( B == NULL ) B = newNode;
	else if ( x < parent->key ) parent->left = newNode;
	else parent->right = newNode;
	return B;
}

node_t deleteBST(node_t B, int x)
{
	node_t p, q, parent;
	p = searchBST(B, x, &parent);	
	if ( p == NULL ) {
		printf("\n삭제할 원소 탐색되지 않음.\n\n");
		return B;
	}
	else if ( parent == NULL ) {
		if ( p->left == NULL && p->right == NULL ) {
			if ( p == B ) {
				B = NULL;
				B->left = NULL;
				B->right = NULL;
				return B;
			}			
		}
		else if ( p->right == NULL && p->left != NULL ) {
			q = maxNode(p->left);
			p->key = q->key;
			if ( p->left == q && q->left == NULL && q->right == NULL ) {
				p->left = NULL;
			}
			else deleteBST(p->left, p->key);
		}
		else if ( p->left == NULL && p->right != NULL ) {
			q = minNode(p->right);
			p->key = q->key;
			if ( p->right == q && q->left == NULL && q->right == NULL ) {
				p->right = NULL;
			}
			else deleteBST(p->right, p->key);
		}
		else if ( p->left != NULL && p->right != NULL ) {			
			q = maxNode(p->left);
			p->key = q->key;
			if ( p->left == q && q->left == NULL && q->right == NULL ) {
				p->left = NULL;
			}
			else deleteBST(p->left, p->key);
		}
	}
	else { 	
		if ( p->left == NULL && p->right == NULL ) {			
			if ( parent->left == p ) parent->left = NULL;
			else parent->right = NULL;
		}
		else if ( p->left == NULL || p->right == NULL ) {
			if ( p->left != NULL ) {
				if ( parent->left == p ) parent->left = p->left;
				else parent->right = p->left;
			}
			else {
				if ( parent->left == p ) parent->left = p->right;
				else parent->right = p->right;
			}
		}
		else if ( p->left != NULL && p->right != NULL ) {
			q = maxNode(p->left);
			p->key = q->key;
			deleteBST(p->left, p->key);
		}
		return B;
	}
}

node_t searchBST(node_t B, int key, node_t *parent)
{
	node_t p;
	p = B;	
	*parent = NULL;
	if ( p == NULL ) return p;
	while ( p != NULL ) {
		if ( key == p->key ) return p;
		*parent = p;	// 찾을 키값을 가진 노드의 부모노드
		if ( key < p->key ) p = p->left;
		else p = p->right;
	}
	return p;
}

node_t maxNode(node_t B)
{	// 왼쪽 서브트리의 최대원소를 리턴
	node_t p;
	p = B;
	if ( p == NULL ) return p;
	else if ( p->right == NULL ) return p;
	else {
		while ( p->right != NULL ) {
			p = p->right;
		}
		return p;
	}
}


node_t minNode(node_t B)
{	// 오른쪽 서브트리의 최대원소를 리턴
	node_t p;
	p = B;
	if ( p == NULL ) return p;
	else if ( p->left == NULL ) return p;
	else {
		while ( p->left != NULL ) {
			p = p->left;
		}
		return p;
	}
}

void printBST(node_t p) {
	if (p != NULL)
	{
		printf("(");
		printBST(p->left);
		printf ("%d", p->key);
		printBST(p->right);
		printf(")");
	}
}

int main()
{
	int menu = 0;
	int key;
	node_t p;
	node_t parent;
	while (menu != 9) {
		printf("\n이진 탐색 트리 연산\n\n");
		printf("1. 삽입\n");
		printf("2. 삭제\n");
		printf("3. 탐색\n");
		printf("9. 종료\n\n");
		printf("선택 : ");
		scanf("%d", &menu);
		switch(menu) {
		case 1 : 
			printf("\n삽입할 원소값 : ");
			scanf("%d", &key);
			B = insertBST(B, key);
			printf("\n");
			printBST(B);
			printf("\n");
			break;
		case 2 :
			printf("\n삭제할 원소값 : ");
			scanf("%d", &key);
			B = deleteBST(B, key);
			printf("\n");
			printBST(B);
			printf("\n");
			break;
		case 3 :
			printf("\n탐색할 원소값 : ");
			scanf("%d", &key);
			p = searchBST(B, key, &p);
			if ( p == NULL ) printf("\n원소 %d 탐색되지 않음.\n", key);
			else printf("\n원소 %d 탐색됨.\n", key);
			break;
		case 9 :
			printf("\n프로그램 종료\n");
			break;
		default :
			printf("\n잘못 선택함\n");
		}
	}
	getch();
	return 0;
}