본문 바로가기
CS/Data structures

[자료구조] C언어 - 이진 탐색 트리(BST , binary search tree) 구현 - 객체지향

by Nahwasa 2022. 4. 9.

- C언어로 구현한 이진 탐색 트리(BST, binary search tree) 코드이다. 완벽하진 않지만 c에서 객체지향 개념을 넣을 수 있는 기본 베이스는 마련해둔 코드이다.

 

- 재귀를 사용한 버전과, 그렇지 않은 버전 두 가지 종류가 함께 들어있다.(각각 따로 빼내도 된다.) 사용예시처럼 구분해서 사용할 수 있다. 덕분에 코드가 좀 길다. binary_search_tree.c만 600줄정도..

 

- 글 말고 github으로 보려면 여기를 누르면 된다.

 

- 영어를 잘 못하지만 주석을 영어로 작성했으므로 틀린 표현이 많을 수 있다. (댓글로 알려줘요 ㅠ)

 

- 이하 코드에서 사용된 node.h, list.h, list.c, stack.h, stack.c, queue.h, queue.c는 '[자료구조] C언어 - 이중 연결 리스트(doubly linked list) 구현 - 객체지향'(링크), '[자료구조] C언어 - 스택(stack) 구현 - 객체지향'(링크), '[자료구조] C언어 - 큐(queue) 구현 - 객체지향'(링크) 글에서 구현한 코드들이다. 위 github에는 모든 코드가 있으므로 거기서 확인하거나, 각 글 링크에서 확인하면 된다.

 

 

0. 사용예시

#include<stdio.h>
#include"binary_search_tree.h"

int main(int argc, char* argv[])
{
	printf("--- nonrecurrent ---\n");
	bst_t* b = create_nonrecurrent_bst();
	
	b->op->insert_node(b, 5);
	b->op->insert_node(b, 3);
	b->op->insert_node(b, 8);
	b->op->insert_node(b, 1);
	b->op->insert_node(b, 10);

	b->op->print_inorder(b);
	b->op->print_preorder(b);
	b->op->print_postorder(b);
	b->op->print_bfs(b);
	b->op->print_dfs(b);


	printf("--- recursive ---\n");	
	b = create_recursive_bst();
	
	b->op->insert_node(b, 5);
	b->op->insert_node(b, 3);
	b->op->insert_node(b, 8);
	b->op->insert_node(b, 1);
	b->op->insert_node(b, 10);

	b->op->print_inorder(b);
	b->op->print_preorder(b);
	b->op->print_postorder(b);
	b->op->print_bfs(b);
	b->op->print_dfs(b);
}

 

1. binary_search_tree.h

/**
* binary search tree Header
* made by nahwasa
*/

#ifndef BST_H_NAHWASA
#define BST_H_NAHWASA

#include"list.h"
#include"stack.h"
#include"queue.h"

typedef struct bst_node {
	struct bst_node* left;
	struct bst_node* right;
	int num;
	int checked;
} bst_node_t;

typedef struct {
	bst_node_t* root;
	int size;
	struct bst_operations* op;
} bst_t;

struct bst_operations {
	void (*destroy)(bst_t* b);
	bst_node_t* (*search_node)(bst_t* b, int find_num);
	void (*insert_node)(bst_t* b, int num);
	void (*remove_node)(bst_t* b, int num);
	void (*print_inorder)(bst_t* b);
	void (*print_preorder)(bst_t* b);
	void (*print_postorder)(bst_t* b);
	void (*print_bfs)(bst_t* b);
	void (*print_dfs)(bst_t* b);
	int (*get_size)(bst_t* b);
};

extern bst_t* create_recursive_bst();
extern bst_t* create_nonrecurrent_bst();

#endif

 

2. binary_search_tree.c

/**
* binary search tree (with and without recursion call)
* made by nahwasa
*
* list OOP, there's root Node.
*
*     bst  -- start tree structure and using like OOP's class name
*      |
*     root    
*     /   \
* nodes..  nodes..
*
* SO, you can make many tree structures you wants.
*/

#include<stdio.h>
#include<stdlib.h>
#include"binary_search_tree.h"

static void destroy(bst_t* b);
static bst_node_t* search_node_recursive(bst_t* b, int find_num);
static void insert_node_recursive(bst_t* b, int num);
static void remove_node_recursive(bst_t* b, int num);
static void print_inorder_recursive(bst_t* b);
static void print_preorder_recursive(bst_t* b);
static void print_postorder_recursive(bst_t* b);
static bst_node_t* search_node_nonrecurrent(bst_t* b, int find_num);
static void insert_node_nonrecurrent(bst_t* b, int num);
static void remove_node_nonrecurrent(bst_t* b, int num);
static void print_inorder_nonrecurrent(bst_t* b);
static void print_preorder_nonrecurrent(bst_t* b);
static void print_postorder_nonrecurrent(bst_t* b);
static void print_bfs(bst_t* b);
static void print_dfs(bst_t* b);
static int get_size(bst_t* b);

