[자료구조] 트리(Tree), 트리 순회(Tree Traversal)와 이진 탐색 트리(Binary Search Tree)

# 트리 (Tree)

 가계도와 같은 계층적인 구조를 표현할 때 사용하는 자료구조이다.

 

 - 루트 노드 (root node): 부모가 없는 최상위 노드 ex) A

 - 단말 노드 (leaf node): 자식이 없는 노드 ex) G, E, F

 - 크기 (size): 트리에 포함된 모든 노드의 개수  ex) 7개

 - 깊이 (depth): 루트 노드부터 해당 노드까지의 거리  ex) A: 0 / B, C: 1 / D, E, F: 2 / G: 3

 - 높이 (height): 깊이 중 최댓값  ex) 3

 - 차수 (degree): 각 노드의 (자식 방향) 간선 개수 ex) A, B: 2 / C, D: 1

 - 트리의 크기가 N일 때, 전체 간선의 개수는 N - 1개

 

# 트리의 순회 (Tree Traversal)

 트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법을 말한다. 대표적인 트리 순회는 3가지 방법이 있다.

 - 전위 순회 (pre-order traverse): 루트를 먼저 방문한 후, 왼쪽 오른쪽을 차례로 방문

 - 중위 순회 (in-order traverse): 왼쪽 자식을 방문한 뒤에 루트를 방문하고 그 다음 오른쪽 자식을 방문

 - 후위 순회 (post-order traverse): 왼쪽 자식을 방문하고 오른쪽 자식을 방문한 이후에 루트를 방문

 

 다음은 트리 순회를 구현한 파이썬 소스코드이다.

# 입력 예시
# 7
# A B C
# B D E
# C F G
# D None None
# E None None
# F None None
# G None None


class Node:
    def __init__(self, data, left_node, right_node):
        self.data = data
        self.left_node = left_node
        self.right_node = right_node


# 전위 순회 (Preorder Traversal)
def pre_order(node):
    print(node.data, end=' ')
    if node.left_node != None:
        pre_order(tree[node.left_node])
    if node.right_node != None:
        pre_order(tree[node.right_node])


# 중위 순회 (Inorder Traversal)
def in_order(node):
    if node.left_node != None:
        in_order(tree[node.left_node])
    print(node.data, end=' ')
    if node.right_node != None:
        in_order(tree[node.right_node])


# 후위 순회 (Postorder Traversal)
def post_order(node):
    if node.left_node != None:
        post_order(tree[node.left_node])
    if node.right_node != None:
        post_order(tree[node.right_node])
    print(node.data, end=' ')


n = int(input())
tree = {}

for i in range(n):
    data, left_node, right_node = input().split()
    if left_node == "None":
        left_node = None
    if right_node == "None":
        right_node = None
    tree[data] = Node(data, left_node, right_node)

pre_order(tree['A'])
print()
in_order(tree['A'])
print()
post_order(tree['A'])

 

# 이진 탐색 트리 (Binary Search Tree)

 

 이진 탐색이 동작하여 효율적인 탐색이 가능하도록 고안된 자료구조이다. 이진 탐색 트리의 특징은 왼쪽 자식 노드가 부모 노드보다 작고 오른쪽 자식 노드가 부모 노드보다 크다는 점이다. (왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드) 다음은 이진 탐색 트리에서 데이터 값 37을 조회하는 과정이다.

 

 

 

본 포스팅은 '안경잡이 개발자' 나동빈 님의 저서

'이것이 코딩테스트다'와 그 유튜브 강의를 공부하고 정리한 내용을 담고 있습니다.