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

코드

---

 //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)

 

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

---

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

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

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

 

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

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

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

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

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