[자료구조] 트리(Tree)의 기본 구조와 순회 방법

스택, 큐, 덱은 모두 데이터가 일직선으로 나열되는 선형(Linear) 자료구조입니다. 데이터 사이의 관계가 단순히 앞뒤로만 연결됩니다. 그런데 현실의 데이터는 대부분 이보다 복잡한 구조를 가집니다. 파일 시스템의 폴더 계층, 조직도, HTML DOM, 데이터베이스 인덱스 등 이런 구조들은 상하 관계와 계층이 존재하고 하나의 부모가 여러 자식을 가질 수 있습니다. 트리(Tree)는 바로 이 계층적 관계를 표현하기 위한 비선형(Non-linear) 자료구조입니다. 이 글에서는 트리의 구성 요소와 핵심 용어, 이진 트리의 종류, 그리고 트리를 탐색하는 네 가지 순회 방법을 정리합니다.

 

1. 트리(Tree)란 무엇인가

트리는 노드(Node)와 엣지(Edge)로 구성된 계층적 자료구조입니다. 이름 그대로 나무를 거꾸로 뒤집어 놓은 형태와 유사하며, 최상위에 루트(Root)가 있고 아래로 가지를 뻗어나가는 구조입니다.

트리를 선형 자료구조와 구분 짓는 핵심 특성은 다음 세 가지입니다.

첫째, 단 하나의 루트 노드가 존재합니다.

둘째, 부모-자식 관계가 있어 모든 노드는 루트에서 도달 가능합니다.

셋째, 사이클(cycle)이 없습니다. 즉, 순환하는 경로가 존재하지 않습니다. 반대로 말하면 사이클이 있거나 루트가 여러 개라면 트리가 아닙니다. 트리는 정의상 비순환 연결 그래프(Acyclic Connected Graph) 입니다.

 

2. 트리의 핵심 용어 정리

트리를 다루려면 용어 정리가 먼저입니다.

용어	설명
노드 (Node)	트리를 구성하는 기본 단위. 데이터를 저장합니다.
엣지 (Edge)	노드와 노드를 연결하는 선. 부모-자식 관계를 나타냅니다.
루트 (Root)	트리의 최상위 노드. 부모가 없습니다.
부모 (Parent)	자식 노드를 가진 상위 노드.
자식 (Child)	부모 노드 아래에 연결된 하위 노드.
형제 (Sibling)	같은 부모를 가진 노드들.
리프 (Leaf)	자식이 없는 말단 노드. 단말 노드라고도 합니다.
내부 노드 (Internal Node)	자식이 하나 이상 있는 노드.
깊이 (Depth)	루트에서 해당 노드까지의 엣지 수.
높이 (Height)	해당 노드에서 가장 깊은 리프까지의 엣지 수. 트리의 높이는 루트의 높이.
레벨 (Level)	루트를 레벨 1로 시작해 아래로 내려갈수록 1씩 증가.
차수 (Degree)	한 노드가 가진 자식 노드의 수.
서브트리 (Subtree)	특정 노드를 루트로 하는 부분 트리.

 

3. 이진 트리(Binary Tree)의 종류

이진 트리는 모든 노드의 자식이 최대 2개인 트리입니다. 자식을 왼쪽 자식(left child)과 오른쪽 자식(right child)으로 구분합니다. BST, 힙, AVL 트리 등 CS에서 다루는 트리 자료구조의 대부분이 이진 트리 기반입니다.

 

편향 이진 트리 (Skewed Binary Tree) 모든 노드가 한쪽 방향으로만 자식을 가지는 형태입니다. 사실상 연결 리스트와 같은 구조가 되어, 탐색 시 O(n)이라는 최악의 성능이 나옵니다. 이 문제를 해결하기 위해 AVL 트리, 레드-블랙 트리 같은 균형 트리가 등장합니다.

 

포화 이진 트리 (Perfect Binary Tree) 모든 레벨이 완전히 채워진 이진 트리입니다. 리프 노드가 모두 같은 레벨에 있으며, 노드 개수는 항상 2ⁿ - 1개입니다. (n = 레벨 수)

 

완전 이진 트리 (Complete Binary Tree) 마지막 레벨을 제외한 모든 레벨이 꽉 차 있고, 마지막 레벨은 왼쪽부터 순서대로 채워진 형태입니다. 힙(Heap) 자료구조가 완전 이진 트리로 구현됩니다.

 

 

4. 트리 순회(Tree Traversal) — 4가지 방법

