C언어 - 이진 트리, 이진 탐색 트리 구현 (binary tree, binary search tree)
본문 바로가기
CS/알고리즘 및 자료구조

C언어 - 이진 트리, 이진 탐색 트리 구현 (binary tree, binary search tree)

by IYK2h 2021. 3. 5.
728x90

코드


 //binary search tree
#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
	int data;
	struct node* left;
	struct node* right;
}node;

node* root;

node* insert(node* root,int data)
{
	if(root == NULL)
	{
		root = (node*)malloc(sizeof(node));
		root->right = root->left = NULL;
		root->data = data;
		return root;
	}
	else
	{
		if(data < root->data)
			root->left = insert(root->left,data);
		else
			root->right = insert(root->right,data);
	}
	return root;
}

node* fMin(node* root)
{
	node* min = root;
	while(min->left!=NULL)
		min = min->left;
	return min;
}

node* delete(node* root,int data)
{
	node *tmproot = NULL;

	if(root==NULL)
		return NULL;
	if(data < root->data)
		root->left = delete(root->left,data);
	else if(data > root->data)
		root->right = delete(root->right,data);
	else
	{
		if(root -> left!=NULL && root->right != NULL)
		{
			tmproot = fMin(root->right);
			root->data = tmproot->data;
			root->right = delete(root->right,tmproot->data);
		}
		else
		{
			tmproot = (root->left == NULL) ? root->right : root->left;
			free(root);
			return tmproot;
		}
	}
	return root;
}

void print(node* root)
{
	if(root==NULL)
		return;
	printf("%d ",root->data);
	print(root->left);
	print(root->right);
}

//전위 순회
void preorderPrint(node* root)
{
	if(root==NULL)
		return;
	printf("%d ",root->data);
	print(root->left);
	print(root->right);
}

//중위 순회
void inorderPrint(node* root)
{
	if(root==NULL)
		return;
	print(root->left);
	printf("%d ",root->data);
	print(root->right);
}

//후위 순회
void postorderPrint(node* root)
{
	if(root==NULL)
		return;
	print(root->left);
	print(root->right);
	printf("%d ",root->data);
}

int main()
{
	root = insert(root,5);
	root = insert(root,1);
	root = insert(root,9);

	printf("preorder : ");
	preorderPrint(root);
	printf("\n");
	printf("inorder : ");
	inorderPrint(root);
	printf("\n");
	printf("postorder : ");
	postorderPrint(root);
	printf("\n\n");


	printf("preorder : ");
	preorderPrint(root);
	printf("\n");

	printf("delete : 9\n");
	root = delete(root,9);

	preorderPrint(root);
	printf("\n");

	root = insert(root,9);

	printf("delete : 1\n");
	root = delete(root,1);

	preorderPrint(root);
	printf("\n");

	root = insert(root,1);

	printf("delete : 5\n");
	root = delete(root,5);

	preorderPrint(root);
	printf("\n");
}

 

이진트리를 구현하기 위한 이진트리의 조건들

한 부모 노드에 자식 노드는 최소 0부터 최대 2개의  자식 노드를 가질 수 있다.

부모보다 작으면 왼쪽 자식 부모보다 크면 오른쪽 자식으로 보내야 한다.

이진트리를 순회하는 방식은 4가지가 있다. 1. 전위 순회 2. 중위 순회 3. 후위 순회 4. 레벨 순회

c언어 - 이진 트리 레벨 순회 (LevelTraverse)

 

c언어 - 이진 트리 레벨 순회 (LevelTraverse)

이진트리 레벨 순회란. 트리를 레벨이 낮은 순으로 순회하는 검색 방식 중 하나이다. 같은 레벨에 있다면 왼쪽부터 오른쪽으로 나열된다. (ex. 1, 2, 3, 4, 5, 6, 7) 레벨 순회를 하기 위해서는 트리를

iyk2h.tistory.com

 

프로그래밍하면서 배운 부분


구조체를 리턴하기 위해 구조체 반환형으로 함수를 선언해야 한다.

재귀 함수는 함수의 패턴이 있으면 패턴을 단순화시키는 게 중요하다.

단순하고 반복되는 패턴을 찾아 그 패턴을 재귀화로 만드는 게 이번 프로그래밍하면서 느낀 점이다.

 

이제부터 다른 간단한 함수를 코딩할 때 패턴을 찾으면 재귀 함수로 프로그래밍하려고 시도해볼 것 같다.

재귀 함수가 처리해야 하는 수가 일정 수준을 넘어가면 너무 느려지기 때문에 적당한 수준을 처리한다면 재귀 함수는 매력적인 함수이다.

트리에 재귀 함수가 잘 맞는 이유도 재귀 함수가 쓰이는 이유와 비슷하다.

일정 수준을 넘어가기 전에는 트리는 합리적인 자료구조이나, 일정 수준을 넘어가면 트리를 나눠서 만드는 게 더 좋다.

이렇게 보면 재귀와 트리는 비슷한 부분이 많은 거 같다.

728x90

댓글