[C언어] 이진탐색트리의 삽입,삭제,탐색,출력 연산 함수 구현하기(Binary Search Tree)

 

안녕하세요. 

오늘은 이진탐색트리에서 출력, 삽입, 삭제, 검색 함수를 구현해보겠습니다.

 

(예시)

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

typedef char element;

typedef struct treeNode {
	char key;
	struct treeNode* left;
	struct treeNode* right;
}treeNode;

//serachBST함수:root에서 x의 값을 찾아서 그 위치를 반환하기때문에 treeNode*를 반환한다
treeNode* searchBST(treeNode* root, char x) {
	treeNode* p;
	p = root;
	while (p != NULL) {
		if (x < p->key) p = p->left;
		else if (x == p->key) return p;
		else p = p->right; //x>p->key 인 경우
	}
	printf("[ 찾는 값이 없습니다 ]\n");
	return p;
}

treeNode* insertNode(treeNode* p, char x) {
	treeNode* newNode;
	
	if (p == NULL) { //p가 첫번째로 온 경우
		newNode = (treeNode*)malloc(sizeof(treeNode));
		newNode->key = x;
		newNode->left = NULL;
		newNode->right = NULL;
		return newNode;
	}
	else if (x < p->key) p->left = insertNode(p->left, x);
	else if (x > p->key) p->right = insertNode(p->right, x);
	else printf("[ 넣을려는 값과 같은 값이 이미 있습니다 ]\n");

	return p;
}

void deleteNode(treeNode* root, element key) {
	treeNode* parent, * p, * succ, * succ_parent;
	treeNode* child;
	parent = NULL;
	p = root;
	while ((p != NULL) && (p->key != key)) {
		parent = p;
		if (key < p->key) p = p->left;
		else p = p->right;
	}

	if (p == NULL) {
		printf("[ 삭제하려는 키가 이진트리에 없습니다] \n");
	}
	if ((p->left == NULL) && (p->right == NULL)) { //지울려는 값 p 가 단말 노드인 경우
		if (parent != NULL) {
			if (parent->left == p) parent->left = NULL;  //p가 parent의 왼쪽에 달려있는 경우
			else parent->right = NULL; //p가 parent의 오른쪽에 달려있는 경우
		}
		else { //parent==NULL 인경우 
			root = NULL;
		}
	}
	else if ((p->left == NULL) || (p->right == NULL)) {//지울려는 값 p의 차수가 1인 경우
		if (p->left != NULL) child = p->left;
		else child = p->right;

		if (parent != NULL) {
			if (parent->left == p) parent->left = child;
			else parent->right = child;
		}
		else root = child;
	}
	else {//지울려는 값 p의 차수가 2인 경우
		succ_parent = p;
		succ = p->left;
		while (succ->right != NULL) { //왼쪽 서브트리에서 가장 큰값 찾기
			succ_parent = succ;
			succ = succ->right;
		}

		if (succ_parent->left == succ) succ_parent->left = succ->left;
		else succ_parent->right = succ->left;

		p ->key = succ->key;
		p = succ;
	}
	free(p);
}


void displayInorder(treeNode* root) {
	if (root) {
		displayInorder(root->left);
		printf("%c", root->key);
		displayInorder(root->right);
	}
}

void menu() {
	printf("\n========================\n");
	printf("\nt1:트리 출력 \n");
	printf("t2:문자 삽입 \n");
	printf("t3:문자 삭제 \n");
	printf("t4:문자 검색 \n");
	printf("t5:종료 \n");
	printf("\n========================\n");
}

int main() {
	treeNode* root = NULL;
	treeNode* foundedNode = NULL;

	char choice, key;
	root = insertNode(root, 'G');
	insertNode(root, 'I');
	insertNode(root, 'H');
	insertNode(root, 'D');
	insertNode(root, 'B');
	insertNode(root, 'M');
	insertNode(root, 'N');
	insertNode(root, 'A');
	insertNode(root, 'J');
	insertNode(root, 'E');
	insertNode(root, 'Q');

	while (1) {
		printf("<메뉴에서 항목을 선택해주세요>");
		menu();
		scanf_s("%c", &choice);
		getchar();

		switch (choice - '0') {
		case 1:
			printf("\n1. 이진 트리 출력(중위 순환) : ");
			displayInorder(root);
			printf("\n\n");
			break;
		case 2:
			printf("\n2. 삽입할 문자를 입력해주세요");
			scanf_s("%c", &key);
			getchar();
			insertNode(root, key);
			break;
		case 3:
			printf("\n3. 삭제할 문자를 입력해주세요");
			scanf_s("%c", &key);
			getchar();
			deleteNode(root, key);
			break;
		case 4:
			printf("\n4. 탐색할 문자를 입력해주세요");
			scanf_s("%c", &key);
			getchar();
			foundedNode = searchBST(root, key);
			if (foundedNode != NULL)printf("\n [ %c를 찾았습니다 ]\n", foundedNode->key);
			else printf(" 탐색을 실패하였습니다 ");
			break;
		case 5:
			return 0;
		}
	}
}