트리: 계층 데이터의 수학

        Root (1)
       /        \
      2          3
     / \        / \
    4   5      6   7
   / \
  8   9

용어:
- Root: 최상위 노드 (1)
- Leaf: 자식 없는 노드 (5, 6, 7, 8, 9)
- Parent/Child: 1은 2와 3의 부모
- Sibling: 같은 부모를 가진 노드 (4와 5)
- Depth: 루트로부터의 거리
- Height: 트리의 최대 깊이

# 각 노드가 최대 2개의 자식 (left, right)

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


# 예제 트리 만들기
root = TreeNode(1,
    TreeNode(2,
        TreeNode(4),
        TreeNode(5),
    ),
    TreeNode(3,
        TreeNode(6),
        TreeNode(7),
    ),
)


# 시각화
def print_tree(node, depth=0):
    if node is None:
        return
    print_tree(node.right, depth + 1)
    print('   ' * depth + str(node.value))
    print_tree(node.left, depth + 1)


print_tree(root)

# 1. 전위 순회 (Pre-order): 루트 → 왼쪽 → 오른쪽
def preorder(node):
    if node is None:
        return []
    return [node.value] + preorder(node.left) + preorder(node.right)


# 2. 중위 순회 (In-order): 왼쪽 → 루트 → 오른쪽
def inorder(node):
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)


# 3. 후위 순회 (Post-order): 왼쪽 → 오른쪽 → 루트
def postorder(node):
    if node is None:
        return []
    return postorder(node.left) + postorder(node.right) + [node.value]


# 4. 레벨 순회 (Level-order, BFS)
from collections import deque

def levelorder(root):
    if root is None:
        return []
    result, queue = [], deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.value)
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)
    return result


print(preorder(root))    # [1, 2, 4, 5, 3, 6, 7]
print(inorder(root))     # [4, 2, 5, 1, 6, 3, 7]
print(postorder(root))   # [4, 5, 2, 6, 7, 3, 1]
print(levelorder(root))  # [1, 2, 3, 4, 5, 6, 7]

# 규칙: 왼쪽 < 부모 < 오른쪽
# → 정렬된 데이터 + O(log n) 탐색

class BST:
    def __init__(self):
        self.root = None

    def insert(self, value):
        self.root = self._insert(self.root, value)

    def _insert(self, node, value):
        if node is None:
            return TreeNode(value)
        if value < node.value:
            node.left = self._insert(node.left, value)
        elif value > node.value:
            node.right = self._insert(node.right, value)
        return node

    def search(self, value):
        return self._search(self.root, value)

    def _search(self, node, value):
        if node is None:
            return False
        if node.value == value:
            return True
        if value < node.value:
            return self._search(node.left, value)
        return self._search(node.right, value)


bst = BST()
for v in [50, 30, 70, 20, 40, 60, 80]:
    bst.insert(v)

print(bst.search(40))  # True
print(bst.search(45))  # False

# 중위 순회 = 정렬된 결과
print(inorder(bst.root))  # [20, 30, 40, 50, 60, 70, 80]

✅ 균형 BST           ❌ 불균형 BST
       4               1
      / \               \
     2   6               2
    / \ / \               \
   1  3 5  7              3
                            \
                             4 ...
                              \
                               7

균형: 검색 O(log n)
불균형: 검색 O(n) — 사실상 연결 리스트
→ AVL, Red-Black 트리 등 자동 균형 트리 (모듈 5+)

# DOM은 트리 — 각 노드가 HTML 요소
dom = {
    'tag': 'html',
    'children': [
        {'tag': 'head', 'children': [
            {'tag': 'title', 'text': 'OHS'},
        ]},
        {'tag': 'body', 'children': [
            {'tag': 'h1', 'text': '제목'},
            {'tag': 'div', 'children': [
                {'tag': 'p', 'text': '본문'},
            ]},
        ]},
    ],
}


# 모든 텍스트 추출 — DFS
def extract_text(node):
    texts = []
    if 'text' in node:
        texts.append(node['text'])
    for child in node.get('children', []):
        texts.extend(extract_text(child))
    return texts


print(extract_text(dom))  # ['OHS', '제목', '본문']

# JSON은 트리 — 객체/배열이 노드
import json

data = json.loads('{"a": 1, "b": [2, 3, {"c": 4}]}')

# 모든 정수 값 찾기 — DFS
def find_ints(node):
    ints = []
    if isinstance(node, int):
        ints.append(node)
    elif isinstance(node, dict):
        for v in node.values():
            ints.extend(find_ints(v))
    elif isinstance(node, list):
        for item in node:
            ints.extend(find_ints(item))
    return ints


print(find_ints(data))  # [1, 2, 3, 4]