[알고리즘] 이진트리의 전위순회, 중위순회, 후위순회 알아보기

오늘은 이진트리 순회 하는 방법에 대해서 공부해 보려고 합니다.

이진트리란?

이진 트리는 루트(Root) 노드에서 시작하여 각 노드는 왼쪽 서브트리(Left Subtree)와 오른쪽 서브트리(Right Subtree)로 이루어져 있습니다. 각 노드의 자식 노드는 최대 두 개이기 때문에, 이진 트리는 가장 단순한 형태의 트리 중 하나입니다.

이진트리의 활용분야

• 데이터베이스: 이진 트리는 데이터베이스에서 색인(Index)을 만드는데 사용됩니다. 이진 트리를 사용하면 검색 속도가 빨라지기 때문에, 대규모 데이터베이스에서 빠른 검색을 구현할 수 있습니다.
• 정렬 알고리즘: 이진 트리는 정렬 알고리즘에서 사용됩니다. 예를 들어, 이진 탐색 트리(Binary Search Tree)는 데이터를 효과적으로 정렬하고 검색할 수 있는 알고리즘입니다.
• 압축 알고리즘: 이진 트리는 압축 알고리즘에서도 사용됩니다. 예를 들어, 허프만 코딩(Huffman Coding) 알고리즘은 이진 트리를 사용하여 데이터를 압축합니다.
• 인공지능: 이진 트리는 인공지능에서도 사용됩니다. 예를 들어, 의사결정나무(Decision Tree)는 이진 트리를 사용하여 데이터를 분류하는 알고리즘입니다.

이진트리의 장단점

장점:

• 검색 속도가 빠릅니다: 이진 탐색 트리(Binary Search Tree)는 검색 속도가 매우 빠르기 때문에, 대용량 데이터의 검색이나 정렬에 매우 유용합니다.
• 데이터를 효율적으로 저장합니다: 이진 트리는 데이터를 효율적으로 저장할 수 있습니다. 데이터의 추가, 삭제, 검색 등이 매우 빠르게 이루어지기 때문에, 데이터를 효율적으로 관리할 수 있습니다.
• 구현이 간단합니다: 이진 트리는 구현이 간단하고, 이해하기 쉬운 자료구조입니다. 이진 트리를 사용하면, 다양한 문제를 해결하는데 도움이 됩니다.

단점:

• 균형이 맞지 않을 경우 성능이 저하됩니다: 이진 트리는 데이터의 추가, 삭제에 따라 균형이 깨질 수 있습니다. 이 경우, 검색 속도가 느려지거나, 최악의 경우 성능이 매우 저하될 수 있습니다. 이를 해결하기 위해 균형 이진 트리(AVL Tree, Red-Black Tree 등)를 사용할 수 있습니다.
• 트리의 높이가 너무 높아질 수 있습니다: 이진 트리의 높이가 너무 높아지면, 검색 속도가 느려질 수 있습니다. 이를 해결하기 위해 트리의 깊이를 최소화하는 방법(균형 이진 트리, 힙 등)을 사용할 수 있습니다.
• 메모리 사용량이 많을 수 있습니다: 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지기 때문에, 메모리 사용량이 많아질 수 있습니다. 이를 해결하기 위해 노드를 사용하지 않는 빈 공간(Null 포인터)으로 대체하는 방법을 사용할 수 있습니다.

이진트리의 순회 방법

• 전위 순회
• 중위 순회
• 후위 순회

아래 트리 모두 1번 Node부터 왼쪽 트리로 조회합니다.

전위 순회 방법

검은색선은 해당 번호를 출력하고 움직인것을 의미합니다.
빨간색선은 번호를 출력하지 않고 움직인것을 의미합니다.

전위 순회 방식은 중앙 -> 왼쪽 -> 오른쪽 순서로 순회를 하는 방식입니다.

예를 들면)
1번을 순회했으니 더이상의 중앙은 없기 때문에 왼쪽 노드인 2번 노드로 이동
2번 노드에서도 마찬가지로 중앙을 출력하고 왼쪽 노드인 4번으로 이동합니다.
4번 노드를 출력 후 더이상 자식 노드가 없기 때문에 부모 노드로 이동합니다.
이제 2번 노드에서 방문안한 오른쪽 노드인 5번 노드로 이동 하는 것입니다.
이제 왼쪽 서브 트리는 모두 조회했기 때문에 오른쪽 서브 트리의 시작지점인 3번으로 이동합니다.
이후에 내용은 동일합니다.

중위 순회 방법

