🌳 트리 (Tree) 기초 완벽 정리

---

✅ 트리란?

트리는 데이터를 계층적으로 표현하는 비선형 자료구조다.
선형 구조인 배열이나 연결 리스트와 달리, 하나의 노드가 여러 개의 하위 노드를 가질 수 있다.

트리는 사이클이 없는 방향 그래프(DAG)의 일종이며, 루트에서 다른 노드로 가는 경로는 반드시 하나뿐이다.
파일 시스템, 조직도, HTML DOM 구조 등이 트리의 대표적인 예시다.

---

📌 주요 용어 정리

용어	설명
루트(Root)	트리의 시작점이 되는 노드
노드(Node)	데이터를 담고 있는 요소
간선(Edge)	노드 간의 연결선
부모(Parent)	다른 노드를 가리키는 노드
자식(Child)	부모에 의해 연결된 노드
리프(Leaf)	자식이 없는 노드
서브트리(Subtree)	어떤 노드를 루트로 하는 하위 트리
깊이(Depth)	루트에서 특정 노드까지의 거리
높이(Height)	특정 노드에서 가장 깊은 리프 노드까지의 거리

---

✅ 트리의 특징

• 루트 노드가 하나이며, 하나의 부모만 가질 수 있다.
• n개의 노드는 항상 n - 1개의 간선을 가진다.
• 순환(Cycle)이 존재하지 않는다.
• 노드 간의 경로는 유일하다.

---

✅ 이진 트리 (Binary Tree)

이진 트리는 각 노드가 최대 2개의 자식 노드를 가지는 트리다.
왼쪽 자식 노드는 left, 오른쪽 자식 노드는 right로 구분된다.

    1
   / \
  2   3
 / \    
4   5  

---

✅ 트리 순회(Tree Traversal)

트리의 모든 노드를 특정 순서로 방문하는 방법을 트리 순회라고 한다.
총 4가지 기본 방식이 있으며, 순회 방식에 따라 결과가 달라진다.

🔹 전위 순회 (Preorder)

• 방문 순서: 현재 노드 → 왼쪽 자식 → 오른쪽 자식
• 예시 출력: 1 2 4 5 3

🔹 중위 순회 (Inorder)

• 방문 순서: 왼쪽 자식 → 현재 노드 → 오른쪽 자식
• 예시 출력: 4 2 5 1 3
• 이진 탐색 트리에서 오름차순 결과를 얻는 데 사용된다.

🔹 후위 순회 (Postorder)

• 방문 순서: 왼쪽 자식 → 오른쪽 자식 → 현재 노드
• 예시 출력: 4 5 2 3 1

🔹 레벨 순서 순회 (Level-order)

• BFS 방식
• 방문 순서: 같은 레벨을 위에서 아래로, 왼쪽에서 오른쪽으로
• 예시 출력: 1 2 3 4 5

---

✅ 파이썬 코드 예제

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

# 트리 구성
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

# 전위 순회
def preorder(node):
    if node:
        print(node.key, end=' ')
        preorder(node.left)
        preorder(node.right)

# 중위 순회
def inorder(node):
    if node:
        inorder(node.left)
        print(node.key, end=' ')
        inorder(node.right)

# 후위 순회
def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.key, end=' ')

# 레벨 순서 순회
from collections import deque

def level_order(root):
    if not root:
        return
    q = deque([root])
    while q:
        node = q.popleft()
        print(node.key, end=' ')
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

# 실행 예시
print("Preorder:")
preorder(root)
print("\nInorder:")
inorder(root)
print("\nPostorder:")
postorder(root)
print("\nLevel-order:")
level_order(root)

---

🎯 마무리 요약

• 트리는 계층적이고 비선형적인 구조로, 사이클이 없는 방향 그래프이다.
• 이진 트리는 각 노드가 최대 2개의 자식을 가지며, 다양한 탐색 알고리즘의 기초가 된다.
• 트리 순회는 전위, 중위, 후위, 레벨 순서 4가지가 있으며, 문제 상황에 따라 적절히 선택하여 사용해야 한다.
• 트리를 정확히 이해하는 것은 BST, AVL, 힙, 트라이, B-트리 등 고급 자료구조로 나아가기 위한 필수 과정이다.