비선형 자료 구조는 데이터가 단순히 일렬로 연결되지 않고 계층적 관계나 복잡한 연결 관계를 가지는 구조입니다. 대표적인 비선형 자료 구조에는 트리와 그래프가 있으며, 파일 시스템·조직도·네트워크·검색 구조처럼 데이터 사이의 관계를 표현하는 데 사용됩니다.
이 장에서는 트리의 기본 구조와 용어, 이진 트리의 종류, 전위·중위·후위 순회를 정리합니다. 이어서 수식의 전위·중위·후위 표기법과 그래프의 구성 요소, 인접 행렬, 신장 트리, 무방향 그래프의 최대 간선 수와 순환 복잡도를 살펴봅니다.
이 장의 핵심 내용
- 트리는 노드와 간선으로 이루어진 계층적 비선형 자료 구조입니다.
- 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다.
- 전위 순회는 루트→왼쪽→오른쪽, 중위 순회는 왼쪽→루트→오른쪽, 후위 순회는 왼쪽→오른쪽→루트 순서입니다.
- 전위 표기법은 연산자를 앞에, 후위 표기법은 연산자를 뒤에 배치합니다.
- 그래프는 정점과 간선의 집합으로 이루어진 비선형 자료 구조입니다.
- 인접 행렬은 정점 사이의 연결 여부를 행과 열의 값으로 표현합니다.
- 정점이 n개인 단순 무방향 완전 그래프의 최대 간선 수는 n(n−1)/2입니다.
- 신장 트리는 모든 정점을 포함하면서 순환이 없는 부분 그래프입니다.
비선형 자료 구조란 무엇인가?
비선형 자료 구조는 하나의 데이터가 여러 데이터와 연결될 수 있는 자료 구조입니다. 데이터가 앞뒤 순서로 나열되는 리스트·스택·큐와 달리 계층 구조나 망형 구조를 표현할 수 있습니다.
| 구분 | 선형 자료 구조 | 비선형 자료 구조 |
|---|---|---|
| 데이터 관계 | 앞뒤의 순차적 관계 | 계층적 관계 또는 망형 관계 |
| 대표 구조 | 리스트, 스택, 큐, 데크 | 트리, 그래프 |
| 대표 활용 | 순차 처리, 대기열, 함수 호출 | 파일 구조, 검색 구조, 네트워크 |
트리란 무엇인가?
트리(Tree)는 노드와 간선을 이용해 데이터를 계층적으로 표현하는 비선형 자료 구조입니다. 하나의 루트 노드에서 시작하며, 루트를 제외한 각 노드는 하나의 부모 노드와 연결됩니다.
일반적인 트리는 모든 노드가 연결되어 있고 순환이 없습니다. 따라서 두 노드 사이의 단순 경로는 하나만 존재합니다.
계층 구조
루트를 기준으로 부모와 자식 관계가 형성되며, 상위·하위 관계를 표현하기에 적합합니다.
순환이 없는 구조
간선을 따라 이동했을 때 출발한 노드로 다시 돌아오는 순환이 존재하지 않습니다.
트리의 주요 용어
| 용어 | 의미 |
|---|---|
| 노드(Node) | 트리를 구성하는 데이터 요소 |
| 간선(Edge) | 노드와 노드를 연결하는 선 |
| 루트 노드(Root Node) | 부모가 없는 최상위 노드 |
| 부모 노드(Parent Node) | 특정 노드의 바로 위 단계에 연결된 노드 |
| 자식 노드(Child Node) | 특정 노드의 바로 아래 단계에 연결된 노드 |
| 형제 노드(Sibling Node) | 같은 부모를 가지는 노드 |
| 조상 노드(Ancestor Node) | 특정 노드에서 루트까지의 경로에 있는 상위 노드 |
| 후손 노드(Descendant Node) | 특정 노드 아래에 연결된 모든 하위 노드 |
| 단말 노드(Leaf Node) | 자식이 없는 노드 |
| 노드의 차수(Degree) | 해당 노드가 가진 자식 노드의 수 |
| 트리의 차수 | 트리에 포함된 노드의 차수 중 가장 큰 값 |
| 레벨(Level) | 루트를 기준으로 노드가 위치한 단계 |
| 깊이(Depth) | 루트에서 특정 노드까지의 경로 길이 |
| 높이(Height) | 특정 노드에서 가장 먼 단말 노드까지의 경로 길이 |
용어 주의: 깊이와 높이를 같은 뜻으로 단순화하는 자료도 있지만 엄밀히는 서로 다릅니다. 깊이는 루트에서 특정 노드까지, 높이는 특정 노드에서 가장 먼 단말 노드까지의 경로 길이입니다.
이진 트리란 무엇인가?
이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다. 두 자식은 왼쪽 자식과 오른쪽 자식으로 구분합니다.
레벨별 최대 노드 수
루트 노드를 레벨 1로 정의하면 레벨 k에서 가질 수 있는 최대 노드 수는 다음과 같습니다.
레벨 1부터 레벨 k까지 모든 노드가 채워졌을 때 전체 최대 노드 수는 다음과 같습니다.
이진 트리의 종류
| 종류 | 의미 | 핵심 특징 |
|---|---|---|
| 정 이진 트리 Full Binary Tree | 모든 노드가 자식을 0개 또는 2개 가지는 이진 트리 | 자식이 하나뿐인 노드가 없음 |
| 포화 이진 트리 Perfect Binary Tree | 모든 내부 노드가 두 자식을 가지며 단말 노드가 같은 레벨에 있는 트리 | 모든 레벨이 완전히 채워짐 |
| 완전 이진 트리 Complete Binary Tree | 마지막 레벨을 제외한 레벨이 채워지고 마지막 레벨은 왼쪽부터 채워지는 트리 | 힙의 기본 구조 |
| 편향 이진 트리 Skewed Binary Tree | 노드가 한쪽 방향으로만 이어지는 이진 트리 | 선형 구조와 비슷한 형태 |
시험 자료의 용어 차이: 일부 자료에서는 포화 이진 트리를 정 이진 트리로 표기하기도 합니다. 실제 문제에서는 그림과 정의를 함께 확인해야 합니다.
이진 트리는 어떻게 순회할까?
트리 순회(Tree Traversal)는 트리의 모든 노드를 일정한 순서로 한 번씩 방문하는 과정입니다. 깊이 우선 방식의 이진 트리 순회는 루트를 방문하는 시점에 따라 전위·중위·후위 순회로 구분합니다.
| 순회 방식 | 방문 순서 | 루트 방문 시점 |
|---|---|---|
| 전위 순회 Preorder | 루트 → 왼쪽 부분 트리 → 오른쪽 부분 트리 | 부분 트리보다 먼저 |
| 중위 순회 Inorder | 왼쪽 부분 트리 → 루트 → 오른쪽 부분 트리 | 왼쪽과 오른쪽 사이 |
| 후위 순회 Postorder | 왼쪽 부분 트리 → 오른쪽 부분 트리 → 루트 | 부분 트리를 모두 처리한 뒤 |
순회 순서 계산 사례
A를 루트로 하고, A의 왼쪽 자식이 B, 오른쪽 자식이 C이며, B의 자식이 D와 E, C의 자식이 F와 G인 이진 트리를 가정합니다.
| 순회 방식 | 순회 결과 |
|---|---|
| 전위 순회 | A → B → D → E → C → F → G |
| 중위 순회 | D → B → E → A → F → C → G |
| 후위 순회 | D → E → B → F → G → C → A |
전위·중위·후위 표기법이란 무엇인가?
수식 표기법은 연산자와 피연산자의 배치 순서에 따라 전위·중위·후위 표기법으로 구분합니다. 수식 트리를 전위 순회하면 전위 표기식, 중위 순회하면 중위 표기식, 후위 순회하면 후위 표기식이 됩니다.
| 표기 방식 | 배치 순서 | 예시 |
|---|---|---|
| 전위 표기법 Prefix | 연산자 → 피연산자 → 피연산자 | +AB |
| 중위 표기법 Infix | 피연산자 → 연산자 → 피연산자 | A+B |
| 후위 표기법 Postfix | 피연산자 → 피연산자 → 연산자 | AB+ |
중위 수식을 전위·후위 수식으로 변환하기
중위 수식: (A×B)+(C×D)
| 구분 | 결과 |
|---|---|
| 전위 표기 | + × A B × C D |
| 후위 표기 | A B × C D × + |
그래프란 무엇인가?
그래프(Graph)는 정점(Vertex)의 집합과 정점 사이를 연결하는 간선(Edge)의 집합으로 이루어진 비선형 자료 구조입니다. 트리보다 일반적인 연결 구조이며, 하나의 정점이 여러 정점과 자유롭게 연결될 수 있습니다.
| 구성 요소 | 의미 |
|---|---|
| 정점(Vertex) | 그래프를 구성하는 데이터 또는 위치 |
| 간선(Edge) | 두 정점 사이의 연결 관계 |
| 경로(Path) | 간선을 따라 정점 사이를 이동하는 순서 |
| 순환(Cycle) | 출발 정점에서 시작해 다시 같은 정점으로 돌아오는 경로 |
| 인접(Adjacency) | 두 정점이 하나의 간선으로 직접 연결된 관계 |
그래프는 어떻게 분류할까?
| 종류 | 의미 |
|---|---|
| 방향 그래프 | 간선에 방향이 지정된 그래프 |
| 무방향 그래프 | 간선에 방향이 없는 그래프 |
| 완전 그래프 | 서로 다른 모든 정점 쌍이 간선으로 연결된 그래프 |
| 부분 그래프 | 원래 그래프의 일부 정점과 간선으로 구성된 그래프 |
| 가중 그래프 | 간선에 거리·비용·시간 등의 값이 부여된 그래프 |
무방향 그래프의 최대 간선 수
정점이 n개인 단순 무방향 완전 그래프에서는 서로 다른 두 정점의 모든 조합이 하나의 간선을 이룹니다.
적용 조건: 위 공식은 자기 자신으로 연결되는 루프와 중복 간선이 없는 단순 무방향 그래프에 적용합니다.
신장 트리란 무엇인가?
신장 트리(Spanning Tree)는 연결 그래프의 모든 정점을 포함하면서 순환이 없도록 일부 간선만 선택한 부분 그래프입니다.
포함 조건
- 원래 그래프의 모든 정점을 포함
- 모든 정점이 서로 연결됨
- 원래 그래프의 간선만 사용
제외 조건
- 순환이 존재하면 안 됨
- 연결되지 않은 정점이 있으면 안 됨
- 필요 이상의 간선을 포함하지 않음
인접 행렬이란 무엇인가?
인접 행렬(Adjacency Matrix)은 그래프의 정점 사이에 간선이 존재하는지를 행과 열로 표현하는 방식입니다. 정점이 n개라면 n×n 크기의 행렬을 사용합니다.
| 구분 | 방향 그래프 | 무방향 그래프 |
|---|---|---|
| 행렬 값 | i에서 j로 향하는 간선이 있으면 Aij=1 | i와 j 사이에 간선이 있으면 Aij=1 |
| 대칭 여부 | 대칭일 필요가 없음 | Aij=Aji이므로 대칭 행렬 |
| 저장 공간 | 정점 수의 제곱에 비례 | 정점 수의 제곱에 비례 |
| 연결 확인 | 행렬의 한 칸을 확인 | 행렬의 한 칸을 확인 |
순환 복잡도란 무엇인가?
순환 복잡도(Cyclomatic Complexity)는 프로그램의 제어 흐름 그래프에서 선형 독립적인 기본 경로의 수를 나타내는 지표입니다. 하나로 연결된 제어 흐름 그래프에서는 다음 공식을 사용할 수 있습니다.
적용 범위: 위 공식은 하나로 연결된 제어 흐름 그래프를 전제로 합니다. 연결 요소가 여러 개라면 연결 요소의 수를 별도로 고려해야 합니다.
트리와 그래프는 무엇이 다를까?
| 비교 항목 | 트리 | 그래프 |
|---|---|---|
| 구조 | 루트를 중심으로 한 계층 구조 | 정점 사이의 일반적인 연결 구조 |
| 루트 | 하나의 루트가 존재 | 반드시 존재하지 않음 |
| 순환 | 존재하지 않음 | 존재할 수 있음 |
| 경로 | 두 노드 사이의 단순 경로가 하나 | 경로가 없거나 여러 개일 수 있음 |
| 간선 수 | 노드가 n개이면 n−1개 | 그래프 종류에 따라 달라짐 |
시험에서 자주 혼동되는 개념
노드의 차수와 트리의 차수
노드의 차수는 해당 노드의 자식 수이고, 트리의 차수는 모든 노드의 차수 중 최댓값입니다.
전위 순회와 전위 표기
전위 순회는 루트를 먼저 방문하고, 수식 트리를 전위 순회하면 연산자가 앞에 오는 전위 표기식이 됩니다.
완전 그래프와 완전 이진 트리
완전 그래프는 모든 정점 쌍이 연결된 그래프이고, 완전 이진 트리는 마지막 레벨을 왼쪽부터 채우는 이진 트리입니다.
그래프와 신장 트리
그래프에는 순환이 존재할 수 있지만, 신장 트리는 모든 정점을 연결하면서 순환을 제거한 트리 구조입니다.
이번 장 핵심 요약
- 트리와 그래프는 비선형 자료 구조입니다.
- 트리는 하나의 루트에서 시작하고 순환이 없습니다.
- 단말 노드는 자식이 없는 노드입니다.
- 노드의 차수는 자식 수이고, 트리의 차수는 노드 차수의 최댓값입니다.
- 이진 트리는 각 노드가 최대 두 개의 자식을 가집니다.
- 전위는 루트→왼쪽→오른쪽, 중위는 왼쪽→루트→오른쪽, 후위는 왼쪽→오른쪽→루트입니다.
- 전위 표기는 연산자가 앞에, 후위 표기는 연산자가 뒤에 옵니다.
- 단순 무방향 완전 그래프의 최대 간선 수는 n(n−1)/2입니다.
- 신장 트리의 간선 수는 정점 수보다 하나 적습니다.
- 무방향 그래프의 인접 행렬은 대칭입니다.
복습 문제
트리와 그래프는 선형 구조와 비선형 구조 중 어디에 해당할까?
비선형 자료 구조에 해당합니다.
자식 노드가 없는 노드는 무엇이라고 할까?
단말 노드 또는 리프 노드라고 합니다.
루트→왼쪽→오른쪽 순서로 방문하는 순회 방식은?
전위 순회입니다.
왼쪽→루트→오른쪽 순서로 방문하는 순회 방식은?
중위 순회입니다.
왼쪽→오른쪽→루트 순서로 방문하는 순회 방식은?
후위 순회입니다.
(A×B)+(C×D)의 전위 표기식은?
+ × A B × C D입니다.
(A×B)+(C×D)의 후위 표기식은?
A B × C D × +입니다.
정점이 6개인 단순 무방향 완전 그래프의 최대 간선 수는?
6×5÷2이므로 15개입니다.
정점이 8개인 신장 트리의 간선 수는?
7개입니다.
참고자료
- 학습 범위 — 사무자동화산업기사 제1과목 사무자동화 시스템, 비선형 자료 구조
- Q-Net — 사무자동화산업기사 종목별 상세정보 및 출제기준
- NIST Dictionary of Algorithms and Data Structures — Tree Traversal
- NIST — Preorder Traversal
- NIST — In-order Traversal
- NIST — Postorder Traversal
이 글은 사무자동화산업기사 시험 범위에 포함된 트리와 그래프, 이진 트리 순회, 수식 표기법과 인접 행렬을 이해하고 복습할 수 있도록 재구성한 정리입니다. 트리의 레벨·깊이와 이진 트리 종류의 명칭은 자료에 따라 다르게 사용될 수 있으므로 실제 시험에서는 문제에 제시된 정의와 최신 Q-Net 출제기준을 함께 확인해야 합니다.