파이썬의 자료구조 - 트리 문제풀이

트리 문제풀이 (백준 온라인 저지 1991번)

트리 개념 정리 (전위, 중위, 후위)

중위 순회

• 왼편 서브트리(left subtree)를 중위 순회한다.
• 루트 노드(root node)를 방문한다.
• 오른편 서브트리(right subtree)를 중위 순회한다.

후위 순회

• 왼편 서브트리(left subtree)를 후위 순회한다.
• 오른편 서브트리(right subtree)를 후위 순회한다.
• 루트 노드(root node)를 방문한다.

전위 순회

• 루트 노드(root node)를 방문한다.
• 왼편 서브트리(left subtree)를 전위 순회한다.
• 오른편 서브트리(right subtree)를 전위 순회한다.

70번 트리 선회하기 (전위, 중위, 후위)

• 문제 접근

  재귀함수 이용 - 한번 재귀할 때마다 탐색을 한번 더 하는 의미로
  함수 안의 ~~order(tree[root][0]) 재귀함수는 왼쪽으로 끝까지 탐색한다는 의미
  함수 안의 ~~order(tree[root][1]) 재귀함수는 오른쪽으로 끝까지 탐색한다는 의미
  root -> 출력하면 됨
  노드 이름은 A부터 차례로 영문자 대문자로 매기고 항상 A가 루트 노드가 됨
  자식 노드가 없으면 .으로 표현된다
  

  1. 전위 순회 : 루트 -> 왼쪽 자식 -> 오른쪽 자식이므로 재귀함수 순서도 root출력문 -> 왼쪽 재귀함수 -> 오른쪽 재귀함수
  2. 중위 순회 : 왼쪽 자식 -> 루트 -> 오른쪽 자식이므로 재귀함수 순서도 왼쪽 재귀함수 -> root 출력문 -> 오른쪽 재귀함수
  3. 후위 순회 : 왼쪽 자식 -> 오른쪽 자식 -> 루트이므로 재귀함수 순서도 왼쪽 재귀함수 -> 오른쪽 재귀함수 -> root 출력문
  

  
  

• 코드

import sys
input = sys.stdin.readline
N = int(input())
tree = {} # 트리 딕셔너리로 사용, 간단하게 관계로 표현하기 위함

for _ in range(N) :
    root, left, right = input().split() # root, right, left 데이터 받기
    tree[root] = [left, right] # 트리 딕셔너리에 데이터 저장

def preOrder(now) : # 중간-왼쪽-오른쪽 전위 순회
    if now == '.' :
        return # 자식 노드가 없으면 return
    print(now, end = '') # 현재 노드 출력
    preOrder(tree[now][0]) # 왼쪽 자식 노드 탐색
    preOrder(tree[now][1]) # 오른쪽 자식 노드 탐색

def inOrder(now): # 왼쪽-중간-오른쪽 중위 순회
    if now == '.' :
        return # 자식 노드가 없으면 return
    inOrder(tree[now][0]) # 왼쪽 자식 노드 탐색
    print(now, end='') # 현재 노드 출력
    inOrder(tree[now][1]) # 오른쪽 자식 노드 탐색

def postOrder(now) : # 왼쪽-오른쪽-중간 중위 순회
    if now == '.' :
        return # 자식 노드가 없으면 return
    postOrder(tree[now][0]) # 왼쪽 자식 노드 탐색
    postOrder(tree[now][1]) # 오른쪽 자식 노드 탐색
    print(now, end = '') # 현재 노드 출력

#preOrder - inOrder - postOrder 순으로 실행, 결과 출력
preOrder('A')
print()
inOrder('A')
print()
postOrder('A')

참고

클래스를 이용하여 좀 더 직관적인 풀이가 가능하였다.

import sys
input = sys.stdin.readline

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

def preorder(node):
  print(node.item, end="")
  if node.left != '.':
    preorder(tree[node.left])
  if node.right != '.':
    preorder(tree[node.right])

def inorder(node):
  if node.left != '.':
    inorder(tree[node.left])
  print(node.item, end="")
  if node.right != '.':
    inorder(tree[node.right])

def postorder(node):
  if node.left != '.':
    postorder(tree[node.left])
  if node.right != '.':
    postorder(tree[node.right])
  print(node.item, end="")

n = int(input())
tree = {}

for _ in range(n):
  node, left, right = map(str, input().split())
  tree[node] = Node(item=node, left=left, right=right)

preorder(tree['A'])
print()
inorder(tree['A'])
print()
postorder(tree['A'])