[Python] BOJ 1191 : 트리 순회

👉 백준 1191: 트리 순회

✔️ 문제 풀이 포인트

class Node: # 바이너리 트리를 구성 할 노드 클래스 생성
    def __init__(self, data):
        self.data = data;
        self.left = None;
        self.right = None;

바이너리 트리는 data, left, right 멤버를 가진 노드 클래스를 생성하면 문제를 쉽게 다룰 수 있다.

def preorder(node): # 전위 순회
    print(node.data, end='')
    if node.left != '': preorder(node.left)
    if node.right != '': preorder(node.right)

def inorder(node): # 중위 순회
    if node.left != '': inorder(node.left)
    print(node.data, end='')
    if node.right != '': inorder(node.right)

def postorder(node): # 후위 순회
    if node.left != '': postorder(node.left)
    if node.right != '': postorder(node.right)
    print(node.data, end='')

• 전위 순회는 해당 노드 먼저 출력, 그 후 좌-우 재귀
• 중위 순회는 좌 재귀 후 노드 출력, 그리고 마지막으로 우 재귀
• 후위 순회는 좌-우 재귀 후 마지막으로 노드 출력이 이뤄지는 간단한 함수이다.

# 자식 노드들 중 . 으로 입력된 데이터는 공백으로 처리
    if data[1] == '.': data[1] = ''
    if data[2] == '.': data[2] = ''

다만, 위와 같이 입력받는 자식 노드의 데이터가 . 일 때, '' 로 처리하였기 때문에 자식 노드로 재귀 진입시 if문 처리를 제대로 하지않으면 아래와 같은 에러가 발생한다.

AttributeError: 'str' object has no attribute 'left'

for i in range(n):
    for j in range(n):
        # 트리 리스트들의 부모 노드와 자식 노드들을 서로 매칭시켜 트리 구성
        if tree_li[i].data == tree_li[j].left: tree_li[j].left = tree_li[i]
        elif tree_li[i].data == tree_li[j].right: tree_li[j].right = tree_li[i]

• n^2 으로 노드 인스턴스들이 추가된 트리 리스트를 돌면서 노드들을 서로 연결해주어 바이너리 트리를 구성한다.

✏️ 전체 코드

import sys
input = sys.stdin.readline

class Node: # 바이너리 트리를 구성 할 노드 클래스 생성
    def __init__(self, data):
        self.data = data;
        self.left = None;
        self.right = None;

def preorder(node): # 전위 순회
    print(node.data, end='')
    if node.left != '': preorder(node.left)
    if node.right != '': preorder(node.right)

def inorder(node): # 중위 순회
    if node.left != '': inorder(node.left)
    print(node.data, end='')
    if node.right != '': inorder(node.right)

def postorder(node): # 후위 순회
    if node.left != '': postorder(node.left)
    if node.right != '': postorder(node.right)
    print(node.data, end='')

n = int(input())
tree_li = []
for i in range(n):
    data = input().split()
    node = Node(data[0]) # 부모 노드는 데이터로 저장하여 클래스 생성

    # 자식 노드들 중 . 으로 입력된 데이터는 공백으로 처리
    if data[1] == '.': data[1] = ''
    if data[2] == '.': data[2] = ''

    # 자식 노드 저장
    node.left = data[1] 
    node.right = data[2]
    
    # 노드 클래스들을 트리 리스트에 추가
    tree_li.append(node)

for i in range(n):
    for j in range(n):
        # 트리 리스트들의 부모 노드와 자식 노드들을 서로 매칭시켜 트리 구성
        if tree_li[i].data == tree_li[j].left: tree_li[j].left = tree_li[i]
        elif tree_li[i].data == tree_li[j].right: tree_li[j].right = tree_li[i]

preorder(tree_li[0])
print()
inorder(tree_li[0])
print()
postorder(tree_li[0])