[Python] 백준 1991번 문제, 트리 순회

<문제 링크>

 

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

1991번: 트리 순회

 

---

<풀이>

 

트리 순회로 전위 순회, 중위 순회, 후위 순회를 수행해야 한다.

기본적인 자료구조 문제이기 때문에 그닥 어렵진 않다.

각각의 순회 작동 원리를 알면 누구나 쉽게 구현할 수 있다.

그럼 여기서 말하는 순회 작동 원리가 무엇이냐?

{ 나 자신 -> 왼쪽 자식 -> 오른쪽 자식 }인 트리 탐색 순서를 이야기하는 것이다.

이 원리만 알고 있으면, OO 순회에서 OO 부분에 알맞게 원리 적용만 바꿔주면 된다.

 

즉, 다음과 같이 진행하며 모든 탐색의 시작은 ROOT이다.

전위는 출력 -> 왼쪽 자식 탐색() -> 오른쪽 자식 탐색()

중위는 왼쪽 자식 탐색() -> 출력 -> 오른쪽 자식 탐색()

후위는 왼쪽 자식 탐색() -> 오른쪽 자식 탐색() -> 출력

 

왼쪽 자식 탐색(), 오른쪽 자식 탐색()와 같이 메소드로 표시한 이유는 단순히 1회만 수행하는 것이 아니라 재귀함수로 탐색을 해야 하기 때문이다.

 

그리고 Python에서는 생성자가 오버라이딩이 안 된다고 한다. 자바를 쓰다가 넘어 와서 각 상황에 맞는 생성자를 구현했었는데 에러가 발생해 조사를 해보니 Python에서는 하나의 생성자만 사용하며, default 값을 주어 오버라이딩과 비슷하게 사용할 수 있다고 한다.

 

---

<코드>

Node: {

key: Node의 알파벳 값,

left: 왼쪽 자식 Node 정보,

right: 오른쪽 자식 Node 정보

}

---

import sys

class Node:
    key = None
    left = None
    right = None

    # constructor
    def __init__(self, value, left=".", right="."):
        self.key = value
        if left != '.':
            self.left = Node(left)
        if right != '.':
            self.right = Node(right)

    # find root
    def find_tree(self, value, left, right):
        if self.key == value:
            self.left = Node(left)
            self.right = Node(right)

        if self.left is not None:
            self.left.find_tree(value, left, right)

        if self.right is not None:
            self.right.find_tree(value, left, right)
    
    # 전위 순회
    def first_traversal(self):
        if self.key != '.':
            print(self.key, end="")

        if self.left is not None:
            self.left.first_traversal()

        if self.right is not None:
            self.right.first_traversal()

    # 중위 순회
    def middle_traversal(self):
        if self.left is not None:
            self.left.middle_traversal()

        if self.key != '.':
            print(self.key, end="")

        if self.right is not None:
            self.right.middle_traversal()

    # 후위 순회
    def last_traversal(self):
        if self.left is not None:
            self.left.last_traversal()

        if self.right is not None:
            self.right.last_traversal()

        if self.key != '.':
            print(self.key, end="")

if __name__ == '__main__':
    N = int(sys.stdin.readline())
    tree = Node('A')

    # input
    for _ in range(N):
        k, l, r = sys.stdin.readline().split()
        tree.find_tree(k, l, r)

    # logic
    tree.first_traversal()
    print()
    tree.middle_traversal()
    print()
    tree.last_traversal()