[백준] 1991. 트리 순회 (실버1, Python)

트리 순회

트리 순회 안한지 너무 오래 되어서 까먹어서 좀 찾아봤다...!

전위순회: 루트 -> 완쪽 -> 오른쪽

중위순회: 왼쪽 -> 루트 -> 오른쪽

후위순회: 왼쪽 -> 오른쪽 -> 루트

 

풀이

이걸 바탕으로 재귀함수로 구현하려고 한다.

 

트리구조는 노드가 있어야 하기 때문에 노드 클래스를 만들었다. 입력 데이터를 root, left, right에 저장했다.

해당 Node 객체를 트리에 저장한다. 나중에 트리에서 빼기 쉽게 사용하도록 딕셔너리 형태를 사용했다.

q

 

 

최종 코드

class Node:
    def __init__(self, data):
        self.root = data.split()[0]
        self.left = data.split()[1]
        self.right= data.split()[2]

N = int(input())
tree_dict = {}

for i in range(0, N):
    node = Node(input()) # 노드 생성
    tree_dict[node.root] = node # tree에 노드 저장

# 전위순회: 루트 -> 왼쪽 -> 오른쪽
def preorder(root):
    if root != '.': 
        print(root, end='') # 루트
        preorder(tree_dict[root].left) # 왼쪽
        preorder(tree_dict[root].right) # 오른쪽

# 중위순회: 왼쪽 -> 루트 -> 오른쪽
def inorder(root):
    if root != '.':
        inorder(tree_dict[root].left) # 왼쪽
        print(root, end='') # 루트
        inorder(tree_dict[root].right) # 오른쪽
        

# 후위순회: 자식 노드(왼 -> 오)를 모두 확인한 후에 루트 노드를 확인
def postorder(root):
    if root != '.':
        postorder(tree_dict[root].left) # 왼쪽
        postorder(tree_dict[root].right) # 오른쪽
        print(root, end='')

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

 

 

프로그래머스 문제