백준 1991번 : 트리 순회

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

1991번: 트리 순회

 

이진 트리에서 전위, 중위, 후위순회를 코드로 구현하는 문제이다.

각 순회는 자식을 가진 특정 노드에서, 부모 노드가 방문되는 순서에 따른 분류이다.

전위 순회 : 부모 노드를 가장 먼저 방문하고 왼쪽 자식, 오른쪽 자식 순서대로 방문한다. (parent → left → right)

중위 순회 : 왼쪽 자식을 먼저 방문하고 부모 노드, 오른쪽 자식 순서대로 방문한다. (left → parent → right)

후위 순회 : 왼쪽 자식, 오른쪽 자식을 순서대로 방문하고 마지막에 부모 노드를 방문한다. (left → right → parent)

 

Node 객체를 만들어서 프로퍼티로 부모와 왼쪽, 오른쪽 자식 노드의 이름을 갖도록 해준다. 각 순회의 종류별로 재귀를 통해 노드를 방문할 때마다 방문한 노드의 이름을 출력하도록 함수를 구현한다. 마지막으로, 노드의 이름을 Key로 하고 Node 객체를 Value로 갖는 사전 객체를 만들어주어 입력이 주어질 때 마다 각 노드의 부모, 자식관계를 설정해준 뒤 루트 노드(A)부터 순회를 진행하면 된다.

class Node:
    def __init__(self, root, left_node, right_node):
        self.root = root
        self.left_node = left_node
        self.right_node = right_node


def preorder(node):
    print(node.root, end='')
    if node.left_node != None:
        preorder(t[node.left_node])
    if node.right_node != None:
        preorder(t[node.right_node])


def inorder(node):
    if node.left_node != None:
        inorder(t[node.left_node])
    print(node.root, end='')
    if node.right_node != None:
        inorder(t[node.right_node])

def postorder(node):
    if node.left_node != None:
        postorder(t[node.left_node])
    if node.right_node != None:
        postorder(t[node.right_node])
    print(node.root, end='')

t = {}
for _ in range(int(input())):
    root, left, right = input().split()
    if left == '.':
        left = None
    if right == '.':
        right = None
    t[root] = Node(root, left, right)

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