순회(Traversal)란 트리 안의 모든 노드를 빠짐없이, 정해진 순서에 따라 한 번씩 방문하는 과정입니다. 배열은 인덱스로 순서가 명확하지만, 트리는 방문 순서를 어떻게 결정하느냐에 따라 결과가 완전히 달라집니다.

순회의 핵심은 딱 한 가지 질문입니다. "루트(Root)를 언제 방문하느냐?"

• 루트를 먼저 방문 → 전위 순회
• 루트를 중간에 방문 → 중위 순회
• 루트를 마지막에 방문 → 후위 순회
• 레벨 순서대로 방문 → 레벨 순회

전위·중위·후위는 재귀(Recursion) 기반, 레벨 순회는 큐(Queue) 기반으로 구현됩니다.

 

 

4.1 전위 순회 (Pre-order) — Root → Left → Right

루트를 가장 먼저 방문하고 이후 왼쪽 서브트리 → 오른쪽 서브트리 순서로 재귀적으로 탐색합니다.

방문 규칙 : ① 현재 노드 방문 → ② 왼쪽 서브트리 전위 순회 → ③ 오른쪽 서브트리 전위 순회

def preorder(node):
    if node is None:
        return
    print(node.val)       # ① 현재 노드 방문
    preorder(node.left)   # ② 왼쪽 서브트리
    preorder(node.right)  # ③ 오른쪽 서브트리

 

활용 : 트리 구조를 그대로 복사할 때, 디렉터리 구조 탐색(부모 폴더를 먼저 처리), 전위 표기법(prefix notation) 계산에 사용됩니다.

.

4.2 중위 순회 (In-order) — Left → Root → Right

왼쪽 서브트리를 먼저 탐색하고, 루트를 중간에 방문한 뒤 오른쪽 서브트리를 탐색합니다.

방문 규칙 : ① 왼쪽 서브트리 중위 순회 → ② 현재 노드 방문 → ③ 오른쪽 서브트리 중위 순회

def inorder(node):
    if node is None:
        return
    inorder(node.left)    # ① 왼쪽 서브트리
    print(node.val)       # ② 현재 노드 방문
    inorder(node.right)   # ③ 오른쪽 서브트리

 

활용 : 이진 탐색 트리(BST)에서 중위 순회를 수행하면 데이터가 오름차순으로 정렬되어 출력됩니다. 이 특성이 BST의 핵심 강점 중 하나이며, 정렬된 데이터를 순서대로 가져올 때 그대로 활용됩니다.

 

4.3 후위 순회 (Post-order) — Left → Right → Root

왼쪽 서브트리와 오른쪽 서브트리를 모두 탐색한 후, 루트를 마지막에 방문합니다.

방문 규칙 : ① 왼쪽 서브트리 후위 순회 → ② 오른쪽 서브트리 후위 순회 → ③ 현재 노드 방문

def postorder(node):
    if node is None:
        return
    postorder(node.left)  # ① 왼쪽 서브트리
    postorder(node.right) # ② 오른쪽 서브트리
    print(node.val)       # ③ 현재 노드 방문

 

활용 : 자식 노드를 먼저 처리해야 부모를 처리할 수 있는 구조에 사용됩니다. 대표적으로 파일 시스템에서 폴더 삭제(하위 파일부터 삭제 후 상위 폴더 삭제), 후위 표기법 수식 계산, 트리 메모리 해제 등에 활용됩니다.

 

4.4 레벨 순회 (Level-order) — BFS 기반

 

 

루트에서 시작해 같은 레벨(깊이)의 노드들을 왼쪽에서 오른쪽으로 모두 방문한 뒤 다음 레벨로 내려가는 방식입니다. 너비 우선 순회(Breadth-First Traversal, BFT)라고도 합니다. 앞의 세 순회가 스택 기반 재귀로 구현되는 것과 달리 레벨 순회는 큐(Queue) 를 사용해 구현합니다.

방문 순서 : A → B → C → D → E → F → G

from collections import deque

def level_order(root):
    if root is None:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()  # front에서 꺼냄
        print(node.val)
        if node.left:
            queue.append(node.left)   # rear에 추가
        if node.right:
            queue.append(node.right)

 

큐에서 노드를 꺼낼 때마다 해당 노드의 자식들을 순서대로 큐에 넣습니다. FIFO 구조 덕분에 자연스럽게 레벨 순서가 보장됩니다.

활용 : BFS 탐색, 트리의 최소 깊이 계산, 레벨별 데이터 집계에 사용됩니다.