[백준] (1991) 트리 순회 [Python]

🔗 문제 링크

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

문제

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

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

입력

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

출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

예제 입력	예제 출력
7 A B C B D . C E F E . . F . G D . . G . .	ABDCEFG DBAECFG DBEGFCA

---

💻 나의 코드

1st Try:

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

class BT:
    def __init__(self):
        self.root = None

    def add_left(self, parent_key, child_key):
        if self.root is None:
            self.root = Node(parent_key)
            
        queue = [self.root]
        while queue:
            temp = queue.pop(0)
            if temp.key == parent_key:
                if temp.left is None:
                    temp.left = Node(child_key)
                return
            if temp.left:
                queue.append(temp.left)
            if temp.right:
                queue.append(temp.right)
    
    def add_right(self, parent_key, child_key):
        if self.root is None:
            self.root = Node(parent_key)
            
        queue = [self.root]
        while queue:
            temp = queue.pop(0)
            if temp.key == parent_key:
                if temp.right is None:
                    temp.right = Node(child_key)
                return
            if temp.left:
                queue.append(temp.left)
            if temp.right:
                queue.append(temp.right)
        
    def preorder(self, node, result=None):
        if result is None:
            result = []
        if node:
            result.append(node.key)
            self.preorder(node.left, result)
            self.preorder(node.right, result)
        return result
    
    def inorder(self, node, result=None):
        if result is None:
            result = []
        if node:
            self.inorder(node.left, result)
            result.append(node.key)
            self.inorder(node.right, result)
        return result
    
    def postorder(self, node, result=None):
        if result is None:
            result = []
        if node:
            self.postorder(node.left, result)
            self.postorder(node.right, result)
            result.append(node.key)
        return result

n = int(input())
bt = BT()

for _ in range(n):
    p, cl, cr = input().split()
    if cl != ".":
        bt.add_left(p, cl)
    if cr != ".":
        bt.add_right(p, cr)

print(*bt.preorder(bt.root), sep="")
print(*bt.inorder(bt.root), sep="")
print(*bt.postorder(bt.root), sep="")

여기서 구현했던 이진 트리 코드를 사용해서 문제를 풀었지만, 메모리 초과가 발생했다.😵 트리 생성 과정에서 queue라는 리스트 구조체를 사용했는데, 이것 때문에 메모리 사용량이 크게 늘어난 것 같다.

2nd Try:

import sys
input = sys.stdin.readline

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

class Tree:
    def __init__(self):
        self.root = None

    def pre_order(self, node):
        if node is not None:
            print(node.key, end="")
            if node.left:
                self.pre_order(node.left)
            if node.right:
                self.pre_order(node.right)

    def in_order(self, node):
        if node is not None:
            if node.left:
                self.in_order(node.left)
            print(node.key, end="")
            if node.right:
                self.in_order(node.right)

    def post_order(self, node):
        if node is not None:
            if node.left:
                self.post_order(node.left)
            if node.right:
                self.post_order(node.right)
            print(node.key, end="")

n = int(input())
nodes = [None] * n
for i in range(n):
    nodes[i] = Node(chr(i+65))

tree = Tree()
tree.root = nodes[0]

for _ in range(n):
    p, l, r = input().split()
    np = nodes[ord(p)-65]
    if l != ".":
        nl = nodes[ord(l)-65]
        np.left = nl
    if r != ".":
        nr = nodes[ord(r)-65]
        np.right = nr

tree.pre_order(tree.root)
print()
tree.in_order(tree.root)
print()
tree.post_order(tree.root)
print()

여기서처럼 직접 노드에 노드를 연결하는 방식을 사용해서 코드를 작성했더니, 코드의 양이 절반으로 줄어들었고 메모리 사용량도 줄어들어 맞았습니다!! 를 받을 수 있었다.

python을 이용한 이진트리 구현과 순회

Another Code:

다음은 tmdalsehrwhs님의 코드이다.

import sys

def preorder(node):
    if node == '.':
        return ''
    
    left, right = tree[node]
    return node + preorder(left) + preorder(right)

def inorder(node):
    if node == '.':
        return ''
    
    left, right = tree[node]
    return inorder(left) + node + inorder(right)

def postorder(node):
    if node == '.':
        return ''
    
    left, right = tree[node]
    return postorder(left) + postorder(right) + node


input = sys.stdin.readline

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

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

print(preorder('A'))
print(inorder('A'))
print(postorder('A'))

나 같은 경우에는 노드의 정보를 리스트에 저장을 해서, 알파벳 정보를 숫자로 변환하는 등 번거로운 작업이 필요했다. 하지만 이 코드처럼 dict 자료형에 노드 정보를 저장한다면 더 쉽게 구현할 수 있을 것이다.