백준 - 트리 순회(1991)

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

---

문제 설명

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

제한조건

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

---

코드

import sys
input = sys.stdin.readline
print = sys.stdout.write

class Node:
    def __init__(self, val) -> None:
        self.val = val
        self.left = None
        self.right = None

    def insert(self, val, left, right):
        if self.val == val:
            self.left = Node(left)
            self.right = Node(right)
        else:
            if self.left:
                self.left.insert(val, left, right)
            if self.right:
                self.right.insert(val, left, right)
    
    def preOrder(self): # VLR
        if self.val != '.':
            print(self.val)
        if self.left:
            self.left.preOrder()
        if self.right:
            self.right.preOrder()
    
    def inOrder(self): #LVR
        if self.left:
            self.left.inOrder()
        if self.val != '.':
            print(self.val)
        if self.right:
            self.right.inOrder()

    def postOrder(self): #LRV
        if self.left:
            self.left.postOrder()
        if self.right:
            self.right.postOrder()
        if self.val != '.':
            print(self.val)

N = int(input()) - 1
root, left, right = input().split()
tree = Node(root)
tree.left = Node(left)
tree.right = Node(right)

for _ in range(N):
    val, left, right = input().split()
    tree.insert(val, left, right)

tree.preOrder()
print('\n')
tree.inOrder()
print('\n')
tree.postOrder()

---

아이디어

트리의 구현문제라고 생각해도 맞을 것 같다.

class로 Node를 만들어 이진트리이니 자식 노드 left, right를 지정할 수 있게 하고, 새로운 노드 삽입의 경우 root 노드에서부터 모든 노드를 돌아서 넣을려 하는 노드의 부모노드에 도달하면 자식으로 넣어주는 방식으로 했다.

* 노드의 값이 중복인 문제라면 구조를 조금 변형해야겠다.