binary_search_tree(BST).cc

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)

//이진검색트리노드
typedef struct treenode {
	int data;
	struct treenode* left;
	struct treenode* right;
}treenode;

treenode* insertnode(treenode* root, int data); //이진 검색 트리 노드추가
treenode* search(treenode* root, int data); //이진 검색 트리 노드 검색
treenode* deletenode(treenode* root, int data); //이진검색트리 삭제

void preorder(treenode* node); //전위순회
void inorder(treenode* node); //중위순회
void postorder(treenode* node); //후위순회

int all_node(treenode* node); //모든 노드 개수 찾기
int maxValue(int a, int b); //큰 값 찾기
int leaf_node(treenode* node); //단 노드 수 계산
int all_height(treenode* node); //높이 구하기

								//이진검색트리 검색
treenode* search(treenode* root, int data)
{
	while (root->data != data)
	{
		if (data < root->data) //root노드보다 작은 수인경우
			root = root->left; //왼쪽 자식으로 이동
		else if (data > root->data) //root노드보다 큰 수인경우
			root = root->right; //오른쪽 자식으로 이동
		if (root == NULL)
			return NULL;
	}

	return root;
}

//이진검색트리 삭제
treenode* deletenode(treenode* root, int data)
{
	treenode* del = root; //삭제 노드
	treenode* p = NULL; //삭제 노드의  부모 노드

	treenode* max_left = NULL; //왼쪽 서브트리 중 가장 큰 노드
	treenode* p_max_left = NULL; //max_left 부모 노드
	
	treenode* search_node = root;

	while (1)
	{
		if (search_node == NULL) //NULL인 경우-삭제 노드 못 찾은 경우
		{
			printf("삭제 노드를 찾지 못했습니다.\n");
			return root;
		}
		else if (search_node->left != NULL&&search_node->left->data == data)
			//왼쪽 자식이 삭제 노드일 경우
		{
			del = search_node->left;
			p = search_node;
			break;
		}
		else if (search_node->right != NULL&&search_node->right->data == data)
			//오른쪽 자식이 삭제 노드일 경우
		{
			del = search_node->right;
			p = search_node;
			break;
		}
		if (data < search_node->data) //root노드보다 작은 수인경우
			search_node = search_node->left; //왼쪽 자식으로 이동
		else if (data > search_node->data) //root노드보다 큰 수인경우
			search_node = search_node->right; //오른쪽 자식으로 이동
		else //root 노드가 탐색노드인 경우
			break;
	}

	//====================후속 처리 시작===========================
	if (del->right == NULL && del->left == NULL) //삭제 노드가 단노드일 경우
	{
		if (p == NULL) // 루트노드인 경우
			return NULL;
		else if (p->right != NULL && p->right == del) //오른쪽 자식노드가 삭제 노드인 경우
			p->right = NULL; //삭제 노드의 부모 노드 오른쪽 연결 해제
		else//왼쪽 자식 노드가 삭제 노드일 경우
			p->left = NULL; //삭제 노드의 부모 노드 왼쪽 연결 해제
	}

	else if ((del->right == NULL && del->left != NULL) || (del->right != NULL && del->left == NULL))
		//삭제하고자 하는 노드의 자식노드가 한개인 경우
	{
		// 루트 노드인 경우
		if (p == NULL) {
			return root->right == NULL ? root->left : root->right;
		}

		if (del->right != NULL) //오른쪽 자식이 존재하는 경우
		{
			if (p->right == del) //오른쪽 자식노드가 삭제 노드인 경우
				p->right = del->right; //삭제 노드 대신 삭제 노드의 자식 노드 연결
			else //왼쪽 자식노드가 삭제 노드인 경우
				p->left = del->right; //삭제 노드 대신 삭제 노드의 자식 노드 연결
		}
		else //왼쪽 자식이 존재하는 경우
		{
			if (p->right == del) //오른쪽 자식노드가 삭제 노드인 경우
				p->right = del->left; //삭제 노드 대신 삭제 노드의 자식 노드 연결
			else //왼쪽 자식노드가 삭제 노드인 경우
				p->left = del->left; //삭제 노드 대신 삭제 노드의 자식 노드 연결
		}
	}

	else //삭제 노드의 자식노드가 두 개인 경우
	{
		//왼쪽 자식 노드 중 최대 값 노드 대입 방법으로 구현함

		//우선 삭제 노드의 왼쪽 자식이 왼쪽 서브트리의 제일 큰 노드라고 가정
		max_left = del->left;
		p_max_left = del;

		while (max_left->right != NULL)	//max_left의 오른쪽 자식이 존재하는 경우 반복
										//왼쪽 서브트리의 가장 큰 노드 찾는 과정
		{
			p_max_left = max_left;
			max_left = max_left->right;
		}

		if (del->left == max_left)
			//삭제 노드의 왼쪽 자식이 왼쪽 서브트리의 최대 값일 경우
		{
			max_left->right = del->right;
			//최대 노드의 오른쪽 자식에 삭제 노드의 오른쪽 자식 연결
		}

		else
			//삭제 노드의 왼쪽 자식이 왼쪽 서브트리의 최대 값이 아닌 경우
		{
			p_max_left->right = max_left->left;
			//최대값 노드와 부모 노드 연결 해제 
			max_left->left = del->left;
			max_left->right = del->right;
			//최대값 노드 삭제 노드 위치에 삽입
		}

		if (p == NULL) // 루트가 삭제 노드일 경우
			root = max_left;
		else if (p->right == del) //오른쪽 자식이 삭제 노드일 경우
			p->right = max_left; //부모노드에 새로 삽입한 노드 연결
		else //왼쪽 자식이 삭제 노드일 경우
			p->left = max_left;//부모노드에 새로 삽입한 노드 연결	 
	}
	//============================================================

	free(del); //노드 삭제	
	printf("삭제하였습니다.\n");

	return root;
}

