자료구조 - 트리와 이진트리

트리 (이진트리, 순회, 자료구조)

스택과 큐가 1차원 자료구조였다면, 트리는 한 단계 더 추상화된 계층 구조(hierarchical structure) 자료구조이다. 파일 시스템의 디렉터리, HTML DOM, 회사 조직도, 컴퓨터 게임의 의사 결정 흐름, 운영체제의 프로세스 트리까지 — 실세계의 거의 모든 "포함 관계"가 사실상 트리로 표현되며, 그 위에 정렬·탐색·압축 같은 거의 모든 고급 알고리즘이 얹어진다. 본 글은 정보처리기사 시험 출제 범위와 학교 자료구조 수업 입문 영역을 모두 닿도록 트리 일반·이진 트리·순회 알고리즘을 세심하게 정리한다(출처: 위키백과 — Tree (data structure)). 제가 학교 자료구조 시험에서 가장 자주 틀린 영역이 트리 순회의 결과 추적이었는데, 작은 트리를 직접 종이에 그려 전위·중위·후위 순회를 다 적어 본 후로는 같은 유형의 문제를 거의 자동으로 풀어내게 되었다.

 

트리 자료구조의 기본 개념과 용어

트리(Tree)란 노드(Node)들이 부모-자식 관계로 연결된 계층 구조의 자료구조이다. 일반 그래프와 가장 큰 차이는 사이클이 없고(non-cyclic), 모든 노드가 단 하나의 부모만 가진다는 점이다(루트 제외). 그래프의 일종이지만 이 두 제약 덕분에 훨씬 단순한 알고리즘으로 다룰 수 있고, 검색·정렬·압축 같은 영역에서 압도적인 성능을 만들어 낸다.

트리에서 가장 자주 등장하는 용어를 한 번에 정리하면 다음과 같다. 시험에서 단답형으로 가장 자주 출제되는 항목들이다.

용어	의미
루트(Root)	트리에서 부모가 없는 최상위 노드. 트리당 정확히 1개
부모(Parent) / 자식(Child)	한 간선으로 연결된 두 노드 중 위쪽이 부모, 아래쪽이 자식
형제(Sibling)	같은 부모를 가진 노드들
잎(Leaf) / 단말 노드	자식이 없는 노드
내부(Internal) 노드	자식이 하나 이상 있는 노드
차수(Degree)	한 노드가 가진 자식의 수
트리의 차수	트리 전체에서 한 노드가 가질 수 있는 최대 차수
깊이(Depth)	루트에서 해당 노드까지의 간선 수
높이(Height)	한 노드에서 가장 먼 잎까지의 간선 수
트리의 높이	루트의 높이 = 가장 깊은 잎의 깊이
레벨(Level)	루트가 레벨 0(또는 1) 인지에 따라 책마다 다름

여기서 차수(Degree)란 한 노드가 자기 아래로 가질 수 있는 자식 노드의 개수를 가리키며, 이 수가 트리의 종류를 결정하는 가장 핵심적인 기준이 된다. 차수가 2 이하인 트리를 이진 트리(Binary Tree)라 부르며, 자료구조 수업에서 다루는 거의 모든 트리는 이 이진 트리이다. 솔직히 제 경험상 학교에서 처음 트리를 그릴 때 깊이와 높이를 자주 혼동했는데, "깊이는 위에서 아래로 세고, 높이는 아래에서 위로 센다"라는 한 줄을 외운 후로는 시험 답안에서 헷갈리지 않게 되었다.

이진 트리의 종류와 표현 방법

이진 트리는 모든 노드가 최대 두 개의 자식(좌·우)을 가지는 트리이다. 구조가 단순하면서도 표현력이 강해, 이후 등장하는 거의 모든 트리 변형(BST·힙·세그먼트 트리 등)의 토대가 된다. 정보처리기사 시험에서는 이진 트리의 네 가지 특수 형태가 자주 출제된다.

첫째, 포화 이진 트리(Perfect Binary Tree)는 모든 내부 노드가 두 자식을 갖고 모든 잎이 같은 깊이에 있는 가장 완벽한 형태이다. 높이가 h일 때 노드 수가 정확히 2^(h+1) - 1개이다. 둘째, 완전 이진 트리(Complete Binary Tree)는 마지막 레벨을 제외한 모든 레벨이 꽉 차 있고, 마지막 레벨은 왼쪽부터 채워진 형태이다. 힙(Heap) 자료구조의 표준 구조이며, 배열로 표현해도 빈자리가 거의 없다는 강점이 있다. 셋째, 편향 이진 트리(Skewed Binary Tree)는 한쪽 자식만 가지는 가장 비효율적인 형태로, 사실상 연결리스트와 같다. 넷째, 정 이진 트리(Full Binary Tree)는 모든 내부 노드가 두 자식을 가지는(0 또는 2명) 형태이다. 시험에서는 완전과 정의 차이를 묻는 문제가 가장 자주 출제된다.

이진 트리를 메모리에 표현하는 방법은 크게 두 가지다.

# 방법 1: 노드 기반(포인터/참조)
class Node:
    __slots__ = ("v", "left", "right")
    def __init__(self, v):
        self.v = v; self.left = None; self.right = None

