트리 노드와 구조
포인터로 노드를 모델링해 보세요.
트리 노드와 구조은(는) CoddyKit의 무료 C Academy 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 C Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
이진 트리란 무엇인가요?
이진 트리는 각 노드가 값을 하나 보유하고 왼쪽 자식과 오른쪽 자식, 최대 두 자식으로 연결되는 계층적 구조입니다.
가장 위에 있는 노드가 루트입니다. 자식이 없는 노드는 리프입니다. 이러한 구조 덕분에 이진 트리는 빠른 검색, 정렬, 재귀 처리에 적합합니다.
노드 구조체
C에서는 데이터를 저장하고 자기 자신을 가리키는 포인터 두 개를 포함하는 구조체로 노드를 모델링합니다.
각 포인터는 다른 Node를 가리키거나, 해당 방향에 자식이 없을 때 NULL을 가리킵니다.
struct Node {
int value;
struct Node *left;
struct Node *right;
};자기 참조 포인터를 사용하는 이유
노드는 값으로 다른 완전한 노드를 포함할 수 없습니다. 그렇게 하면 무한한 저장 공간이 필요하기 때문입니다. 대신 자식을 가리키는 포인터를 보유합니다.
포인터의 크기는 고정되어 있으므로 구조체는 알려진 크기를 유지하면서도 힙의 다른 노드와 연결될 수 있습니다.
struct Node {
int value;
struct Node *left; /* 8 bytes on 64-bit */
struct Node *right; /* 8 bytes on 64-bit */
};편의를 위한 typedef
어디서나 struct Node를 입력하는 일은 번거롭습니다. typedef를 사용하면 간단히 Node라고 쓸 수 있습니다.
이 시점에서는 형식이 아직 완전히 정의되지 않았으므로 구조체 내부에서는 태그가 여전히 필요합니다.
typedef struct Node {
int value;
struct Node *left;
struct Node *right;
} Node;Node 할당하기
노드는 malloc으로 생성되어 힙에 저장됩니다. 값을 설정하고 두 자식 포인터를 모두 NULL로 초기화합니다.
메모리를 사용하기 전에 malloc이 NULL을 반환하지 않았는지 항상 확인하십시오.
Node *create_node(int value) {
Node *n = malloc(sizeof(Node));
if (n == NULL) return NULL;
n->value = value;
n->left = NULL;
n->right = NULL;
return n;
}손으로 작은 트리 만들기
연결 관계를 이해하기 위해 루트와 두 자식으로 이루어진 노드 세 개를 직접 연결해 보겠습니다.
이 프로그램은 트리를 만들고 값을 출력한 다음, 일반적으로는 트리를 해제합니다(뒤에서 다룹니다).
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node *left;
struct Node *right;
} Node;
Node *create_node(int v) {
Node *n = malloc(sizeof(Node));
n->value = v; n->left = NULL; n->right = NULL;
return n;
}
int main(void) {
Node *root = create_node(10);
root->left = create_node(5);
root->right = create_node(15);
printf("%d %d %d\n", root->left->value, root->value, root->right->value);
return 0;
}손자 노드에 도달하기
화살표 연산자를 이어 붙여 트리를 탐색할 수 있습니다. root->left->right는 왼쪽 자식으로 내려간 다음 그 자식의 오른쪽 자식으로 내려갑니다.
포인터를 따라가기 전에 해당 포인터가 NULL이 아닌지 확인하십시오. 그렇지 않으면 프로그램이 중단됩니다.
/* root
* \
* right (15)
* \
* right->right (20)
*/
if (root->right != NULL && root->right->right != NULL)
printf("%d\n", root->right->right->value);재귀적으로 노드 세기
재귀는 트리에 자연스럽게 맞습니다. 노드를 셀 때 빈 하위 트리에는 노드가 0개이고, 그렇지 않으면 현재 노드 하나와 두 하위 트리의 노드 수를 더합니다.
NULL 확인이 재귀를 멈추게 하는 기본 사례입니다.
int count_nodes(Node *root) {
if (root == NULL) return 0;
return 1 + count_nodes(root->left)
+ count_nodes(root->right);
}높이 측정하기
트리의 높이는 루트에서 리프까지 이어지는 가장 긴 경로의 길이이며, 간선의 수로 측정합니다.
두 하위 트리 높이 중 더 큰 값에 1을 더합니다. 빈 트리의 높이를 -1로 두면 노드 하나만 있는 트리의 높이는 0이 됩니다.
int height(Node *root) {
if (root == NULL) return -1;
int l = height(root->left);
int r = height(root->right);
return 1 + (l > r ? l : r);
}리프 식별하기
리프는 자식이 없는 노드입니다. 즉 left와 right가 모두 NULL입니다.
이 간단한 도우미는 다양한 순회 및 개수 세기 루틴에서 유용합니다.
int is_leaf(Node *n) {
return n != NULL && n->left == NULL && n->right == NULL;
}구조 활용하기
여기서는 작은 트리를 만들고 재귀 도우미를 사용해 노드 수와 높이를 출력합니다.
도우미 함수는 고정된 형태를 가정하지 않습니다. 재귀가 실제 포인터를 따라가기 때문에 어떤 트리에서도 작동합니다.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *nn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
int count(Node *r){ return r? 1+count(r->left)+count(r->right):0; }
int height(Node *r){ if(!r) return -1; int l=height(r->left),x=height(r->right); return 1+(l>x?l:x); }
int main(void){
Node *root = nn(10);
root->left = nn(5); root->right = nn(15);
root->left->left = nn(2);
printf("nodes=%d height=%d\n", count(root), height(root));
return 0;
}빠른 확인
노드 구조에 대한 이해도를 확인해 보십시오.
복습
이진 트리의 노드는 값 하나와 자기 자신을 가리키는 포인터 두 개(left, right)를 보유하며, 자식이 없을 때는 이를 NULL로 설정합니다.
malloc으로 노드를 할당하고 직접 연결한 뒤 재귀적으로 처리합니다. 개수, 높이, 리프 확인에서는 항상 NULL 확인이 기본 사례입니다.
자주 묻는 질문
“트리 노드와 구조” 강의는 무료인가요?
네 — “트리 노드와 구조” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 C Academy 강의 전체를 잠금 해제할 수 있습니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“트리 노드와 구조”에서 뭘 배우나요?
포인터로 노드를 모델링해 보세요. 브라우저에서 직접 실행하는 실습 코드로 C Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
C Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 C Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.
“트리 노드와 구조” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 C Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 C Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.