[트리] 1991번 : 트리 순회

 

- 출제 문제 

해당 문제는 그래프의 기본에 대해 배울 수 있는 문제이다.

입력 받은 이진트리에 대해 전위 순회 중위 순회, 우선 순회에 대해 실습할 수 있다. 

 

https://www.acmicpc.net/problem/1991

1991번: 트리 순회

---

- 접근 방법

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

문제 내에서 위 글이 포인트인데 동일한 형식의 함수를 만들고 재귀의 순서를 전위/중위/후위로 나누어 구현하면 완성된다.

 

예를 들어 전위의 경우,

def preorder(root):
    if root != '.':
        print(root 자신,end='')
        preorder(root의 왼쪽 자식)
        preorder(root의 오른쪽 자식)

root는 출력으로 지정해 놓고 root의 왼쪽 자식과 오른쪽 자식을 각각 재귀로 구현하면 된다.

 

중위와 후위도 동일하게 진행한다.

---

- 완성 코드

import sys

N = int(sys.stdin.readline())
tree = {}
for i in range(N):
    root, left, right = sys.stdin.readline().split()
    tree[root]= [left,right]

# 전위(루트->왼쪽->오른쪽)
def preorder(root):
    if root != '.':
        print(root,end='')
        preorder(tree[root][0]) # root의 왼쪽 자식
        preorder(tree[root][1]) # root의 오른쪽 자식

# 중위(왼쪽->루트->오른쪽)
def inorder(root):
    if root !='.':
        inorder(tree[root][0]) # root의 왼쪽 자식
        print(root,end='')
        inorder(tree[root][1]) # root의 오른쪽 자식
        
# 후위(왼쪽->오른쪽->루트)
def postorder(root):
    if root != '.':
        postorder(tree[root][0]) # root의 왼쪽 자식
        postorder(tree[root][1]) # root의 오른쪽 자식
        print(root,end='')

preorder('A')
print()
inorder('A')
print()
postorder('A')