트리 순회에 대해 알아보자

대표적인 트리 순회 방법들인 전위 순회(Preorder Traversal), 중위 순회(Inorder Traversal), 후위 순회(Postorder Traversal)에 대해 정리해보자.

전위 순회 (Preorder Traversal)

• 트리를 루트 방문 -> 왼쪽 자식 -> 오른쪽 자식 순서로 순회하는 방법.

• 다음과 같은 상황에서 유용하게 사용 가능

  트리의 노드를 깊이 우선(DFS)으로 탐색해야 할 때
  트리의 노드를 복사하거나 복제할 때
  트리의 노드에 대한 전처리 작업을 수행해야 할 때

중위 순회 (Inorder Traversal)

• 트리를 왼쪽 자식 -> 루트 방문 -> 오른쪽 자식 순서로 순회하는 방법.

• 다음과 같은 상황에서 유용하게 사용 가능

  트리의 노드를 정렬된 순서로 처리해야 할 때
  트리의 노드를 검색, 탐색 또는 정렬 작업을 수행할 때
  트리의 노드를 중간에 처리해야 할 때

후위 순회 (Postorder Traversal)

• 트리를 왼쪽 자식 -> 오른쪽 자식 -> 루트 순서로 순회하는 방법.

• 다음과 같은 상황에서 유용하게 사용 가능

  트리의 노드를 하향식 우선(DFS)으로 탐색해야 할 때
  트리의 노드를 삭제할 때
  트리의 노드에 대한 후처리 작업을 수행해야 할 때

직접 구현해본 각 순회들

import sys
input = sys.stdin.readline

N = int(input())
tree= [list(input().split())for _ in range(N)]

def findNode(tree, nodeName):
    for elem in tree:
        if elem[0] == nodeName:
            return elem
    raise

def preorder(node):
    # 노드 방문시 노드명 출력
    print(node[0], end='')
    # 더이상 방문할 자식이 없다면 돌아감
    if node[1] == '.' and node[2] == '.':
        return
    # 자식들이 있는지 확인하고, 계속하여 탐색함
    if node[1] != '.':
        preorder(findNode(tree, node[1]))
    if node[2] != '.':
        preorder(findNode(tree, node[2]))

def inorder(node):
    # 왼쪽 자식 있는지 체크 후 방문
    if node[1] != '.':
        inorder(findNode(tree, node[1]))
    # 두 자식 모두 없는 곳까지 내려왔다면 출력 후 올라감
    if node[1] == '.' and node[2] == '.':
        print(node[0], end='')
        return
    # 루트로 올라왔으니 출력해주고
    print(node[0], end='')
    # 오른쪽 자식이 없다면 돌아감
    if node[2] == '.':
        return
    # 오른쪽 자식만 있음 -> 오른쪽 자식으로 넘어가 반복
    inorder(findNode(tree, node[2]))

def postorder(node):
    # 왼쪽 자식 있는지 체크 후 방문
    if node[1] != '.':
        postorder(findNode(tree, node[1]))
    # 두 자식 모두 없는 곳까지 내려왔다면 출력 후 올라감
    if node[1] == '.' and node[2] == '.':
        print(node[0], end='')
        return
    # 올라와서 오른쪽 자식 있는지 체크 후 있다면 오른쪽으로 쭉~ 내려감
    if node[2] != '.':
        postorder(findNode(tree, node[2]))
    # 두 자식 모두 없는 곳까지 내려왔다면 출력 후 올라감
    if node[1] == '.' and node[2] == '.':
        print(node[0], end='')
        return
    print(node[0], end='')
    return

preorder(tree[0])
print()
inorder(tree[0])
print()
postorder(tree[0])

• 백준 1991번: 트리 순회