[C언어] 이진 탐색트리 입력, 출력, 탐색 구현

이진 탐색트리(Binary Search Tree)의 입력, 출력, 탐색 함수를 구현해보겠습니다.

 

실행 예시

이진탐색 트리의 값을 10개 입력받고 출력, 탐색까지 구현

---

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

typedef int element;

//Binary Search Tree의 Node
typedef struct BSNode {
	element data;
	struct BSNode* llink;
	struct BSNode* rlink;
}BSNode;

//루트 노드 (n1)
typedef struct BStype{
	BSNode* root;
}BStype;

BStype* makeRootNode() {
	BStype* BS = (BStype*)malloc(sizeof(BStype));
	BS->root = NULL;	
	return BS;
}

void input(BStype* BS,element item) {
	BSNode* newNode = (BSNode*)malloc(sizeof(BSNode));
	BSNode* temp = BS->root; //
	newNode->data = item;
	newNode->llink = NULL;
	newNode->rlink = NULL;

	if (BS->root== NULL) { //첫번째로 값을 받은 경우
		BS->root = newNode;
	}
	else {
		//값을 넣을곳 탐색
		while (temp != NULL) {
			//item 의 값이 더 큰 경우(오른쪽 서브트리로 이동)
			if (temp->data < item) {
				if (temp->rlink == NULL) {
					temp->rlink=newNode;
					break;
				}
				else {
					temp = temp->rlink;
				}
			}
			//item 의 값이 작은 경우(왼쪽 서브트리로 이동)
			else if (temp->data > item) {
				if (temp->llink == NULL) {
					temp->llink = newNode;
					break;
				}
				else {
					temp = temp->llink;
				}
			}
			else{
				printf("오류:같은 값이 이미 있습니다\n");
				return;
			}
				
		}
		//새로운 노드를 연결
		newNode = temp;
	}
}

void search(BStype* BS, element item) {
	BSNode* temp = BS->root;
	while (temp != NULL) {
		if (temp->data==item) {
			printf("temp->data: %d값을 찾았습니다\n", temp->data);
			return ;
		}
		//item 값이 작은 경우
		else if (temp->data > item) {
			temp = temp->llink;
		}
		//item 값이 큰 경우
		else{
			temp = temp->rlink;
		}
	}
	printf("item(%d)값을 찾지 못했습니다",item);
}

void printBS(BStype* BS,BSNode* node) {
	int *value[10];
	int i = 0;
	if (node!=NULL) {
		printBS(BS,node->rlink);
		printf(" %d", node->data);
		printBS(BS,node->llink);
	}
}

void main() {
	BStype* BS = makeRootNode();
	int i = 0;
	element value, key = 0;
	printf("이진 탐색 트리 구현(서로 다른 정수값 10개를 입력받고 순서대로 정렬해보자)\n");

	for (i = 0; i < 10; i++) {
		printf("%d번째 루트 값을 입력하세요:", i + 1);
		scanf_s("%d", &value);
		input(BS, value);
	}		

	printf("최종 결과:");
	printBS(BS, BS->root);

	printf("\n\n(탐색 연산 실행)찾고 싶은 값을 입력하세요:");
	scanf_s("%d", &key);
	search(BS, key);

}