자료구조_Binary Search Tree (BST)

Binary Search Tree 자료구조입니다.

메모리는 동적이 아닌 정적으로 잡아서 사용하고 있으니, 필요시 동적할당으로 수정하시면 됩니다.

소스는 아래 참고 바랍니다.

#include "iostream"
using namespace std;

#define MAX_DATA 10000
#define INIT_DATA -1

typedef int T;
typedef struct _node {
	T data;
	struct _node *left, *right;
} NODE;
NODE tree[MAX_DATA + 1];
NODE *root_node;
int tree_idx;

NODE *alloc_node() {
	return &tree[tree_idx++];
}

void init() {
	for (int i = 0; i < MAX_DATA; i++) {
		tree[i].data = INIT_DATA;
		tree[i].left = tree[i].right = 0;
	}
	root_node = 0;
	tree_idx = 0;
}

NODE* insert_to_bst(NODE* node, T data) {
	if (node == 0) {
		node = alloc_node();
		node->data = data;
		return node;
	}

	if (node->data > data) {
		node->left = insert_to_bst(node->left, data);
		return node;
	}

	if (node->data < data) {
		node->right = insert_to_bst(node->right, data);
		return node;
	}
	return 0;
}

NODE* find_leastnode(NODE* node) {
	while (node && node->left) {
		node = node->left;
	}
	return node;
}

NODE* find_mostnode(NODE* node) {
	while (node && node->right) {
		node = node->right;
	}
	return node;
}

NODE* delete_from_bst(NODE *node, T data) {
	if (node == 0) {
		return 0;
	}

	if (data < node->data) {
		node->left = delete_from_bst(node->left, data);
		return node;
	}

	if (data > node->data) {
		node->right = delete_from_bst(node->right, data);
		return node;
	}

	node->data = INIT_DATA;

	// 단말 노드일 경우
	if (node->left == 0 && node->right == 0) {
		return node;
	}

	// 한쪽만 존재
	if (node->left == 0) {
		return node->right;
	}

	if (node->right == 0) {
		return node->left;
	}

	// 둘다 존재하는 경우
	NODE *successor_node = find_leastnode(node->right);
	node->data = successor_node->data;
	node->right = delete_from_bst(node->right, successor_node->data);
	return node;
}

void add_data(T data) {
	NODE* node = insert_to_bst(root_node, data);
	if (root_node == 0) {
		root_node = node;
	}
}

void delete_data(T data) {
	root_node = delete_from_bst(root_node, data);
}

void pre_order(NODE* node) {
	if (node == 0 || node->data == INIT_DATA) {
		return;
	}

	cout << node->data << " -> ";
	pre_order(node->left);
	pre_order(node->right);
}

void in_order(NODE* node) {
	if (node == 0 || node->data == INIT_DATA) {
		return;
	}

	pre_order(node->left);
	cout << node->data << " -> ";
	pre_order(node->right);
}

NODE *find_node(NODE *node, T data) {
	if (node == 0) {
		cout << "Not found data : " << data << endl;
		return 0;
	}

	if (node->data == data) {
		cout << "Found a data : " << data << endl;
		return node;
	}

	if (node->data < data) {
		return find_node(node->right, data);
	}

	if (node->data > data) {
		return find_node(node->left, data);
	}

	return 0;
}

void test_add() {
	init();
	add_data(50);
	add_data(30);
	add_data(25);
	add_data(35);
	add_data(4);
	add_data(7);
	add_data(70);
	add_data(69);

	pre_order(root_node);
}

void test_delete() {
	init();
	add_data(50);
	add_data(30);
	add_data(25);
	add_data(35);
	add_data(4);
	add_data(7);
	add_data(70);
	add_data(69);
	pre_order(root_node);
	cout << endl;

	delete_data(50);
	delete_data(30);
	delete_data(25);
	delete_data(35);
	delete_data(4);
	delete_data(7);
	delete_data(70);

	pre_order(root_node);
}

void test_search() {
	init();
	add_data(50);
	add_data(30);
	add_data(25);
	add_data(35);
	add_data(4);
	add_data(7);
	add_data(70);
	add_data(69);
	pre_order(root_node);
	cout << endl;
	
	find_node(root_node, 68);
	find_node(root_node, 69);
}

int main() {
	// test_add();
	// test_delete();
	// test_close_data();
	test_search();

	return 0;
}