//이진트리 노드추가
treenode* insertnode(treenode* root, int data)
{
	treenode* n;
	if (root == NULL) { //트리 처음 생성하는 경우
		n = (treenode*)malloc(sizeof(treenode));
		n->data = data;
		n->left = NULL;
		n->right = NULL;
		return n;
	}
	else if (data < root->data) //root노드보다 작은 수인경우
		root->left = insertnode(root->left, data); //왼쪽 자식으로 이동
	else if (data > root->data) //root노드보다 큰 수인경우
		root->right = insertnode(root->right, data); //오른쪽 자식으로 이동
	else //data와 같은 노드인 경우
		printf("이미존재하는노드입니다.\n");

	return root;
}

//전위순회
void preorder(treenode* node)
{
	if (node == NULL) return;
	printf("%d ", node->data);
	preorder(node->left);
	preorder(node->right);
}

//중위순회
void inorder(treenode* node)
{
	if (node == NULL) return;
	inorder(node->left);
	printf("%d ", node->data);
	inorder(node->right);
}

//후위순회
void postorder(treenode* node)
{
	if (node == NULL) return;
	postorder(node->left);
	postorder(node->right);
	printf("%d ", node->data);
}

//모든 노드 개수 찾기
int all_node(treenode* node)
{
	if (node == NULL) //NULL노드인경우
		return 0; //0반환
	else //NULL노드가 아닌 경우
		return 1 + all_node(node->left) + all_node(node->right);
	//자신노드(1) + 왼쪽 자식 노드 수 + 오른쪽 자식 노드 수 
}

//큰 값 찾기
int maxValue(int a, int b)
{
	if (a > b)
		return a;
	else
		return b;
}

//단 노드 수 계산
int leaf_node(treenode* node)
{
	if (node == NULL) //NULL노드인 경우
		return 0; //0반환
	else if (node->right == NULL && node->left == NULL) //단노드인 경우
		return 1; //1반환(단노드 수 추가)
	else
		return leaf_node(node->right) + leaf_node(node->left);
	//왼쪽 자식 단 노드 수 + 오른쪽 자식 단 노드 수
}

//높이 구하기
int all_height(treenode* node)
{
	if (node == NULL) //NULL노드인 경우
		return 0; //0반환
	else //NULL노드가 아닌 경우
		return 1 + maxValue(all_height(node->left), all_height(node->right));
	//현재 노드 높이 추가(1)+왼쪽 자식의 높이와 오른쪽 자식 높이 중 높은 것
}

//메인 함수
int main()
{
	int data = 0;
	treenode* root = NULL;
	treenode* find = NULL;

	printf("==이진 탐색 트리==\n");
	printf("루트 데이터 입력 : ");
	scanf("%d", &data);
	root = insertnode(root, data);

	while (1)
	{
		printf("추가 노드 데이터 입력(종료 시 -1입력) : ");
		scanf("%d", &data);
		if (data == -1)
			break;
		insertnode(root, data);
	}

	printf("1. Preorder : "); preorder(root); printf("\n");
	printf("2. Inorder : "); inorder(root); printf("\n");
	printf("3. Postorder : "); postorder(root); printf("\n");
	printf("\n");
	printf("전체노드수: %d\n", all_node(root));
	printf("단노드수: %d\n", leaf_node(root));
	printf("트리높이: %d\n", all_height(root));
	printf("\n");

	printf("검색 하고자 하는 노드 데이터 : ");
	scanf("%d", &data);
	find = search(root, data);
	if (find == NULL)
		printf("존재하지 않는 노드입니다.\n");
	else
		printf("존재하는 노드입니다.\n");

	printf("\n");
	printf("삭제 하고자 하는 노드 데이터 : ");
	scanf("%d", &data);
	root = deletenode(root, data);

	printf("1. Preorder : "); preorder(root); printf("\n");
	printf("2. Inorder : "); inorder(root); printf("\n");
	printf("3. Postorder : "); postorder(root); printf("\n");

	printf("\n");
	printf("전체노드수: %d\n", all_node(root));
	printf("단노드수: %d\n", leaf_node(root));
	printf("트리높이: %d\n", all_height(root));

	return 0;
}

Your algorithm is nice but,
I think Line 130 p_max_left->right = NULL; isn't correct.

I think p_max_left->right = max_left->left; is correct

@sswssw81
I'm sorry. I confirmed the comment today.
You are right. 👍

If delete NODE 28 from the BST created with "15 28 25 36 24 27 26 36 30 39" input, the child NODE 26 of NODE 27 replaced at the delete node position is deleted.

I modified the code. Thank you for your help. :)