/*
* functions using recursive call
*/
static struct bst_operations recursive_op =
	{
		.destroy = destroy,
		.search_node = search_node_recursive,
		.insert_node = insert_node_recursive,
		.remove_node = remove_node_recursive,
		.print_inorder = print_inorder_recursive,
		.print_preorder = print_preorder_recursive,
		.print_postorder = print_postorder_recursive,
		.print_bfs = print_bfs,
		.print_dfs = print_dfs,
		.get_size = get_size
	};

/*
* functions without recursive call
*/
static struct bst_operations nonrecurrent_op =
	{
		.destroy = destroy,
		.search_node = search_node_nonrecurrent,
		.insert_node = insert_node_nonrecurrent,
		.remove_node = remove_node_nonrecurrent,
		.print_inorder = print_inorder_nonrecurrent,
		.print_preorder = print_preorder_nonrecurrent,
		.print_postorder = print_postorder_nonrecurrent,
		.print_bfs = print_bfs,
		.print_dfs = print_dfs,
		.get_size = get_size
	};


bst_t* create_recursive_bst()
{
	bst_t* b = (bst_t*)malloc(sizeof(bst_t));
	b->op = &recursive_op;
	b->root = NULL;
	b->size = 0;
	return b;
}


bst_t* create_nonrecurrent_bst()
{
	bst_t* b = (bst_t*)malloc(sizeof(bst_t));
	b->op = &nonrecurrent_op;
	b->root = NULL;
	b->size = 0;
	return b;
}


static void destroy(bst_t* b)
{
	b->op = NULL;
	free(b);
	b = NULL;
}

/*
* create one node
*/
static bst_node_t* create_node(int num)
{
	bst_node_t* n = (bst_node_t*)malloc(sizeof(bst_node_t));
	n->left = NULL;
	n->right = NULL;
	n->num = num;
	n->checked = 0;
 
	return n;
}

static bst_node_t* search_node_nonrecurrent(bst_t* b, int find_num)
{
	stack_t* st = create_stack();
	
	if (b->root == NULL) {	// if there's no root node
		st->op->destroy(st);		
		return NULL;
	}
	
	st->op->push(st, b->root);

	while (!st->op->is_empty(st)) {
		bst_node_t* n = (bst_node_t*)st->op->pop(st);

		if (n->num == find_num)
			return n;
		else if (n->num > find_num)
			st->op->push(st, n->left);
		else
			st->op->push(st, n->right);
	}

	st->op->destroy(st);
	return NULL;
}

static bst_node_t* search_node_recursive_sub(bst_node_t* n, int find_num)
{
	if (n == NULL)
		return NULL;

	if (n->num == find_num)
		return n;
	else if (n->num > find_num)
		search_node_recursive_sub(n->left, find_num);
	else
		search_node_recursive_sub(n->right, find_num);
}

static bst_node_t* search_node_recursive(bst_t* b, int find_num)
{
	if (b->root == NULL)	// if there's no root node
		return NULL;
		
	return search_node_recursive_sub(b->root, find_num);
}

 
static void insert_node_nonrecurrent(bst_t* b, int num)
{
	bst_node_t* nn = create_node(num);
	stack_t* st = create_stack();
		
	
	if (b->root == NULL) {
		b->root = nn;
		b->size++;
		st->op->destroy(st);
		return;	
	}
	
	st->op->push(st, b->root);
	while (!st->op->is_empty(st)) {
		bst_node_t* n = (bst_node_t*)st->op->pop(st);
		
		if (nn->num > n->num) {
			if (n->right != NULL)
				st->op->push(st, n->right);
			else 
				n->right = nn;
		} else if (nn->num <= n->num) {
			if (n->left != NULL)
				st->op->push(st, n->left);
			else 
				n->left = nn;
		}
	}
		
	b->size++;
	st->op->destroy(st);	
}

static void insert_node_recursive_sub(bst_node_t* n, bst_node_t* nn)
{
	if (nn->num > n->num) {
		if (n->right != NULL)
			insert_node_recursive_sub(n->right, nn);
		else 
			n->right = nn;
	} else if (nn->num <= n->num) {
		if (n->left != NULL)
			insert_node_recursive_sub(n->left, nn);
		else 
			n->left = nn;
	}
}


static void insert_node_recursive(bst_t* b, int num)
{
	bst_node_t* nn = create_node(num);
	
	if (b->root == NULL) {
		b->root = nn;
		b->size++;
		return;	
	}

	insert_node_recursive_sub(b->root, nn);
	b->size++;
}


