본문 바로가기
Algorithm/Concepts

전위 / 중위 / 후위순회 (Preorder/ Inorder / Postorder Traversal)(이진트리 탐색)

by 컴돈AI 2024. 3. 15.

목차

    이진 트리(Binary Tree)를 탐색하는 방법

    • 이진 트리를 탐색하는 방법(4가지)
      • 전위 순회(Preorder Traversal)
      • 중위 순회(Inorder Traversal)
      • 후위 순회(Postorder Traversal).
      • 레벨순회(Levelorder Traversal) 또는 BFS(Breadth-First Search; 너비 우선 탐색)
      • 참고 : 전위 순회, 중위 순회, 후위 순회는 모두 DFS의 변형으로 간주
    • 전위 순회, 중위 순회, 후위 순회의 명칭은 루트가 어디 있는지 기준입니다. 
      • 즉 ,전 -> 루트가 앞 / 중 -> 루트가 중간 / 후 -> 루트가 뒤
    • 전위, 중위, 후위 순회의 각 탐색 방법은 재귀적으로 구현할 수 있으며, 각 노드를 한 번씩 방문하므로 시간복잡도는 모두 O(n)입니다.
    • 코드도 거의 비슷합니다. 다만 이제 root 시점에서 result에 해당 노드의 value만 append 시켜주면 됩니다.
      • 코드를 살펴보면 손쉽게 이해 가능합니다.

    전위 순회(Preorder Traversal)

    • 전위 순회(Preorder Traversal)
      • 루트-왼쪽-오른쪽 순서
        • 먼저 현재 노드를 방문하고, 그다음에 왼쪽 서브 트리를, 마지막으로 오른쪽 서브 트리를 방문합니다.
        • 즉 dfs로 탐색하는데 방문하는 즉시 출력되는 것입니다.
      • 16 - 8 - 4 - 2 - 6 - 12 - 10 - 14 - 24 - 20 - 18 - 22 - 28 - 26 - 30 순서로 방문합니다.
    • 코드 
      • class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


# 전위 순회 (Preorder Traversal)
def preorder(node, result):
    if node:
        result.append(node.value)  # 현재 노드 처리
        preorder(node.left, result)  # 왼쪽 서브트리 순회
        preorder(node.right, result)  # 오른쪽 서브트리 순회
    return result


# 이진 트리 예시 생성
#     1
#    / \
#   2   3
#  / \
# 4   5

# 이진트리 데이터 생성
root = TreeNode(1)
root.left = TreeNode(2, TreeNode(4), TreeNode(5))
root.right = TreeNode(3)

# 순회 실행
print("Preorder: ", preorder(root, []))

    중위 순회(Inorder Traversal)

    • 중위 순회(Inorder Traversal)
      • 왼쪽-루트-오른쪽 순서
        • 왼쪽 서브 트리를 먼저 방문한 후, 현재 노드를 방문하고, 그다음에 오른쪽 서브 트리를 방문합니다.
        • dfs로 방문하는데, 왼쪽 자식 노드가 없으면 해당노드를 출력합니다. (또는 왼쪽노드가 이미 출력이 완료됐으면)
        • 중위 순회는 모든 노드를 x값 순서대로 왼쪽부터 쭈욱 읽은것과 동일합니다.
      • 2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 - 20 - 22 - 24 - 26 - 28 - 30
       
    • 코드 
      • class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


# 중위 순회 (Inorder Traversal)
def inorder(node, result):
    if node:
        inorder(node.left, result)  # 왼쪽 서브트리 순회
        result.append(node.value)  # 현재 노드 처리
        inorder(node.right, result)  # 오른쪽 서브트리 순회
    return result


# 이진 트리 예시 생성
#     1
#    / \
#   2   3
#  / \
# 4   5

# 이진트리 데이터 생성
root = TreeNode(1)
root.left = TreeNode(2, TreeNode(4), TreeNode(5))
root.right = TreeNode(3)

