[백준 1991] 트리 순회

문제

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

예를 들어 위와 같은 이진 트리가 입력되면,

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

가 된다.

 

입력

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

 

출력

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

---

접근

트리의 구조를 잡고 각 노드를 어떻게 탐색할지 공부를 하였다.

트리를 탐색하는 방법에는 전위 순회, 중위 순회, 후위 순회가 존재한다. 각 이름은 부모 노드를 언제 방문하는지에 따라 정해진다.

전위 순회는 부모 노드를 먼저 방문하고 이후 왼쪽과 오른쪽 노드 순으로 방문을 하게된다.

중위 순회는 부모 노드를 중간에 방문하고 왼쪽 노드 방문 이후 부모 노드 -> 오른쪽 노드를 방문한다.

후위 순회는 부모 노드를 마지막에 방문하며 왼쪽 노드->오른쪽 노드->부모 노드 순으로 방문한다.

 

탐색을 할 때는 주로 재귀를 활용한다.

예전에는 느끼지 못했는데 재귀로 구현하는 것이 좀 더 직관적이라는 생각이 들었다.

중위 순회를 예로 든다면 루트 노드를 시작으로 탐색을 진행한다.

이때 루트 노드의 왼쪽 노드가 있다면 왼쪽노드를 탐색하고 계속해서 왼쪽 노드로 재귀호출을 한다. 이후 더 이상 왼쪽 노드에 데이터가 존재하지 않는다면 다시 돌아올 것이며 돌아오면서 부모 노드를 방문하고 해당 부모 노드의 오른쪽 노드를 방문하면서 하나의 함수가 종료된다.

 

구현

먼저 노드를 클래스로 구현을 한다.

노드를 생성할 때는 해당 노드에 들어있는 data와 연결되어 있는 노드를 각각 left와 right에 넣는다.

class Node:

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

 

이후 트리의 구조를 잡는다. tree라는 딕셔너리를 선언하고 parent를 키 값으로 Node 클래스를 value로 넣는다.

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

for _ in range(N):
    parent, left, right = map(str, input().split())
    tree[parent] = Node(data=parent, left=left, right=right)

 

아래는 순서대로 전위 순회, 중위 순회, 후위 순회를 구현한 것이다.

각각 언제 부모 노드를 출력하고 언제 어떻게 재귀호출을 하는지 살펴보면 어떠한 순회인지 알 수 있을 것이다.

def preorder(node):
    print(node.data, 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.data, 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.data, end="")

---

전체 코드

class Node:

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


def preorder(node):
    print(node.data, 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.data, 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.data, end="")


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

for _ in range(N):
    parent, left, right = map(str, input().split())
    tree[parent] = Node(data=parent, left=left, right=right)

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