Binary Search Tree

다음과 같이 임의의 노드 n개로 구성된 이진탐색트리(binary search tree)를 생성하여 아래와 같이 실행하도록 프로그램을 작성하라.

 

난수생성을 위한 seed와 이진탐색트리의 노드 개수(n)를 입력받음

printf("random number generation (1 ~ %d)\n", MAX_SIZE);
printf("%s", "the number of nodes in BST (less than and equal to 50) : ");
scanf_s("%d", &n);
printf("%s", "seed : ");
scanf_s("%u", &seed);
printf("\ncreating a BST from random numbers\n");
srand(seed);

 

1~500 범위의 난수를 생성하여 노드의 key와 item 필드 값으로 동일하게 사용(키값과 항 목 값이 같음), 난수가 발생 되는 순서대로 출력 할 것(이진탐색트리의 key 값은 중복이 허용되지 않음을 주의, 난수발생 순서대로 노드를 추가해야 함)

 

탐색할 key를 입력받아서 이진탐색하여 그 결과를 출력한다. 탐색과정을 출력하시오.

 

이진탐색트리를 구성하고 있는 노드의 key값을 오름차순으로 정렬되도록 출력함(inorder traversal 사용)

 

Result

#include <stdio.h>
#include <Stdlib.h>
#include <stdbool.h>

enum {
	FILE_OPEN_ERROR, MEMORY_ALLOCATION_ERROR
};

#define NAME(a) #a
#define CATCH(ERROR) do{printf(NAME(ERROR));exit(0);}while(false)
#define CALLOC(type,data_num,ptr) do{if(!(ptr=(type*)calloc(data_num,sizeof(type)))){CATCH(MEMORY_ALLOCATION_ERROR);}}while(false)

typedef struct node* link;
typedef struct node {
	link l_ch;
	int key;
	link r_ch;
} node;
link root;

#define MAX_SIZE 500
#define RAND (rand() % MAX_SIZE + 1)

int n, seed;

link modified_search(int key);
bool add_node(int key);
void  make_BST(void);

void search(int key);

void inorder(link ptr);

int main(void)
{
	printf("random number generation (1 ~ %d)\n", MAX_SIZE);
	printf("%s", "the number of nodes in BST (less than and equal to 50) : ");
	scanf_s("%d", &n);
	printf("%s", "seed : ");
	scanf_s("%u", &seed);
	printf("\ncreating a BST from random numbers\n");
	srand(seed);

	make_BST();

	int find_key;
	printf("Enter the key to search >> ");
	scanf_s("%d", &find_key);
	search(find_key);

	printf("Inorder treversal of the BST shows the sorted sequence\n");
	inorder(root);
	printf("\n");
	return 0;
}

link modified_search(int key)
{
	link location_of_parent = NULL;

	if (!root) return NULL;
	else
	{
		for (location_of_parent = root;location_of_parent;)
		{
			if (location_of_parent->key < key)
			{
				if (!location_of_parent->r_ch)
					return location_of_parent;
				else location_of_parent = location_of_parent->r_ch;
			}
			else if (location_of_parent->key == key)
				return NULL;
			else
			{
				if (!location_of_parent->l_ch)
					return location_of_parent;
				else location_of_parent = location_of_parent->l_ch;
			}
		}
	}

	return location_of_parent;
}

bool add_node(int key)
{
	link tmp; CALLOC(node, 1, tmp);
	tmp->key = key;
	if (!root)
		root = tmp;
	else
	{
		link location_of_parent = modified_search(key);

		if (!location_of_parent) return false;

		if (location_of_parent->key < key)
			location_of_parent->r_ch = tmp;
		else
			location_of_parent->l_ch = tmp;
	}
	return true;
}

void  make_BST(void)
{
	printf("< Make BST >\n");

	int i;
	int tmp;

	printf("generating numbers : ");
	for (i = 0;i < n;)
	{
		tmp = RAND;
		if (add_node(tmp))
		{
			printf("%4d", tmp);
			i++;
		}
	}
	printf("\n");
}

void search(int key)
{
	printf("The search process : ");
	link scaf; bool is_find = false;
	for (scaf = root;scaf;)
	{
		printf("%d => ", scaf->key);

		if (scaf->key == key)
		{
			is_find = true;
			break;
		}

		scaf = (scaf->key < key) ? (scaf->r_ch) : (scaf->l_ch);
	}
	printf("\n");

	if (is_find)
		printf("The element is in BST\n");
	else
		printf("The element is not in BST\n");
}

void inorder(link ptr)
{
	if (ptr)
	{
		inorder(ptr->l_ch);
		printf("%4d", ptr->key);
		inorder(ptr->r_ch);
	}
}