# 순회 실행
print("Inorder: ", inorder(root, []))

    후위 순회(Postorder Traversal)

    • 후위 순회(Postorder Traversal)
      • 왼쪽-오른쪽-루트 순서
        • 왼쪽 서브 트리를 방문하고, 그 다음 오른쪽 서브 트리를 방문한 후, 마지막으로 현재 노드를 방문합니다.
        • dfs로 방문하는데, 왼쪽 자식 노드와 오른쪽 자식노드가 모두 없으면 해당 노드를 출력합니다. (또는 왼쪽 자식노드 오른쪽 자식 노드가 모두 출력이 완료됐으면)
      • 2 - 6 - 4 - 10 - 14 - 12 - 8 - 18 - 22 - 20 - 26 - 30 - 28 - 24 - 16
    • 코드 
      • class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


# 후위 순회 (Postorder Traversal)
def postorder(node, result):
    if node:
        postorder(node.left, result)  # 왼쪽 서브트리 순회
        postorder(node.right, result)  # 오른쪽 서브트리 순회
        result.append(node.value)  # 현재 노드 처리
    return result


# 이진 트리 예시 생성
#     1
#    / \
#   2   3
#  / \
# 4   5

# 이진트리 데이터 생성
root = TreeNode(1)
root.left = TreeNode(2, TreeNode(4), TreeNode(5))
root.right = TreeNode(3)

# 순회 실행
print("Postorder: ", postorder(root, []))

    전체 코드

    • 전위 순회, 중위 순회, 후위 순회도 재귀가 많으므로 sys.setrecursionlimits(int(1e5)) 처럼 최대 재귀수를 늘려줘야 할 수도 있습니다.
    • class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


# 전위 순회 (Preorder Traversal)
def preorder(node, result):
    if node:
        result.append(node.value)  # 현재 노드 처리
        preorder(node.left, result)  # 왼쪽 서브트리 순회
        preorder(node.right, result)  # 오른쪽 서브트리 순회
    return result


# 중위 순회 (Inorder Traversal)
def inorder(node, result):
    if node:
        inorder(node.left, result)  # 왼쪽 서브트리 순회
        result.append(node.value)  # 현재 노드 처리
        inorder(node.right, result)  # 오른쪽 서브트리 순회
    return result


# 후위 순회 (Postorder Traversal)
def postorder(node, result):
    if node:
        postorder(node.left, result)  # 왼쪽 서브트리 순회
        postorder(node.right, result)  # 오른쪽 서브트리 순회
        result.append(node.value)  # 현재 노드 처리
    return result


# 이진 트리 예시 생성
#     1
#    / \
#   2   3
#  / \
# 4   5

# 이진트리 데이터 생성
root = TreeNode(1)
root.left = TreeNode(2, TreeNode(4), TreeNode(5))
root.right = TreeNode(3)

# 순회 실행
print("Preorder: ", preorder(root, []))
print("Inorder: ", inorder(root, []))
print("Postorder: ", postorder(root, []))

    예시

    • 프로그래머스 길 찾기 게임
      • 전위 순회, 후위 순회한 결과를 반환하는 대표적인 문제입니다.
      • 다만, 이진트리를 구성하는 부분이 다소 까다로울 수 있습니다. 하지만 트리만 구성한다면 손쉽게 풀 수 있는 문제입니다.
      • 이진 트리 구성하기 
        • 부모노드는 무조건 y값이 자식노드보다 1이 큽니다. 또한 왼쪽 자식노드는 부모노드의 x값보다 작은 x값을 가질 것이고, 오른쪽 자식노드는 부모노드의 x값보다 큰 x값을 가질 것입니다
        • 따라서 y가 큰 순으로 정렬하고 하나씩 x범위를 재귀로 비교하면서 위에 level부터 하나씩 노드를 채워나가면 됩니다.
      • 코드 
        • import sys

sys.setrecursionlimit(int(1e5))

class Node():
    def __init__(self,value,x,left=None,right=None):
        self.value = value
        self.x = x
        self.left = left
        self.right = right