저는 중위 순회 방식을 단순히 순서로 이해하려고 했을 때 많이 헷갈렸습니다.
전위, 중위, 후위 순회하는 코드를 보니 이해하기 쉬웠습니다. 밑에 코드를 한번 보시고 오셔도 좋을 것 같습니다. :)

중위 순회 방식은 왼쪽 -> 중앙 -> 오른쪽 순서로 순회를 하는 방식입니다.

예를 들면)
1번에서 왼쪽 노드를 모두 조회하지 않았기때문에 출력하지 않고 2번으로 이동합니다.
2번에서 마찬가지로 왼쪽 자식 노드가 존재하기 때문에 4번 노드로 이동합니다.
4번 노드에서 더이상 자식 노드가 없기때문에 출력하고 부모 노드로 이동합니다.
왼쪽을 다 조회 했으니 중앙 노드 역할을 하는 2번 노드로 출력합니다.
이제 오른쪽인 5번 노드로 이동하고 출력합니다. 이제 왼쪽 서브 트리는 모두 조회했습니다.
중앙노드인 1번 노드로 이동하여 출력하고 오른쪽 노드로 이동하고 이후에 내용은 동일합니다.

후위 순회 방법

후위 순회 방식은 왼쪽 -> 오른쪽 -> 중앙 순서로 순회를 하는 방식입니다.

예를 들면)
1번에서 시작하면 왼쪽 노드인 2번을 순회합니다.
2번 노드에서 왼쪽 자식 노드가 있기 때문에 4번 노드로 더 이동하겠습니다.
4번 노드에서는 왼쪽 자식 노드가 존재하지 않습니다. 그래서 4번 노드를 출력하고 부모 노드인 2번으로 이동합니다.
후위 순회이기 때문에 중앙을 출력하지 않고 오른쪽 노드인 5번을 순회합니다.
5번 노드도 왼쪽, 오른쪽 자식 노드가 존재하지 않기 때문에 출력하고 부모노드인 2번으로 이동합니다.
현재 왼쪽 자식 노드, 오른쪽 자식 노드를 모두 조회했기 때문에 중앙을 출력하고 부모 노드인 1번 노드로 이동합니다.
1번 노드에서도 오른쪽 노드를 아직 조회하지 않았기 떄문에 오른쪽 노드인 3번 노드로 이동하고 이후에 내용은 동일합니다.

의사 코드 작성

1. Node class를 만든다.
2. Node의 필드는 left, right, data가 존재하며 left, right는 자식 노드를 의미합니다.
3. 전위 순회 함수를 만듭니다.
   3.1. 현재 노드의 값을 출력합니다.
   3.1. 왼쪽 노드를 순회합니다.
   3.2. 오른쪽 노드를 순회합니다.
4. 중위 순회 함수를 만듭니다.
   4.1. 왼쪽 노드를 순회합니다.
   4.2. 현재 노드 값을 출력합니다.
   4.3. 오른쪽 노드를 순회합니다.
5. 후위 순회 함수를 만듭니다.
   5.1. 왼쪽 노드를 순회합니다.
   5.2. 오른쪽 노드를 순회합니다.
   5.3. 현재 노드 값을 출력합니다.

이진트리 자료형 만들기

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

전위순회 함수 만들기

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])

저는 전위, 중위, 후위를 외울 때 어디서 내가 원하는 작업을 실행하냐로 생각해서 외웠습니다.
전위는 print가 가장 먼저 나오기 때문에 전위

중위순회 함수 만들기

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])

중위는 print가 중간에 나오기 때문에 중위

후위순회 함수 만들기

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='')

후위는 print가 마지막에 나오기 때문에 후위

실제 사용 및 전체 코드

tree = {}
class Node:
    def __init__(self, data, left_node, right_node):
        self.data = data
        self.left_node = left_node
        self.right_node = right_node
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])
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])
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=' ')
def solution(input):
    for i in input:
        cur, left, right = i
        tree[cur] = Node(cur, left, right)
    # 전위
    print('[ ',end='')
    pre_order(tree[1])
    print(']')

    # 중위
    print('[ ', end='')
    in_order(tree[1])
    print(']')

    # 후위
    print('[ ', end='')
    post_order(tree[1])
    print(']')

solution([[1,2,3], [2,4,5], [3,6,7], [4,None, None], [5, None, None], [6, None, None], [7, None, None]])

입력값

[[1,2,3], [2,4,5], [3,6,7], [4,None, None], [5, None, None], [6, None, None], [7, None, None]]

출력값