트리란 무엇인가?

• 트리(Tree)는 그래프에 포함되는 개념이며, 따라서 그래프의 특별한 경우라고 할 수 있다.

1. 트리란?

• 트리(Tree)란 노드가 N개이고, 간선이 N-1개인 그래프이며, 모든 노드가 서로 연결되어 있는 구조이다.

• 대부분의 트리는 루트 노트(root node)가 존재하며, 이러한 트리를 루트 트리(rooted tree)라고 한다.
루트 노트(root node)란 트리를 대표하는 노드로, 트리의 시작 노드를 의미한다.

• 트리인 경우의 예시



• 간선의 개수가 노드의 개수 - 1개이며, 모든 노드는 서로 연결되어 있다.

• 트리가 아닌 경우의 예시



• 간선의 개수가 노드의 개수 - 1개이지만, 노드 D가 다른 노드들과 연결되어 있지 않다.

• 트리의 특징
• 간선의 개수 = 노드의 개수 - 1
• 모든 노드들이 서로 연결되어 있다.
사이클이 존재하지 않는다.
모든 노드가 연결되어 있으며, 간선의 개수가 노드의 개수 - 1이면 사이클 자체가 생길 수 없는 구조이기 때문에 트리는 항상 사이클이 존재하지 않는다.

2. 이진 트리란?

• 이진 트리(binary tree)는 루트 노드(root node)가 존재하면서, 최대 2개의 자식 노드까지만 가지는 루트 트리(rooted tree)이다.

• 이진 트리의 순회 방법 3가지
1. 전위 순회 (pre-order traversal)
부모 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드



2. 중위 순회 (in-order traversal)
왼쪽 자식 노드 → 부모 노드 → 오른쪽 자식 노드



3. 후위 순회 (post-order traversal)
왼쪽 자식 노드 → 오른쪽 자식 노드 → 부모 노드

2.1. 전위 순회 구현

• 루트 노드에서 시작하여, 부모 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드 순으로 방문하면 된다.

N = 10
root_node = 5

def pre_order(node):
    global tree

    # base case
    if node == None:
        return

    # recursive case
    print(node, end=' ')
    pre_order(tree[node][0])
    pre_order(tree[node][1])


tree = [[None, None] for _ in range(N + 1)]

tree[1] = [10, None]
tree[2] = [None, None]
tree[3] = [None, None]
tree[4] = [3, 9]
tree[5] = [1, 4]
tree[6] = [None, None]
tree[7] = [None, None]
tree[8] = [None, None]
tree[9] = [2, 6]
tree[10] = [8, 7]

pre_order(5)

2.2. 중위 순회 구현

• 루트 노드를 시작으로, 왼쪽 자식 노드 → 부모 노드 → 오른쪽 자식 노드 순으로 방문하면 된다.

N = 10
root_node = 5

def in_order(node):
    global tree

    # base case
    if node == None:
        return

    # recursive case
    in_order(tree[node][0])
    print(node, end=' ')
    in_order(tree[node][1])


tree = [[None, None] for _ in range(N + 1)]

tree[1] = [10, None]
tree[2] = [None, None]
tree[3] = [None, None]
tree[4] = [3, 9]
tree[5] = [1, 4]
tree[6] = [None, None]
tree[7] = [None, None]
tree[8] = [None, None]
tree[9] = [2, 6]
tree[10] = [8, 7]

in_order(5)

2.3. 후위 순회 구현

• 루트 노드를 시작으로, 왼쪽 자식 노드 → 오른쪽 자식 노드 → 부모 노드 순으로 방문하면 된다.

N = 10
root_node = 5

def post_order(node):
    global tree

    # base case
    if node == None:
        return

    # recursive case
    post_order(tree[node][0])
    post_order(tree[node][1])
    print(node, end=' ')


tree = [[None, None] for _ in range(N + 1)]

tree[1] = [10, None]
tree[2] = [None, None]
tree[3] = [None, None]
tree[4] = [3, 9]
tree[5] = [1, 4]
tree[6] = [None, None]
tree[7] = [None, None]
tree[8] = [None, None]
tree[9] = [2, 6]
tree[10] = [8, 7]

post_order(5)