백준 1991 트리 순회

본격적으로 코딩 테스트를 준비하면서, 자료구조와 트리에 대해서 공부하고 있다.

트리의 경우는 원리는 이해하고 있었지만 코드로 구현하는데 어려움을 느꼈던 부분이다.

 

Python에서는 class로 객체지향 프로그래밍을 구현할 수 있다.

트리 순회 코드를 구현하는데 이 방법 외의 방법을 사용해도 되지만, 코딩 테스트를 보는 회사들의 취지를 고려한다면 객체지향에 맞게 구현하는 것이 좋을 것 같다.

 

 

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

pre_array = []
in_array = []
post_array = []
def preorder(node):  # 전위 순회
    pre_array.append(node.item)
    if node.left != '.':
        preorder(tree[node.left])
    if node.right != '.':
        preorder(tree[node.right])


def inorder(node):  # 중위 순회
    if node.left != '.':
        inorder(tree[node.left])
    in_array.append(node.item)
    if node.right != '.':
        inorder(tree[node.right])


def postorder(node):  # 후위 순회
    if node.left != '.':
        postorder(tree[node.left])
    if node.right != '.':
        postorder(tree[node.right])
    post_array.append(node.item)


if __name__ == "__main__":

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

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

    preorder(tree['A'])
    inorder(tree['A'])
    postorder(tree['A'])
  
    print("".join(pre_array))
    print("".join(in_array))
    print("".join(post_array))

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