순회
중위, 전위, 후위 순회를 배워 보세요.
순회은(는) CoddyKit의 무료 C Academy 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 C Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
순회란 무엇인가
순회는 트리의 모든 노드를 정확히 한 번씩 방문하는 체계적인 방법입니다.
대표적인 세 가지 깊이 우선 순회 순서는 중위 순회, 전위 순회, 후위 순회입니다. 이 순서들은 현재 노드를 하위 트리와 비교해 언제 처리하는지만 다릅니다.
중위 순회
중위 순회는 왼쪽 하위 트리를 방문한 다음 노드를 방문하고, 마지막으로 오른쪽 하위 트리를 방문합니다.
BST에서는 이 순회가 값을 오름차순으로 출력하므로, 탐색 트리에 가장 유용한 순회입니다.
void in_order(Node *root) {
if (root == NULL) return;
in_order(root->left);
printf("%d ", root->value);
in_order(root->right);
}전위 순회
전위 순회는 먼저 노드를 방문한 다음 왼쪽 하위 트리와 오른쪽 하위 트리를 차례로 방문합니다.
루트가 자식보다 먼저 출력되므로 트리를 복사하거나 전위 표기식을 만들 때 유용합니다.
void pre_order(Node *root) {
if (root == NULL) return;
printf("%d ", root->value);
pre_order(root->left);
pre_order(root->right);
}후위 순회
후위 순회는 두 하위 트리를 먼저 방문한 다음 마지막에 노드를 방문합니다.
자식이 부모보다 먼저 처리되므로 트리를 해제할 때 정확히 필요한 순서입니다. 따라서 자식이 사라진 뒤에 노드를 사용하는 일이 없습니다.
void post_order(Node *root) {
if (root == NULL) return;
post_order(root->left);
post_order(root->right);
printf("%d ", root->value);
}공통 패턴
세 가지 깊이 우선 순회는 모두 같은 뼈대를 공유합니다. NULL 기본 사례, 왼쪽 자식에 대한 재귀 호출, 오른쪽 자식에 대한 재귀 호출, 그리고 방문 단계로 이루어집니다.
방문 단계의 위치만 바뀌어 순회의 이름이 달라집니다.
/* visit position decides the order:
* pre : VISIT, left, right
* in : left, VISIT, right
* post : left, right, VISIT
*/중위 순회로 정렬된 값 출력
이 프로그램은 작은 BST를 만들고 중위 순회를 실행하여 정렬된 출력이라는 특성을 보여 줍니다.
삽입 순서와 관계없이 값은 가장 작은 것부터 가장 큰 것까지 출력됩니다.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
if(!r) return cn(v);
if(v<r->value) r->left=insert(r->left,v);
else if(v>r->value) r->right=insert(r->right,v);
return r;
}
void in_order(Node *r){ if(!r) return; in_order(r->left); printf("%d ", r->value); in_order(r->right); }
int main(void){
Node *root=NULL;
int d[]={10,5,15,3,7,12};
for(int i=0;i<6;i++) root=insert(root,d[i]);
in_order(root);
printf("\n");
return 0;
}세 가지 순서 비교
루트가 10이고 왼쪽이 5, 오른쪽이 15인 트리에서는 출력이 서로 다릅니다.
전위 순회는 10 5 15를 출력합니다. 중위 순회는 5 10 15를 출력합니다. 후위 순회는 5 15 10을 출력합니다. 노드 값은 같고 방문 시점만 달라집니다.
/* 10
* / \
* 5 15
* pre : 10 5 15
* in : 5 10 15
* post: 5 15 10
*/레벨 순회
너비 우선 순회 또는 레벨 순회는 위에서 아래로 한 레벨씩 노드를 방문합니다. 이 순회는 자연스럽게 재귀로 구현되지 않으며 큐를 사용합니다.
루트를 큐에 넣은 다음 노드를 반복해서 꺼내 출력하고, 그 자식들을 큐에 넣습니다.
void level_order(Node *root) {
if (!root) return;
Node *queue[100];
int head = 0, tail = 0;
queue[tail++] = root;
while (head < tail) {
Node *n = queue[head++];
printf("%d ", n->value);
if (n->left) queue[tail++] = n->left;
if (n->right) queue[tail++] = n->right;
}
}순회가 실제 작업을 수행하는 방식
순회는 단순히 출력하는 작업뿐 아니라 모든 노드를 처리해야 하는 모든 연산의 틀이 됩니다.
방문 단계를 값의 합을 계산하거나 최댓값을 찾거나 노드를 복사하는 단계로 바꾸면 같은 구조로 작업을 수행할 수 있습니다.
int sum_tree(Node *root) {
if (root == NULL) return 0;
return root->value
+ sum_tree(root->left)
+ sum_tree(root->right);
}순회 비용
모든 순회는 각 노드를 한 번씩 방문하므로 노드 수인 n에 비례하는 시간이 걸립니다.
재귀에는 트리 높이에 비례하는 스택 공간이 필요합니다. 트리가 균형 잡혀 있으면 log(n)이고, 최악의 경우에는 n입니다.
세 가지 순서를 한 번에
이 프로그램은 같은 트리에 대해 전위 순회, 중위 순회, 후위 순회를 출력하므로 결과를 나란히 비교할 수 있습니다.
출력 호출의 위치만 바뀌어 결과 시퀀스가 달라지는 모습을 살펴보십시오.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
void pre(Node *r){ if(!r) return; printf("%d ", r->value); pre(r->left); pre(r->right); }
void ino(Node *r){ if(!r) return; ino(r->left); printf("%d ", r->value); ino(r->right); }
void post(Node *r){ if(!r) return; post(r->left); post(r->right); printf("%d ", r->value); }
int main(void){
Node *root = cn(10);
root->left = cn(5); root->right = cn(15);
pre(root); printf("\n");
ino(root); printf("\n");
post(root); printf("\n");
return 0;
}빠른 확인
작업에 맞는 순회를 선택해 보십시오.
복습
깊이 우선 순회는 하나의 재귀 뼈대를 공유하며, 방문 단계의 위치에 따라 전위 순회, 중위 순회, 후위 순회가 됩니다. BST의 중위 순회는 정렬된 출력을 만들고, 후위 순회는 해제할 때 안전한 순서입니다.
레벨 순회는 너비 우선 순회이며 큐를 사용합니다. 세 순회 모두 각 노드를 한 번씩 방문하므로 O(n) 시간이 걸립니다.
자주 묻는 질문
“순회” 강의는 무료인가요?
네 — “순회” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 C Academy 강의 전체를 잠금 해제할 수 있습니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“순회”에서 뭘 배우나요?
중위, 전위, 후위 순회를 배워 보세요. 브라우저에서 직접 실행하는 실습 코드로 C Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
C Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 C Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“순회” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 C Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 C Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.