트리(Tree)

가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 알고리즘

• 루트 노드
  부모가 없는 최상위 노드
• 단말 노드
  자식이 없는 노드
• 크기
  트리에 포함된 모든 노드의 개수
• 깊이
  루트 노드로부터의 거리
• 높이
  깊이 중 최대값
• 차수
  각 노드에 직접적으로(간선 하나로) 연결되어 있는 자식 개수
  기본적으로 트리의 크기가 N이면 전체 간선의 개수는 N-1

이진 탐색 트리(Binary Search Tree)

이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조의 일종
왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
트리 데이터를 이진 탐색 트리 형태로 가공하면 보다 효율적으로 탐색을 수행할 수 있음(노드들이 크기순으로 정렬되어 있기 때문) -> 시간복잡도 O(logN)

트리의 순회(Tree Traversal)

트리 자료구조에 포함된 노드를 특정 방법으로 한 번씩 방문하여 트리의 정보를 시각적으로 확인하는 방법

트리 순회 방법

• 전위 순회(pre-order traverse)
  루트 노드를 먼저 방문
• 중위 순회(in-order traverse)
  왼쪽 자식 노드를 방문한 뒤에 루트 노드를 방문
• 후위 순회(post-order traverse)
  오른쪽 자식 노드를 방문한 뒤에 루트 노드를 방문

# 트리 선언
class Node:
    def __init__(self, data, left_node, right_node):
        self.data = data
        self.left_node = left_node
        self.right_node = right_node

# 전위 순회(pre-order traverse)
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])

# 중위 순회(in-order traverse)
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])

# 후위 순회(post-order traverse)
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=' ')