본문 바로가기
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