Skip to main content
동호의 블로그

트리란 무엇인가?

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

1. 트리란?

  • 트리(Tree)란 노드가 N개이고, 간선이 N-1개인 그래프이며, 모든 노드가 서로 연결되어 있는 구조이다.
  • 대부분의 트리는 **루트 노트(root node)**가 존재하며, 이러한 트리를 **루트 트리(rooted tree)**라고 한다.
**루트 노트(root node)**란 트리를 대표하는 노드로, 트리의 시작 노드를 의미한다.

image.png

  • 트리인 경우의 예시

    image.png

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

  • 트리가 아닌 경우의 예시

    image.png

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

  • 트리의 특징

    • 간선의 개수 = 노드의 개수 - 1
    • 모든 노드들이 서로 연결되어 있다.
사이클이 존재하지 않는다.
Note

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

2. 이진 트리란?

  • **이진 트리(binary tree)**는 루트 노드(root node)가 존재하면서, 최대 2개의 자식 노드까지만 가지는 **루트 트리(rooted tree)**이다.
  • 이진 트리의 순회 방법 3가지
    1. 전위 순회 (pre-order traversal)
**부모 노드** → 왼쪽 자식 노드 → 오른쪽 자식 노드

image.png

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

image.png

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

image.png

2.1. 전위 순회 구현

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

    image.png

**예제 코드** 
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. 중위 순회 구현

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

    image.png

**예제 코드** 
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. 후위 순회 구현

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

    image.png

**예제 코드** 
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)