[백준 1991] 트리 순회 - 파이썬

백준 1991 - 트리 순회

---

* 풀이 과정

 

우선 전위 순회, 중위 순회, 후위 순회의 정확한 의미를 알아야 한다.

트리 개념과 함께 정리해놓은 글을 참고하였다.

• 전위 순회: root를 먼저 방문 (root > 왼쪽 자식 > 오른쪽 자식 순으로)
• 중위 순회: 왼쪽 하위 트리를 방문 후 root를 방문 (왼쪽 자식 > root > 오른쪽 자식 순으로)
• 후위 순회: 하위 트리 모두 방문 후 root 방문 (왼쪽 자식 > 오른쪽 자식 > root 순으로)

나는 tree 개념을 잘 몰라서, 우선 리스트를 이용해서 풀었다.

 

1) 각 순회에 적합한 리스트를 생성하기 위한 preoder, inorder, postorder 함수를 정의한다.

2) 한 줄로 입력받은 숫자를 node, left, right 으로 하여, 함수의 인자로 넣어준다.

3) 전위 순회(preorder)의 경우, 리스트가 비어있다면 node, left, right 순서대로 삽입한다.
리스트가 비어있지 않다면, 리스트에서 입력받은 node를 찾아 node - left - right 순서가 되도록 삽입한다.

4) 중위 순회(inorder)의 경우, 리스트가 비어있다면 left, node, right 순서대로 삽입한다.
리스트가 비어있지 않다면,  리스트에서 입력받은 node를 찾아 left - node - right 순서가 되도록 삽입한다.

5) 후위 순회(postorder)의 경우, 리스트가 비어있다면 left, right, node 순서대로 삽입한다.
리스트가 비어있지 않다면,  리스트에서 입력받은 node를 찾아 left - node - right 순서가 되도록 삽입한다.

6) "."을 제외하여 출력한다.

import sys

arr = []
in_arr = []
post_arr = []

def preorder(root, left, right):
    global arr
    # root, left, right 순서대로 저장
    if not arr: 
       arr.append(root)
       arr.append(left)
       arr.append(right)
    # root를 기준으로 arr를 slice -> root, left, right 순서 되도록 삽입
    else:
        idx = arr.index(root)
        arr = arr[0:idx+1]+[left, right]+arr[idx+1: len(arr)]
        
def inorder(root, left, right):
    global in_arr
    # root, left, right 순서대로 저장
    if not in_arr:
          in_arr.append(left)
          in_arr.append(root)
          in_arr.append(right)
    # root를 기준으로 arr를 slice -> left, root, right 순서 되도록 삽입
    else:
        idx = in_arr.index(root)
        in_arr = in_arr[0:idx]+[left, root, right]+in_arr[idx+1:len(in_arr)]
        
    
def postorder(root, left, right):
    global post_arr
    # left, right, root 순서대로 저장
    if not post_arr:
        post_arr.append(left)
        post_arr.append(right)
        post_arr.append(root)
    # root를 기준으로 arr를 slice -> left, right, root 순서 되도록 삽입
    else:
        idx = post_arr.index(root)
        post_arr = post_arr[0:idx]+[left, right]+post_arr[idx: len(post_arr)]

N = int(input())

for _ in range(N):
    i, j, k = sys.stdin.readline().split()
    preorder(i, j, k)
    inorder(i, j, k)
    postorder(i, j, k)


for i in arr:
    if i != ".": print(i, end="")
print()
for i in in_arr:
    if i != ".": print(i, end="")
print()
for i in post_arr:
    if i != ".": print(i, end="")

 

tree 개념을 활용하면, 훨씬 간단하게 풀 수 있다.

root를 key, left/right 자식들을 value로 할당하면 된다.

tree[key][0]: key의 left 자식을 의미, tree[key][1]: key의 right 자식을 의미

 

전위, 중위, 후위 순회에 따라 root 출력, root = tree[root][0], root = tree[root][1] 의 순서를 변경하여 출력하면 된다.

import sys
 
N = int(input())
tree = {}
 
for n in range(N):
    root, left, right = sys.stdin.readline().split()
    # root를 key, left와 right을 value로 갖도록 저장
    tree[root] = [left, right]
 
 
def preorder(root):
    if root != '.':
        print(root, end='')  # root를 출력한다.
        preorder(tree[root][0])  # left 자식이 새로운 root가 된다. (왼쪽으로 끝까지 탐색하면서 root 출력)
        preorder(tree[root][1])  # right 자식이 새로운 root가 된다. (더 이상 left 자식이 없는 root 부터 시작)
 
 
def inorder(root):
    if root != '.':
        inorder(tree[root][0])  # left 자식이 새로운 root가 된다. (왼쪽으로 끝까지 탐색한다.)
        print(root, end='')  # 더 이상 left 자식이 없으므로 root를 출력한다.
        inorder(tree[root][1])  # right 자식이 새로운 root가 된다.
 
 
def postorder(root):
    if root != '.':
        postorder(tree[root][0])  # left 자식이 새로운 root가 된다.
        postorder(tree[root][1])  # right 자식이 새로운 root가 된다.
        print(root, end='')  # root를 출력한다.
 
 
preorder('A')
print()
inorder('A')
print()
postorder('A')

 

트리 풀이 출처) 

백준 1991번 - 트리 순회 / python 트리 구현