def preorder(root,visit):
    if root:
        visit.append(root.value)
        preorder(root.left,visit)
        preorder(root.right,visit)
    return visit
    
def postorder(root,visit):
    if root:
        postorder(root.left,visit)
        postorder(root.right,visit)
        visit.append(root.value)
    return visit

def addnode(parent,child):
    if child[1]<parent.x:
        if parent.left:
            addnode(parent.left,child)
        else:
            parent.left = Node(child[0],child[1])
    else:
        if parent.right:
            addnode(parent.right,child)
        else:
            parent.right = Node(child[0],child[1])

def solution(nodeinfo):
    index_nodeinfo = [[i+1,x,y] for i,(x,y) in enumerate(nodeinfo)]
    index_nodeinfo.sort(key=lambda x:-x[2])
        
    root_idx,root_x,root_y = index_nodeinfo[0]
    root = Node(root_idx,root_x)

    for i in range(1,len(nodeinfo)):
        addnode(root,index_nodeinfo[i])

    return [preorder(root,[]),postorder(root,[])]
    • [백준 5639] 이진 검색 트리
      • 전위 순회한 결과를 가지고 이진 트리를 생성한 뒤 다시 후위 순회를 한 결과를 출력하면 됩니다.
      • 코드
        • import sys

sys.setrecursionlimit(int(1e5))
input = sys.stdin.readline

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


class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def add_node(root, x):
    if root.value < x:
        if root.right:
            add_node(root.right, x)
        else:
            root.right = Node(value=x)
    else:
        if root.left:
            add_node(root.left, x)
        else:
            root.left = Node(value=x)


root = Node(value=arr[0])
for item in arr[1:]:
    add_node(root, item)


def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.value)
    return


postorder(root)
      • 위 코드는 pypy3에서만 통과가 됩니다. 이는 이제 이진 검색 트리의 경우 연속적인 입력이 트리의 한 쪽 방향으로만 치우치게 된다면, 트리가 사실상 선형 리스트와 같은 형태로 구성됩니다. 따라서 트리를 만드는 add_node부분에서 시간복잡도가 O(n^2)이 됩니다. 
      • 삽입하는 코드 없이 전위 순회 결과를 보고 후위 순회 결과를 바로 출력해야합니다.
      • 전위 순회의 경우 dfs로 방문하는 즉시 해당 노드를 출력한 결과입니다. 따라서 해당 부모노드의 오른쪽 서브트리의 경우는 전위 순회의 결과중에서 부모노드보다 큰 노드가 나오는 그 인덱스 이후가 모두 오른쪽 서브 트리가 됩니다. 이를 이용한다면 삽입하는 코드 없이 전위 순회 결과를 보고 후위 순회 결과를 바로 출력가능합니다.
      • 코드 
        • import sys

sys.setrecursionlimit(int(1e5))
input = sys.stdin.readline

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


def postorder(start, end):  # start~ end까지 탐색
    if start > end:
        return

    # start가 가장 클 경우,
    # 오른쪽 서브 트리는 없기 때문에 없는 값인 end+1로 지정해주기
    div = end + 1
    root = arr[start]  # start 는 root 노드
    for i in range(start + 1, end + 1):
        if root < arr[i]:
            div = i  # i 부터 오른쪽 서브트리입니다.
            break

    postorder(start + 1, div - 1)  # 왼쪽 서브트리
    postorder(div, end)  # 오른쪽 서브트리
    print(arr[start])


postorder(0, len(arr) - 1)

    'Algorithm > Concepts' 카테고리의 다른 글

    Union-Find  (0) 2024.03.20
    백트래킹 (Backtracking)  (0) 2024.03.19
    최단 경로 (플로이드-와샬(Floyd-Warshall))  (1) 2024.02.15
    최단 경로 (벨만-포드(Bellman-Ford))  (0) 2024.02.14
    최단 경로 (다익스트라(Dijkstra))  (0) 2023.10.16

    관련글

    티스토리툴바