[백준] 트리 순회

#백준 1991

이진탐색

그래프

백준

easy

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현된다.

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

ABDCEFG
DBAECFG
DBEGFCA

트리 탐색

전위순회: 루트 → 왼쪽자식 → 오른쪽자식
중위순회: 왼쪽자식 → 루트 → 오른쪽자식
후위순회: 왼쪽자식 → 오른쪽자식 → 루트

전위순회

루트출력 → 왼쪽자식 → 오른쪽자식

 def pre_order(node):
     print(node, end='')
     vertex = mygraph[node]
     if vertex['left'] != '.':
         pre_order(vertex['left'])
     if vertex['right'] != '.':
         pre_order(vertex['right'])

중위순회

왼쪽자식 → 루트출력 → 오른쪽자식 x 축으로 고려해봤을 때, 왼쪽 노드 부터 차례대로 출력되는 것을 확인할 수 있음

중위순회 특징

x 축으로 고려해봤을 때, 왼쪽 노드 부터 차례대로 출력되는 것을 확인할 수 있음
```
 def in_order(node):
     vertex = mygraph[node]
     if vertex['left'] != '.':
         in_order(vertex['left'])
     print(node, end='')
     if vertex['right'] != '.':
         in_order(vertex['right'])
```
후위순회

왼쪽자식 → 오른쪽자식 → 루트출력

트리구현

트리를 구현하는 자료구조로는 다음 두가지 방법이 있다.

구조체역할을 하는 class로 Node를 선언

 mygraph = dict()

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

 for _ in range(n):
     data, left, right = input().split(' ')
     mygraph[data] = Node(data, left, right)

dict를 활용

 mygraph = dict()

 for _ in range(n):
     node, left, right = input().split(' ')

     mygraph[node] = {'left': left, 'right': right}

GIT Source

Jeong Sun Min

[백준] 트리 순회

문제

트리 탐색

중위순회 특징

트리구현