static bst_node_t* find_min_bst_node(bst_t* b, bst_node_t* bn)
{
	stack_t* st = create_stack();

	if (bn == NULL) {
		st->op->destroy(st);
		return NULL;	
	}

	st->op->push(st, bn);
	while (!st->op->is_empty(st)) {
		bst_node_t* n = (bst_node_t*)st->op->pop(st);

		if (n->left != NULL)
			st->op->push(st, n->left);
		else {
			st->op->destroy(st);
			return n;
		}
	}
}

static bst_node_t* find_max_bst_node(bst_t* b, bst_node_t* bn)
{
	stack_t* st = create_stack();	
	
	if (bn == NULL) {
		st->op->destroy(st);
		return NULL;
	}

	st->op->push(st, bn);
	while (!st->op->is_empty(st)) {
		bst_node_t* n = (bst_node_t*)st->op->pop(st);

		if (n->right != NULL)
			st->op->push(st, n->right);
		else {
			st->op->destroy(st);
			return n;
		}
	}	
}
 
static void remove_node_recursive(bst_t* b, int num)
{
	stack_t* st = create_stack();	

	if (b->root == NULL) {
		st->op->destroy(st);
		return;
	}

	st->op->push(st, b->root);
	while (!st->op->is_empty(st)) {
		bst_node_t* n = (bst_node_t*)st->op->pop(st);

		if (n->num > num)
			st->op->push(st, n->left);
		else if (n->num < num)
			st->op->push(st, n->right);
		else {
			if (n->left != NULL && n->right != NULL) {
				bst_node_t* tn = find_min_bst_node(b, n->right);
				num = n->num = tn->num;          
				st->op->push(st, n->right);
			} else if (n->left == NULL) {
				n = n->right;
				b->size--;
			} else if (n->right == NULL) {
				n = n->left;
				b->size--;	
			}			
		} 
	}
	st->op->destroy(st);
}

static void remove_node_nonrecurrent(bst_t* b, int num)
{
	stack_t* st = create_stack();	

	if (b->root == NULL) {
		st->op->destroy(st);
		return;
	}

	st->op->push(st, b->root);
	while (!st->op->is_empty(st)) {
		bst_node_t* n = (bst_node_t*)st->op->pop(st);

		if (n->num > num)
			st->op->push(st, n->left);
		else if (n->num < num)
			st->op->push(st, n->right);
		else {
			if (n->left != NULL && n->right != NULL) {
				bst_node_t* tn = find_min_bst_node(b, n->right);
				num = n->num = tn->num;          
				st->op->push(st, n->right);
			} else if (n->left == NULL) {
				n = n->right;
				b->size--;
			} else if (n->right == NULL) {
				n = n->left;
				b->size--;	
			}			
		} 
	}
	st->op->destroy(st);
}
 

static void print_inorder_nonrecurrent(bst_t* b)
{	
	node_t* n;
	int* i;
	list_t* l = create_list();

	if (b->root == NULL) {
		l->op->destroy(l);
		return;
	}

	l->op->insert_to_head(l, b->root);
	while (1) {
		if (b->op->get_size(b) == l->op->get_size(l)) {
			break;
		}

		n = l->op->get_head_node(l);
		
		while (n->next != NULL) {
			if (! ((bst_node_t*) n->data)->checked ) {
				if (n->prev != NULL)
					l->op->insert_to_before_node(l, n, ((bst_node_t*) n->data)->left);
				if (n->next != NULL)
					l->op->insert_to_before_node(l, n->next, ((bst_node_t*) n->data)->right);
			}
			((bst_node_t*) n->data)->checked = 1;
			n = n->next;
		}		
	}
	
	while (l->op->get_size(l) != 0) {
		n = l->op->get_head_node(l);
		((bst_node_t*) n->data)->checked = 0;
		printf("%d ", ((bst_node_t*) n->data)->num);
	}

	l->op->destroy(l);
	printf("\n");
}

static void print_inorder_recursive_sub(bst_node_t* n)
{
	if(n == NULL)
		return;

	print_inorder_recursive_sub(n->left);
	printf("%d ", n->num);
	print_inorder_recursive_sub(n->right);
}

static void print_inorder_recursive(bst_t* b)
{	
	if (b->root == NULL)
		return;
	
	print_inorder_recursive_sub(b->root);
	printf("\n");
}
	

