[AIGORITHM THEORY] 트리 순회 개념정리

개념

특징

• 전산학에서의 트리 순회는 에서 각각의 노드를 정확히 한 번만, 체계적인 방법으로 방문하는 과정을 말한다. 이는 노드를 방문하는 순서에 따라 분류된다. 여기서 설명하는 알고리즘들은 이진트리에 대해서 작성되었지만, 다른 모든 트리에서도 일반화될 수 있다.
• 분할정복 탐색 알고리즘으로, 빠른 속도로 탐색이 가능하다.
• 힙 정렬의 경우도 이진트리를 활용해 정렬을 수행한다.

알고리즘

• 전위순회 (깊이 우선 순회)
  1. 노드를 방문한다.
  2. 왼쪽 서브 트리를 전위 순회한다.
  3. 오른쪽 서브 트리를 전위 순회한다.
• 중위순회 (대칭 순회)
  1. 왼쪽 서브 트리를 중위 순회한다.
  2. 노드를 방문한다.
  3. 오른쪽 서브 트리를 중위 순회한다.
• 후위순회
  1. 왼쪽 서브 트리를 후위 순회한다.
  2. 오른쪽 서브 트리를 후위 순회한다.
  3. 노드를 방문한다.

---

필기

• 트리의 종류는 내가 아는것보다 훨씬 더 많고, 다양하다. 이 글에 꾸준히 추가해 넣을 예정. 아직까진 기본적인 내용들이 전부여서, 추가되는데로 필기에 적어넣겠다.

---

코드

• 백준 1991 코드

#https://www.acmicpc.net/problem/1991
#트리 순회
#1991

import sys
input = sys.stdin.readline

n = int(input())

tree = {}
for _ in range(n):
    a, b, c = input().split()
    tree[a] = b, c

print(tree)

def LAB(root):

    if root != '.':
        print(root, end='')
        LAB(tree[root][0])
        LAB(tree[root][1])

def ALB(root):

    if root != '.':
        ALB(tree[root][0])
        print(root, end='')
        ALB(tree[root][1])

def ABL(root):

    if root != '.':
        ABL(tree[root][0])
        ABL(tree[root][1])
        print(root, end='')

LAB('A')
print()
ALB('A')
print()
ABL('A')

• 백준 5639 코드

#https://www.acmicpc.net/problem/5639
#이진 검색 트리
#5639

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

graph = []
while True:
    try:
        a = int(input())
        graph.append(a)
    except:
        break

###########################################################

#트리를 튜플형태로 저장하는 방법
def LAB_tree_tuple(graph): 
    if not graph:
        return None

    root = graph[0]

    # 왼쪽 하위 트리와 오른쪽 하위 트리로 나눈다.
    left_subtree = [x for x in graph if x < root]
    right_subtree = [x for x in graph if x > root]

    left = LAB_tree_tuple(left_subtree)
    right = LAB_tree_tuple(right_subtree)

    return (root, left, right)

#트리를 딕셔너리 형태로 저장하는 방법
def LAB_tree_diction(graph):
    if not graph:
        return None

    root = graph[0]

    # 왼쪽 하위 트리와 오른쪽 하위 트리로 나눈다.
    left_subtree = [x for x in graph if x < root]
    right_subtree = [x for x in graph if x > root]

    left = LAB_tree_diction(left_subtree)
    right = LAB_tree_diction(right_subtree)

    return {"root": root, "left": left, "right": right}

###########################################################     

#전위순회
def LAB(tree):
    result = []
    if tree:
        result.append(tree["root"])
        result.extend(ABL(tree["left"]))
        result.extend(ABL(tree["right"]))
    return result   

#중위순회
def ALB(tree):
    result = []
    if tree:
        result.extend(ABL(tree["left"]))
        result.append(tree["root"])
        result.extend(ABL(tree["right"]))
    return result

#후위순회
def ABL(tree):
    result = []
    if tree:
        result.extend(ABL(tree["left"]))
        result.extend(ABL(tree["right"]))
        result.append(tree["root"])
    return result           

###########################################################

tree = LAB_tree_diction(graph)
result_list = ABL(tree)

for i in range(len(result_list)):
    print(result_list[i])

---

참고자료

• https://ko.wikipedia.org/wiki/트리_순회