[python] 백준 1991번 트리 순회

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

1991번: 트리 순회

 

 

 

💻 코드

 

import sys

input = sys.stdin.readline


class Node:  # 노드 생성
    def __init__(self, data, left_node, right_node):
        self.data = data
        self.left_node = left_node
        self.right_node = right_node


def preorder(node):  # 전위 순회 VLR
    print(node.data, end='')
    if node.left_node != '.':
        preorder(tree[node.left_node])
    if node.right_node != '.':
        preorder(tree[node.right_node])


def inorder(node):  # 중위 순회 LVR
    if node.left_node != '.':
        inorder(tree[node.left_node])
    print(node.data, end='')
    if node.right_node != '.':
        inorder(tree[node.right_node])


def postorder(node):  # 후위 순회 LRV
    if node.left_node != '.':
        postorder(tree[node.left_node])
    if node.right_node != '.':
        postorder(tree[node.right_node])
    print(node.data, end='')


n = int(input())
tree = {}  # dictionary 사용

for i in range(n):
    data, left_node, right_node = input().split()
    tree[data] = Node(data, left_node, right_node)

preorder(tree['A'])
print()
inorder(tree['A'])
print()
postorder(tree['A'])

 

 

📝 풀이

 

이진 트리의 개념은 자료구조에서 배운 개념이다.

 

이진 트리 개념

 

간단하게 이진 트리를 설명하면,

트리의 차수가 2인 트리로 왼쪽 자식 노드와 오른쪽 자식 노드를 가지는 트리

 

라고 할 수 있다.

 

 

또한 이진 트리의 구조는 재귀적이므로 재귀 함수를 이용하여 구현할 수 있다.

 

 

이진 트리 생성

 

이전에 배웠던 C언어에서는 노드를 생성할 때 노드 구조체를 만들어 데이터 필드를 만들고 포인터를 이용하여 왼쪽 링크 필드와 오른쪽 링크 필드를 만들었었다.

 

 

하지만 파이썬에서는 클래스를 생성하고 클래스 안에 생성자를 만들어야한다. 생성자에는 각 객체를 초기화해준다.

* 생성자(Constructor) : 객체가 생성될 때 자동으로 호출되는 메서드

 

class Node:  # 노드 생성
    def __init__(self, data, left_node, right_node):
        self.data = data
        self.left_node = left_node
        self.right_node = right_node

 

 

트리는 딕셔너리(dictionary)를 이용하여 생성하고 각 노드와 왼쪽, 오른쪽 노드 변수에 입력을 받은 뒤 만들었던 클래스 호출하여 노드를 생성할 수 있다.

 

tree = {}  # dictionary 사용

for i in range(n):
    data, left_node, right_node = input().split()
    tree[data] = Node(data, left_node, right_node)

 

 

이진 트리 순회 (traversal)

 

이진 트리 순회란,

모든 원소를 빠트리거나 중복하지 않고 체계적으로 방문하는 것

 

을 의미한다.

 

 

이진 트리 순회는 이진 트리가 재귀적으로 정의되어 구성되어 있으므로 순회 작업도 서브 트리에 대해서 재귀적으로 반복하며 수행한다.

 

이진 트리의 순회의 종류는 3가지이다.

 

V : 현재 노드 방문

L : 왼쪽 서브 트리 방문

R : 오른쪽 서브 트리 방문

 

• 전위 순회 (preorder traversal) : V -> L -> R
• 중위 순회 (inorder traversal) : L -> V -> R
• 후위 순회 (postorder traversal) : L -> R -> V

 

이를 코드로 바꾸면,

 

현재 노드 방문

 

print(node.data, end='')

 

 

왼쪽 서브 트리 방문

 

if node.left_node != '.': # 왼쪽 노드가 존재한다면
        preorder(tree[node.left_node])

 

 

오른쪽 서브 트리 방문

 

if node.right_node != '.': # 오른쪽 노드가 존재한다면
        preorder(tree[node.right_node])

 

 

이와 같이 작성할 수 있다.