static void print_preorder_nonrecurrent(bst_t* b)
{	
	node_t* n;
	int* i;
	list_t* l = create_list();

	if (b->root == NULL) {
		l->op->destroy(l);
		return;
	}

	l->op->insert_to_head(l, b->root);
	while (1) {
		if (b->op->get_size(b) == l->op->get_size(l)) {
			break;
		}

		n = l->op->get_head_node(l);
		
		while (n->next != NULL) {
			if (! ((bst_node_t*) n->data)->checked ) {
				if (n->prev != NULL)
					l->op->insert_to_before_node(l, n->next, ((bst_node_t*) n->data)->left);
				if (n->next != NULL)
					l->op->insert_to_before_node(l, n->next, ((bst_node_t*) n->data)->right);
			}
			((bst_node_t*) n->data)->checked = 1;
			n = n->next;
		}		
	}
	
	while (l->op->get_size(l) != 0) {
		n = l->op->get_head_node(l);
		((bst_node_t*) n->data)->checked = 0;
		printf("%d ", ((bst_node_t*) n->data)->num);
	}

	l->op->destroy(l);
	printf("\n");
}

static void print_preorder_recursive_sub(bst_node_t* n)
{
	if(n == NULL)
		return;

	printf("%d ", n->num);
	print_preorder_recursive_sub(n->left);	
	print_preorder_recursive_sub(n->right);
}

static void print_preorder_recursive(bst_t* b)
{	
	if (b->root == NULL)
		return;
	
	print_preorder_recursive_sub(b->root);
	printf("\n");
}

static void print_postorder_nonrecurrent(bst_t* b)
{
	node_t* n;
	int* i;
	list_t* l = create_list();

	if (b->root == NULL) {
		l->op->destroy(l);
		return;
	}

	l->op->insert_to_head(l, b->root);
	while (1) {
		if (b->op->get_size(b) == l->op->get_size(l)) {
			break;
		}

		n = l->op->get_head_node(l);
		
		while (n->next != NULL) {
			if (! ((bst_node_t*) n->data)->checked ) {
				if (n->prev != NULL)
					l->op->insert_to_before_node(l, n, ((bst_node_t*) n->data)->left);
				if (n->next != NULL)
					l->op->insert_to_before_node(l, n, ((bst_node_t*) n->data)->right);
			}
			((bst_node_t*) n->data)->checked = 1;
			n = n->next;
		}		
	}
	
	while (l->op->get_size(l) != 0) {
		n = l->op->get_head_node(l);
		((bst_node_t*) n->data)->checked = 0;
		printf("%d ", ((bst_node_t*) n->data)->num);
	}

	l->op->destroy(l);
	printf("\n");
}

static void print_postorder_recursive_sub(bst_node_t* n)
{
	if(n == NULL)
		return;

	print_postorder_recursive_sub(n->left);	
	print_postorder_recursive_sub(n->right);
	printf("%d ", n->num);
}

static void print_postorder_recursive(bst_t* b)
{	
	if (b->root == NULL)
		return;
	
	print_postorder_recursive_sub(b->root);
	printf("\n");
}



static void print_bfs(bst_t* b)
{
	bst_node_t* n;
	int* i;
	queue_t* q = create_queue();

	if (b->root == NULL)
		return;

	q->op->enqueue(q, b->root);
	while (q->op->get_size(q) != 0) {	
		n = (bst_node_t*)q->op->dequeue(q);
		
		printf("%d ", n->num);
		
		if (n->left != NULL) {
			q->op->enqueue(q, n->left);
		}		

		if (n->right != NULL) {
			q->op->enqueue(q, n->right);
		}
	}
	
	
	printf("\n");
}

static void print_dfs(bst_t* b)
{
	bst_node_t* n;
	int* i;
	stack_t* s = create_stack();

	if (b->root == NULL)
		return;	

	s->op->push(s, b->root);
	while (s->op->get_size(s) != 0) {	
		n = (bst_node_t*)s->op->pop(s);
		
		printf("%d ", n->num);
		
		if (n->left != NULL) {
			s->op->push(s, n->left);
		}	
		
		if (n->right != NULL) {
			s->op->push(s, n->right);
		}
			

	}
	printf("\n");
}


static int get_size(bst_t* b)
{
	return b->size;
}

 

저작자표시 비영리

'CS > Data structures' 카테고리의 다른 글

펜윅 트리(Fenwick tree, BIT) - 기본, 2D, lazy propagation(range update - point query, range update - range query)  (4) 2022.08.15
[자료구조] C언어 - 우선순위 큐(priority queue) 구현 - 객체지향  (0) 2022.04.09
[자료구조] C언어 - 큐(queue) 구현 - 객체지향  (0) 2022.04.09
[자료구조] C언어 - 스택(stack) 구현 - 객체지향  (0) 2022.04.09
[자료구조] C언어 - 다항식(polynomial) 구현 - 객체지향  (0) 2022.04.09

관련글

댓글

티스토리툴바