✅문제 요약

1. 트리의 모형이 입력으로 주어질 때 전위, 중위, 후위 순회했을 때 순서를 출력하라

✅문제 풀이

먼저 개념을 잡고 가야겠다.

전위 순위: 현재 노드를 먼저 출력하고 다음에 왼쪽 자식 노드를 탐색하고, 오른쪽 자식 노드를 탐색한다. 만약 현재 노드에 자식노드가 없거나 모두 탐색 하였다면 상위 노드로 돌아가는 방식

중위 순위: 현재 노드에서 왼쪽 자식 노드 먼저 탐색을 한다. 만약 현재 노드가 왼쪽 자식 노드가 없다면 출력하고, 상위 노드로 올라가 출력하고 오른쪽 자식 노드를 탐색한다.

후위 순위: 현재 노드에서 왼쪽 자식 노드를 먼저 탐색한다. 만약 현재 노드의 왼쪽 자식 노드가 없다면 오른쪽 자식 노드를 탐색한다. 좌우 자식 노드가 모두 없거나 탐색한 노드라면 현재 노드를 출력하고, 상위 노드로 올라가는 방식.

위 사진과 같은 트리가 주어질 때 결과
전위 순회: ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
중위 순회: DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
후위 순회: DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

📌나의 풀이

일반적으로 바이너리 트리를 풀 때, 클래스를 활용하면 생각보다 개념이 쉽게 잡힌다.
Node라는 클래스를 만들고 attribute로 data, left, right를 선언해서, 해당 노드의 값, 왼쪽자식 노드와 오른쪽 자식 노드를 속성으로 주어서 머릿속으로 그리기 쉽게 풀이하였다.

import sys
input = sys.stdin.readline

# 바이너리 트리를 구성 할 노드 클래스
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# 전위 순회
def preorder(node):
    print(node.data, end='')
    if node.left: preorder(node.left)
    if node.right: preorder(node.right)

# 중위 순회
def inorder(node):
    if node.left: inorder(node.left)
    print(node.data, end='')
    if node.right: inorder(node.right)

# 후위 순회
def postorder(node):
    if node.left: postorder(node.left)
    if node.right: postorder(node.right)
    print(node.data, end='')


n = int(input())
graph = []

for i in range(n):
    num, l, r = input().rstrip().split()
    node = Node(num)
	
    # .이 들어왔을 때, 자식 노드가 없다는 것을 보기 쉽게 하기위해 False로 치환
    if l == '.': l = False
    if r == '.': r = False
	
    # 노드의 속성으로 자식노드 입력
    node.left = l
    node.right = r
    graph.append(node)

# 트리를 돌면서 누락된 부모, 자식 관계 노드들을 할당  
for i in range(n):
    for j in range(n):
        if graph[i].data == graph[j].left:
            graph[j].left = graph[i]
        elif graph[i].data == graph[j].right:
            graph[j].right = graph[i]

preorder(graph[0])
print()
inorder(graph[0])
print()
postorder(graph[0])