트리(Tree) 자료구조: 이진 트리와 순회 알고리즘

**트리(Tree)**는 계층적인 관계를 나타내는 대표적인 비선형(Non-linear) 자료구조입니다. 하나의 뿌리(Root) 노드에서 시작하여 나뭇가지처럼 늘어나는 형태를 취합니다.

1. 트리의 용어 및 구조

• 노드 (Node): 트리를 구성하는 데이터 요소.
• 간선 (Edge): 노드와 노드를 연결하는 선.
• 루트 노드 (Root Node): 부모가 없는 최상위 노드.
• 단말 노드 (Leaf Node): 자식이 없는 최하위 노드.
• 서브트리 (Subtree): 하나의 노드와 그 하위 노드들로 구성된 부분 트리.
• 차수 (Degree): 각 노드가 가진 자식 노드의 수.
• 높이 (Height) / 깊이 (Depth): 루트에서 특정 노드까지의 경로 길이 및 최대 레벨.

2. 이진 트리(Binary Tree)의 유형

모든 노드의 차수(자식 노드 수)가 2 이하인 트리를 이진 트리라고 합니다.

3. 이진 트리 순회(Traversal) 알고리즘

순회란 트리의 모든 노드를 중복 없이 방문하는 방법입니다.

class Node:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None

# 1. 전위 순회 (Preorder: V -> L -> R)
def preorder(node):
    if node:
        print(node.val, end=' ')
        preorder(node.left)
        preorder(node.right)

# 2. 중위 순회 (Inorder: L -> V -> R)
def inorder(node):
    if node:
        inorder(node.left)
        print(node.val, end=' ')
        inorder(node.right)

# 3. 후위 순회 (Postorder: L -> R -> V)
def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.val, end=' ')

4. 트리의 실무 활용

1. 파일 시스템: 디렉터리와 파일의 계층적 구조 표현.
2. 이진 탐색 트리 (BST): 빠르고 효율적인 데이터 검색 및 관리.
3. 수식 트리 (Expression Tree): 연산자와 피연산자를 트리로 구성하여 후위 표기법 계산에 사용.
4. 우선순위 큐 (Heap): Complete Binary Tree 구조 기반의 힙 연산.

5. 자주 묻는 질문 (Q&A)

Q. 이진 탐색 트리(BST)에서 중위 순회를 수행하면 어떤 결과가 나오나요? A. 이진 탐색 트리는 왼쪽 자식 < 부모 < 오른쪽 자식 관계를 가지므로, 중위 순회(Inorder Traversal)를 하면 오름차순으로 정렬된 데이터를 얻을 수 있습니다.