[백준 2024/09/15] 1991번 트리 순회

1. 문제

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

 

2. 접근 방법

오랜만에 전위 순회, 중위 순회, 후위 순회에 대해서 다시 개념을 잡고 가는 문제였다.

첫 번째 예제를 바탕으로 더 자세히 알아보았다.

근데 A가 root이며 left node, right node가 순차적으로 나온다.

이를 정의 한 Class Node에 저장을 통해, 노드의 left node와 right node를 .left와 .right로 접근할 수 있도록 하였다.

 

 

전위 순회를 구현하기 위해 Class Node를 작성하였다.

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

만약 Node class가 불러와서 이용되기 위해 호출이 되었다면, def __init__으로 기본 설정을 할 수 있도록 하였다. 일종의 constructor

 

또한, nodes['.']을 찾아서 값을 다음 함수로 넘겨줘야 하기 때문에, 해당 노드에 대한 선언도 포함해 주었다.

nodes = {'.': Node('.', None, None)}

 

전위 순회는 (root)(left_node)(right_node) 순으로 나오게 된다.

 

중위 순회는 (left_node)(root)(right_node)순으로 출력될 수 있도록 하였다.

마지막으로 후위 순회는 (left_node)(right_node)(root) 순으로 출력될 수 있도록 하였다.

 

이번에 Class 를 다시 배워보게 되는 기회가 되었었으며 순회에 대해서도 다시 remind 하는 시간이었다.

 

3. 코드

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


def preorder(curr_node):
    if curr_node.root == '.':
        return ''

    return curr_node.root + preorder(nodes[curr_node.left]) + preorder(nodes[curr_node.right])


def inorder(curr_node):
    if curr_node.root == '.':
        return ''

    return inorder(nodes[curr_node.left]) + curr_node.root + inorder(nodes[curr_node.right])


def postorder(curr_node):
    if curr_node.root == '.':
        return ''

    return postorder(nodes[curr_node.left]) + postorder(nodes[curr_node.right]) + curr_node.root


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

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