이진 트리 (BinaryTree)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_LEN 10


typedef struct _SNode
{
	int data;

	struct _SNode* pLeft;
	struct _SNode* pRight;
} SNode;

SNode* g_pRoot = NULL;


SNode* CreateNode(int _data);
void AddNodeRecursive(SNode* _pNode, int _newData);
void BuildTree(int* _pArr);

// Search
SNode* Find(int _data);
void Remove(int _data);

void Clear();
void ClearRecursive(SNode* _pNode);

void PrintAll();
void PrintAllRecursive(SNode* _pNode);


void main()
{
	// Binary Tree(이진트리, 이진나무)
	srand(time(NULL));

	int arr[MAX_LEN] = { 0 };
	for (int i = 0; i < MAX_LEN; ++i) {
		arr[i] = rand() % 100;
		printf("%d - ", arr[i]);
	}
	printf("(%d)\n", MAX_LEN);

	printf("\n");

	// 정렬
	BuildTree(arr);

	printf("\n");

	PrintAll();

	printf("\n");

	Clear();
}


SNode* CreateNode(int _data)
{
	SNode* pNewNode =
		(SNode*)malloc(sizeof(SNode));

	pNewNode->data = _data;
	pNewNode->pLeft = NULL;
	pNewNode->pRight = NULL;

	return pNewNode;
}

void AddNodeRecursive(SNode* _pNode, int _newData)
{
	if (_pNode == NULL) return;

	//printf("[ %d / %d ]\n",
	//		_pNode->data, _newData);

	// 새로운 데이터가 현재 노드 값 보다 작으면,
	if (_newData < _pNode->data)
	{
		// 왼쪽이 NULL이 아니면 노드가 있다는 뜻
		if (_pNode->pLeft != NULL) {
			AddNodeRecursive(_pNode->pLeft, _newData);
		} else {
			// 왼쪽이 NULL이라는 뜻
			SNode* pNewNode = CreateNode(_newData);
			_pNode->pLeft = pNewNode;

			printf("Add [%d] Left: %d\n",
					_pNode->data,
					_pNode->pLeft->data);
		}
	}
	else
	{
		if (_pNode->pRight != NULL) {
			AddNodeRecursive(_pNode->pRight, _newData);
		} else {
			_pNode->pRight = CreateNode(_newData);

			printf("Add [%d] Right: %d\n",
					_pNode->data,
					_pNode->pRight->data);
		}
	}
}

void BuildTree(int* _pArr)
{
	if (_pArr == NULL) return;

	if (g_pRoot != NULL)
	{
		// 정리
	}

	g_pRoot = CreateNode(_pArr[0]);

	for (int i = 1; i < MAX_LEN; ++i) {
		AddNodeRecursive(g_pRoot, _pArr[i]);
	}
}

void Clear()
{
	if (g_pRoot == NULL) return;

	ClearRecursive(g_pRoot);
}

void ClearRecursive(SNode* _pNode)
{
	if (_pNode == NULL) return;

	ClearRecursive(_pNode->pLeft);
	ClearRecursive(_pNode->pRight);

	printf("Remove: %d\n", _pNode->data);
	if (_pNode != NULL) {
		free(_pNode);
		_pNode = NULL;
	}
}

void PrintAll()
{
	if (g_pRoot == NULL) return;

	PrintAllRecursive(g_pRoot);
	printf("(%d)\n", MAX_LEN);
}

void PrintAllRecursive(SNode* _pNode)
{
	if (_pNode == NULL) return;

	PrintAllRecursive(_pNode->pLeft);

	printf("[%d]-", _pNode->data);

	PrintAllRecursive(_pNode->pRight);
}

<이진 트리>(Binary tree)

 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조입니다.

이진 트리 구조 예시

• 왼쪽 자식(Left child): 현재 노드의 왼쪽에 위치한 자식 노드
• 오른쪽 자식(Right child): 현재 노드의 오른쪽에 위치한 자식 노드
• 루트(Root): 트리의 가장 위에 있는 노드로, 시작점입니다. 트리는 무조건 하나의 루트 노드만 존재
• 리프(Leaf): 자식이 없는 노드입니다. 좌, 우 모두 없는 노드
• 서브트리(Subtree): 트리 안에 작은 트리같은 느낌으로, 어떤 노드를 루트로 하는 부분 트리입니다.

다음은 트리의 종류입니다.

• 완전 이진 트리(Complete Binary Tree): 모든 레벨이 완전히 채워져 있으며, 마지막 레벨만 노드가 왼쪽부터 차례로 채워져 있는 트리입니다.
• 정렬 이진 트리(Binary Search Trr, BST): 왼쪽 서브트리의 모든 노드는 루트 노드보다 작은 값, 오른쪽 서브트리의 모든 노드는 루트 누드보다 큰 값을 가지는 트리입니다.
• 균형 이진 트리: 모드 서브트리가 균형을 이루어 깊이 차이가 특정 값 이하로 유지되는 트리입니다.