#       1
#      / \
#     2   3
#    / \
#   4   5
root = Node(1)
root.left = Node(2); root.right = Node(3)
root.left.left = Node(4); root.left.right = Node(5)

# 방법 2: 배열 기반 — 완전 이진 트리에 최적
# 부모 인덱스 i → 왼쪽 자식 2i+1, 오른쪽 자식 2i+2
arr = [1, 2, 3, 4, 5, None, None]
def left_child(i):  return 2*i + 1
def right_child(i): return 2*i + 2
def parent(i):      return (i - 1) // 2

배열 기반은 완전 이진 트리(힙)에서 메모리 효율이 가장 좋고, 노드 기반은 임의의 모양 트리(BST·일반 트리)에 적합하다. 학교 시험 답안에서는 "이진 트리는 노드 기반 또는 배열 기반으로 표현하며, 힙처럼 완전 이진 트리는 배열로 표현하면 공간을 절약할 수 있다"라는 한 문장이 표준 표현으로 통한다.

트리 순회 알고리즘 — 전위·중위·후위·레벨

트리 순회(Tree Traversal)는 트리의 모든 노드를 정해진 순서로 한 번씩 방문하는 작업이다. 1차원 자료구조(배열·연결리스트)에서는 순회 순서가 자명했지만, 트리는 부모와 두 자식이 동시에 존재하므로 "어느 노드를 언제 방문할 것인가"가 중요한 결정이 된다. 시험에서 매회 출제되는 핵심 순회는 네 가지다.

# 다음 트리로 네 가지 순회 결과 비교
#         1
#        / \
#       2   3
#      / \   \
#     4   5   6

def preorder(n):    # 전위 — V L R
    if not n: return
    print(n.v, end=" ")
    preorder(n.left); preorder(n.right)

def inorder(n):     # 중위 — L V R
    if not n: return
    inorder(n.left)
    print(n.v, end=" ")
    inorder(n.right)

def postorder(n):   # 후위 — L R V
    if not n: return
    postorder(n.left); postorder(n.right)
    print(n.v, end=" ")

from collections import deque
def levelorder(root):   # 레벨 — BFS
    q = deque([root])
    while q:
        n = q.popleft()
        if n is None: continue
        print(n.v, end=" ")
        q.append(n.left); q.append(n.right)

# 결과
# preorder   : 1 2 4 5 3 6
# inorder    : 4 2 5 1 3 6
# postorder  : 4 5 2 6 3 1
# levelorder : 1 2 3 4 5 6

네 순회의 차이는 결국 "자기 자신(V)을 언제 방문하느냐"의 차이이다. 전위는 자기를 먼저, 중위는 가운데, 후위는 마지막에 방문하며, 레벨은 깊이 우선이 아닌 너비 우선으로 큐를 사용한다. 시험 답안에서는 다음 매핑이 표준 표현으로 통한다.

순회	방문 순서	깊이/너비	대표 응용
전위(Preorder)	V → L → R	깊이 우선	트리 복제, 식 표기식 → 전위식
중위(Inorder)	L → V → R	깊이 우선	BST 정렬 결과, 식 → 중위식
후위(Postorder)	L → R → V	깊이 우선	트리 삭제, 식 → 후위식, 종속성 평가
레벨(Levelorder)	같은 레벨끼리	너비 우선	최단 경로 BFS, 직렬화

여기서 BST(Binary Search Tree)란 왼쪽 서브트리 < 노드 < 오른쪽 서브트리 순서가 보장된 이진 트리를 가리키며, 중위 순회 결과가 항상 오름차순으로 나온다는 결정적인 성질을 가진다. 솔직히 이건 예상 밖이었는데, 제가 BST 위에 중위 순회를 처음 굴려 본 후 출력 결과가 그대로 정렬된 배열이 되는 모습을 보고 나서야 "트리는 단순한 계층 구조가 아니라 정렬·탐색을 동시에 푸는 자료구조"라는 인상을 받아들였다.

마지막으로 시험에서 자주 나오는 표현식 트리(Expression Tree) 변환을 정리하면, 같은 이진 표현식 트리에 세 가지 순회를 굴리면 그대로 전위식(prefix)·중위식(infix)·후위식(postfix) 표기로 변환된다는 사실이 핵심이다. 예를 들어 (A + B) * C라는 식의 트리에 후위 순회를 굴리면 A B + C *라는 후위식이 자동으로 만들어지며, 이 결과가 곧 스택 기반 계산기의 입력이 된다. 트리·스택·식 표기가 한 줄로 연결되는 흐름이며, 자료구조 학습에서 가장 강력한 통합 지점 중 하나이다. 다음 글에서는 이 이진 트리 위에 정렬 규칙을 얹은 BST와, 그 BST가 편향되는 문제를 푸는 균형 트리(AVL·Red-Black)를 이어 다룬다.

---

메타 디스크립션: 트리 자료구조의 기본 용어(루트·깊이·차수), 이진 트리의 네 가지 종류(포화·완전·편향·정), 그리고 전위·중위·후위·레벨 순회 알고리즘을 코드 예시·비교표와 함께 자료구조 입문자 관점에서 세심하게 정리합니다.