간단한 소개~
이진 트리 (binary tree)
이진트리는 모든 노드의 차수가 최대 2인 트리 구조를 말한다.
이진트리는 정렬되지 않은 데이터를 저장하고 탐색, 삽입, 삭제 등의 연산을 수행할 수 있으며, 시간복잡도는 경우에 따라 유동적일 수 있다. 일반적으로 O(n)이다.
구현한 코드
#include <stdio.h>
typedef struct _TreeNode
{
int data;
struct _TreeNode *left, *right;
} TreeNode;
void main()
{
TreeNode *n1, *n2, *n3;
n1 = (TreeNode*)malloc(sizeof(TreeNode));
n2 = (TreeNode*)malloc(sizeof(TreeNode));
n3 = (TreeNode*)malloc(sizeof(TreeNode));
n1->data = 10;
n1->left = n2;
n1->right = n3;
n2->data = 20;
n2->left = NULL;
n2->right = NULL;
n3->data = 30;
n3->left = NULL;
n3->right = NULL;
free(n1);
free(n2);
free(n3);
return 0;
}코드 읽기
구조체 TreeNode 선언
typedef struct TreeNode
{
int data;
struct TreeNode *left, *right;
} TreeNode;TreeNode이라는 새로운 데이터 타입을 정의하여 구조체 TreeNode를 선언해준다.
그 안에 int형 변수 data와 한 노드의 각 왼쪽, 오른쪽 자식 노드를 가리키는 포인터 변수 left, right를 정의한다.
main 함수 선언
void main()
{
TreeNode *n1, *n2, *n3;
.
.main 함수를 연 뒤 먼저 TreeNode 포인터 변수인 n1, n2, n3을 정의한다.
포인터 변수 n1, n2, n3에는 이제 malloc 함수를 이용하여 아래의 함수가 실행되는 과정상에서 메모리를 할당해주도록 할 것이다. 이를 동적으로 할당해준다고 이해할 수 있다.
malloc() 함수로 메모리 할당
n1 = (TreeNode*)malloc(sizeof(TreeNode));
n2 = (TreeNode*)malloc(sizeof(TreeNode));
n3 = (TreeNode*)malloc(sizeof(TreeNode));sizeof(TreeNode)은 구조체 TreeNode의 크기를 반환하고 있다. malloc() 함수는 인자로 전달된 크기만큼의 메모리를 동적으로 할당하고, 할당된 메모리 블록의 시작 주소를 반환한다.
그런 다음에 (TreeNode*) 캐스팅 연산자를 사용하여 반환된 주소를 TreeNode 구조체의 포인터 변수로 형변환하여, 할당된 메모리 블록의 시작 주소를 TreeNode 구조체 포인터 변수 n1, n2, n3에 저장하는 것이다.
캐스팅 연산자는 C언어에서 형변환을 수행할 때 사용하는 연산자입니다.
(TreeNode)은 malloc() 함수의 반환값인 void 타입의 주소값을 TreeNode* 타입으로 형변환하는 캐스팅 연산자입니다.
다시 말해,
malloc() 함수가 반환한 메모리 블록의 주소값을
TreeNode* 타입의 포인터 변수에 할당하려고 하고 있기 때문에,
malloc() 함수가 반환한 메모리 블록의 void* 타입 주소값을
TreeNode* 타입으로 형변환해야 하고,
이를 위해 캐스팅 연산자 (TreeNode*) 를 사용하여 TreeNode* 타입으로 형변환하여 n1, n2, n3 포인터 변수에 할당하는 것!!!
트리 구현 및 할당한 메모리 해제
n1->data = 10;
n1->left = n2;
n1->right = n3;
.
.
free(n1);
free(n2);
free(n3);
return 0;
}위 코드는 각각의 포인터 변수에 TreeNode 크기만큼의 동적 메모리를 할당한 후, 해당 노드의 data와 자식 노드를 설정해주고 있다. 이진 트리의 경우 각각의 노드가 서로 연결되어야 하므로, n1의 left, right 포인터 변수에는 각각 n2, n3의 주소를 저장해줄 것이다.
free()는 동적으로 할당한 메모리를 해제하는 함수입니다. 동적으로 할당한 메모리를 해제하지 않으면 프로그램이 종료되더라도 그 메모리가 계속 차지하고 있게 되어 메모리 누수(Memory Leak)가 발생할 수 있습니다.
여기서 free() 함수는 포인터 변수 n1, n2, n3가 가리키고 있는 메모리 블록을 해제하여 메모리의 효율적인 사용을 도모하고 있다.
간단한 소개~
이진 트리의 3가지 순회
순회(Traversal)란 어떠한 목적을 위해 트리의 노드들을 체계적으로 방문하는 수행이다.
종류와 구분
전위 순회 (preorder traversal) : VLR 전위 순회는 루트 이진 트리->왼쪽 이진 트리->오른쪽 이진 트리 순으로 방문.
중위 순회 (inorder traversal) : LVR 중위 순회는 왼쪽 이진 트리->루트 이진 트리->오른쪽 이진 트리 순으로 방문.
후위 순회 (postorder traversal) : LRV후위 순회는 왼쪽 이진 트리->오른쪽 이진 트리->루트 이진 트리 순으로 방문.
구현한 코드
#include <stdio.h>
typedef struct TreeNode
{
int data;
struct TreeNode *left, *right;
} TreeNode;
TreeNode n1 = { 1, NULL, NULL };
TreeNode n2 = { 4, &n1, NULL };
TreeNode n3 = { 16, NULL, NULL };
TreeNode n4 = { 25, NULL, NULL };
TreeNode n5 = { 20, &n3, &n4 };
TreeNode n6 = { 15, &n2, &n5 };
TreeNode *root = &n6;
void preorder(TreeNode* root)
{
if(root)
{
printf("%d - ", root->data);
preorder(root->left);
preorder(root->right);
}
}
void inorder(TreeNode* root)
{
if(root)
{
inorder(root->left);
printf("%d - ", root->data);
inorder(root->right);
}
}
void postorder(TreeNode* root)
{
if(root)
{
postorder(root->left);
postorder(root->right);
printf("%d - ", root->data);
}
}
int main()
{
preorder(root); // inorder(root); // postorder(root);
return 0;
}코드 읽기
구조체 TreeNode 선언 및 트리 구현
함수 선언 전까진 위 코드를 바탕으로 동일하다. 아래의 코드는 위에서 화살표 연산자를 통해 노드 간 간선을 그은 것과 동일한 코드다. 다만 해당 코드의 위치가 다르다던가, 트리의 루트가 되는 포인터 변수 root에 대한 지정하는 점을 주목할 수 있다.
.
.
TreeNode n4 = { 25, NULL, NULL };
TreeNode n5 = { 20, &n3, &n4 };
TreeNode n6 = { 15, &n2, &n5 };
TreeNode *root = &n6;각각의 순회 구현
void 어쩌구order(TreeNode* root)
{
if(root)
{
.
.간단히만 짚자면 if(root)는 root 포인터가 NULL이 아닌 경우에만 if문 안의 코드를 실행하도록 하는 탈출 조건이다.
만약 root가 NULL인 경우, 함수가 더 이상 재귀 호출되지 않고 함수 호출 스택에서 나와서 다음 코드가 실행된다. 이진트리에서 NULL은 자식 노드가 없음을 나타내므로, 재귀 호출에서 자식 노드가 NULL인 경우 이 조건문에 걸린다.
결과 출력
