포인터를 이용한 이진 탐색 트리(Binary search tree)

포인터를 통해 이진 탐색 트리를 간단히 만들어 보자.

 

이진 탐색 트리 개념

https://www.crocus.co.kr/446

이진 탐색 트리(Binary Search Tree) 개념

 

배열을 이용한 이진 탐색 트리

https://www.crocus.co.kr/631

배열을 이용한 이진 탐색 트리(Binary Search Tree) 소스 코드

 

lagacy 코드

https://www.crocus.co.kr/447

이진 탐색 트리(Binary Search Tree) 소스 코드

#include <iostream>
#define MAXROW 5

typedef struct NODE
{
	int key;
	int value;
	struct NODE *left;
	struct NODE *right;
}NODE;

NODE *root;

// 초기화
int init(int key, int val)
{
	// 가장 처음에 들어오는 값은 루트가 된다.
	NODE *newNode = (NODE*)malloc(sizeof(NODE));
	newNode->key = key;
	newNode->value = val;
	newNode->left = NULL;
	newNode->right = NULL;
	root = newNode;
	return 1;
}

// 삽입
int insert(int key, int val, NODE *pt)
{
	NODE *temp = pt;

	// val가 현재 보고있는 노드의 값 보다 작다면
	if (val < temp->value)
	{
		// 왼쪽이 비어있으면
		if (temp->left == NULL)
		{
			// 해당 부분에 삽입
			NODE *newNode = (NODE*)malloc(sizeof(NODE));
			temp->left = newNode;
			newNode->key = key;
			newNode->value = val;
			newNode->left = NULL;
			newNode->right = NULL;
		}

		// 비어있지 않다면 왼쪽으로 이동
		else
		{
			insert(key, val, temp->left);
		}
	}

	// val이 노드에 값보다 보다 크거나 같다면
	else if (val >= temp->value)
	{
		// 오른쪽이 비어있으면
		if (temp->right == NULL)
		{
			// 해당 부분에 삽입
			NODE *newNode = (NODE*)malloc(sizeof(NODE));
			temp->right = newNode;
			newNode->key = key;
			newNode->value = val;
			newNode->left = NULL;
			newNode->right = NULL;
		}

		// 비어있지 않다면 오른쪽으로 이동
		else
		{
			insert(key, val, temp->right);
		}

	}

	return 1;
}
// 이진 탐색 트리 출력(전위 순회)
void binaryTreePrint_preOrder(NODE *node) {
	if (node == NULL) {
		return;
	}

	int key = node->key;
	printf("key : %d value : %d\n", node->key, node->value);
	binaryTreePrint_preOrder(node->left);
	binaryTreePrint_preOrder(node->right);
}

int main()
{

	int bst[MAXROW][2] = {
		{3, 17},
		{1, 18},
		{5, 20},
		{4, 20},
		{2, 15}
	};
	
	// 이진 트리 데이터 삽입
	for (int i = 0; i < MAXROW; i++)
	{
		if (i == 0)
			init(bst[i][0], bst[i][1]);
		else
			insert(bst[i][0], bst[i][1], root);

		printf("binaryTree :: [ \n");
		binaryTreePrint_preOrder(root);
		printf("]\n");
	}

	// 이진 트리 데이터 출력
	printf("binaryTree :: [ \n");
	binaryTreePrint_preOrder(root);
	printf("]\n");

	return 0;
}