C언어 이진 트리 (Binary Tree)
요약
C언어 이진 트리의 노드 구조체 정의와 전위/중위/후위 재귀 순회를 알아봅니다. 자료구조와 재귀를 함께 다루는 정보처리기사 실기 대비 핵심 개념을 정리합니다.
이진 트리 핵심 정리
| 개념 | 설명 | 예시 |
|---|---|---|
| 이진 트리 | 각 노드가 최대 2개의 자식(left, right)을 가지는 트리 | 부모 → 왼쪽/오른쪽 자식 |
| 노드(Node) | 데이터 + 두 자식 포인터를 가진 구조체 | int data, Node* left, Node* right |
| 루트(root) | 트리의 시작 노드 (부모 없음) | 트리의 가장 위 노드 |
| 리프(leaf) | 자식이 없는 노드 | left == NULL && right == NULL |
| 전위 순회 | Root → Left → Right | 부모를 먼저 방문 |
| 중위 순회 | Left → Root → Right | 왼쪽부터 차례로 |
| 후위 순회 | Left → Right → Root | 부모를 마지막에 방문 |
이진 트리란? 쌩기초
이진 트리 (Binary Tree)는 각 노드가 최대 2개의 자식 노드(왼쪽, 오른쪽)를 가지는 자료구조입니다.
연결 리스트는 한 노드가 다음 노드 하나만 가리키지만, 이진 트리는 두 개의 노드를 가리킵니다. 구조체와 포인터를 함께 사용하므로 두 개념이 익숙하지 않다면 먼저 읽고 돌아오세요.
| 용어 | 의미 | 그림 예시 |
|---|---|---|
| 루트(root) | 트리의 가장 위 노드 | 1 |
| 부모(parent) | 자식을 가진 노드 | 2는 4, 5의 부모 |
| 자식(child) | 부모 아래 노드 | 4, 5는 2의 자식 |
| 리프(leaf) | 자식이 없는 노드 | 4, 5, 6 |
노드 구조체 정의 쌩기초
이진 트리의 노드는 데이터 + 왼쪽 자식 포인터 + 오른쪽 자식 포인터 3개의 멤버를 가집니다.
struct Node* left와 struct Node* right는 자기 자신과 같은 타입(struct Node)을 가리키는 포인터입니다. 이렇게 자기 자신과 같은 타입의 포인터를 멤버로 가지는 것을 자기참조 구조체라고 합니다.
노드 만들기 (정적 선언)
가장 단순한 방법은 노드를 변수로 선언하고 직접 연결하는 것입니다. 위 그림(루트 1, 자식 2/3, 2의 자식 4/5, 3의 오른쪽 자식 6)을 코드로 만들면 다음과 같습니다.
구조체 초기화(중괄호 {...}로 멤버 값을 한 번에 채우는 것) 순서는 멤버 선언 순서(data, left, right)와 일치해야 합니다. 자식이 없으면 NULL을 넣어 "여기 아래로 더 이상 자식 노드가 없다"는 표시를 합니다.
노드 만들기 (동적 할당)
정적 선언은 개념 이해용으로 살펴봤고, 이제부터는 실기에서 자주 쓰는 동적 할당 방식을 배웁니다. 두 방식 모두 위와 똑같은 트리를 만들며, 실기에서는 동적 할당이 표준입니다. malloc으로 동적 할당해 노드를 만드는 패턴을 숙지해 두세요.
malloc은 노드 크기만큼 메모리를 할당하고 그 시작 주소를 반환합니다. 반환값을 struct Node*로 형변환한 뒤 멤버를 초기화합니다.
위 정적 선언과 똑같은 트리(루트 1, 자식 2/3, 2의 자식 4/5, 3의 오른쪽 자식 6)가 만들어집니다.
화살표 연산자 ->는 포인터가 가리키는 구조체의 멤버에 접근합니다. root->left->left는 "root의 왼쪽 자식의 왼쪽 자식"을 의미합니다.
트리 순회 기초
순회(Traversal)는 트리의 모든 노드를 한 번씩 방문하는 것입니다. 여기서 "방문"이란 그 노드의 데이터를 출력하거나 처리하는 것을 말합니다. 이진 트리에서는 부모와 두 자식의 방문 순서에 따라 전위·중위·후위 3가지 순회가 있습니다.
| 순회 | 방문 순서 | 영문 |
|---|---|---|
| 전위 순회 | Root → Left → Right | preorder |
| 중위 순회 | Left → Root → Right | inorder |
| 후위 순회 | Left → Right → Root | postorder |
각 순회는 재귀함수로 구현하며, 기저 조건(재귀를 멈추는 종료 지점)은 root == NULL 입니다. 리프 노드의 left나 right(NULL)를 따라간 직후 preorder(NULL)이 호출되는 순간 즉시 return합니다.
전위 순회 (preorder) 기초
부모(Root)를 먼저 방문하고, 왼쪽 자식, 오른쪽 자식 순서로 재귀 호출합니다.
위 트리(루트=1)에서 preorder(root)를 호출하면 다음 순서로 노드를 방문합니다.
중위 순회 (inorder) 기초
왼쪽 자식을 먼저 끝까지 방문한 뒤 부모를 방문하고, 마지막으로 오른쪽 자식을 방문합니다.
같은 트리에서 inorder(root) 호출 결과는 다음과 같습니다.
후위 순회 (postorder) 기초
왼쪽 자식과 오른쪽 자식을 모두 방문한 뒤 부모를 마지막으로 방문합니다.
같은 트리에서 postorder(root) 호출 결과는 다음과 같습니다.
재귀 호출 추적하기 심화
순회 결과만 외우지 말고, 재귀 호출이 어떻게 펼쳐지는지 직접 따라가 봅시다. 전위 순회를 예로 듭니다.
함수 호출이 기저 조건(NULL)에 도달할 때까지 펼쳐집니다. 기저 조건에 도달하면 자기를 호출한 함수로 돌아가 다음 줄을 실행합니다.
들여쓰기 트리를 위에서 아래로 읽으면 함수가 실제로 실행되는 시간 순서와 같습니다(재귀가 깊이 우선으로 펼쳐지기 때문입니다). 들여쓰기 1칸은 함수 호출 1단계 깊이를 나타냅니다. 각 호출에서 printf가 실행되는 시점을 위에서 아래로 읽으면 출력 순서가 그대로 나옵니다: 1 2 4 5 3 6.
순회별 출력 비교
같은 트리를 세 가지 순회로 출력한 결과를 비교하면 차이가 한눈에 보입니다.
| 순회 | 출력 순서 | 첫 출력 | 마지막 출력 |
|---|---|---|---|
| 전위(preorder) | 1 2 4 5 3 6 | 루트(1) | 가장 오른쪽 리프(6) |
| 중위(inorder) | 4 2 5 1 3 6 | 가장 왼쪽 리프(4) | 가장 오른쪽 리프(6) |
| 후위(postorder) | 4 5 2 6 3 1 | 가장 왼쪽 리프(4) | 루트(1) |