[백준] 1991번 트리 순회 파이썬 풀이

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

1991번: 트리 순회

---

1. 접근 방식

• 왼쪽 자식, 오른쪽 자식을 가지는 Node 클래스를 구현하자.

배열로 이진 트리를 표현하는 것보단 실제 이진 트리와 비슷하게 구현하는 편이 더 수월할 것이라고 생각했다. 따라서 실제 이진 트리의 노드처럼 왼쪽 자식, 오른쪽 자식을 갖는 Node 클래스를 작성했다.

 

 

• 딕셔너리로 트리를 표현하자.

key는 해당 노드의 value, value는 해당 노드 인스턴스를 저장한다.

 

 

• 순회 클래스를 생성하자.

사실 전위 / 중위 / 후위 순회를 각 함수로 구현해도 되지만, Node 클래스를 생성했기 때문에 통일감을 주고 싶어 Traverse라는 순회 클래스를 작성했다.

Traverse 객체 생성 시 트리(딕셔너리)를 인자로 넘겨준다. preOrder, inOrder, postOrder 메서드가 존재하고 각 메서드의 인자는 노드의 value이다. 처음 메서드를 호출할 때는 루트 노드의 value인 "A"를 넣어준다.

재귀를 사용하면 쉽게 전위 / 중위 / 후위 순회 코드를 작성할 수 있다. 전위 / 중위 / 후위 순회에 따라 현재 노드 값을 출력하는 문장을 재귀 호출 이전, 중간, 이후에 작성하면 된다.

 

 

 

2. 정답 코드

class Node:
    def __init__(self, value, left, right):
        self.value = value
        self.left = left if left != "." else None
        self.right = right if right != "." else None

class Traverse:
    def __init__(self, nodes):
        self.tree = nodes

    def preOrder(self, node):
        print(self.tree[node].value, end="")

        if self.tree[node].left:
            self.preOrder(self.tree[node].left)

        if self.tree[node].right:
            self.preOrder(self.tree[node].right)

    def inOrder(self, node):
        if self.tree[node].left:
            self.inOrder(self.tree[node].left)

        print(self.tree[node].value, end="")

        if self.tree[node].right:
            self.inOrder(self.tree[node].right)

    def postOrder(self, node):
        if self.tree[node].left:
            self.postOrder(self.tree[node].left)

        if self.tree[node].right:
            self.postOrder(self.tree[node].right)

        print(self.tree[node].value, end="")


# main
n = int(input())
tree = dict()

for _ in range(n):
    value, child1, child2 = input().split()
    tree[value] = Node(value, child1, child2)

traverse = Traverse(tree)

traverse.preOrder('A')
print()
traverse.inOrder('A')
print()
traverse.postOrder('A')

 

 

 

3. 더 짧고, 더 빠른 정답 코드

이 문제에서는 실제로 Node 클래스를 작성하지 않아도 문제를 해결할 수 있다. 딕셔너리가 트리 역할인 것은 동일하지만, 딕셔너리 value에는 (왼쪽 자식, 오른쪽 자식) 튜플이 들어간다. 또한 Traverse 클래스 대신 일반 함수로 순회 함수를 구현한다.

def preOrder(node):
    print(node, end="")

    if tree[node][0] != ".":
        preOrder(tree[node][0])

    if tree[node][1] != ".":
        preOrder(tree[node][1])

def inOrder(node):
    if tree[node][0] != ".":
        inOrder(tree[node][0])

    print(node, end="")

    if tree[node][1] != ".":
        inOrder(tree[node][1])

def postOrder(node):
    if tree[node][0] != ".":
        postOrder(tree[node][0])

    if tree[node][1] != ".":
        postOrder(tree[node][1])

    print(node, end="")


# main
n = int(input())
tree = dict()

for _ in range(n):
    value, left, right = input().split()
    tree[value] = (left, right)

preOrder('A')
print()
inOrder('A')
print()
postOrder('A')