백준 1991번 : 트리 순회 [Python]

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

1991번: 트리 순회

문제를 정리하자면 트리가 주어졌을 때 전위, 중위, 후위 순회로 읽어내면 된다.

트리는 [자기자신, 왼쪽 자식, 오른쪽 자식] 형태로 모든 노드가 주어진다.

 

전체 코드

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

for i in range(N): #트리를 입력받아
    root, left, right = input().split()
    tree[root] = [left, right]
   
class Node(object):
    def __init__(self, item):
        self.item = item
        self.left = self.right = None

class BinaryTree(object):
    def __init__(self):
        self.root = None

def preorder(root):
    if(root != ".") :
        print(root, end = "")
        preorder(tree[root][0]) #left
        preorder(tree[root][1]) #right

def inorder(root):
    if(root != "."):
        inorder(tree[root][0]) #left
        print(root, end="")
        inorder(tree[root][1]) #right

def postorder(root):
    if root != ".":
        postorder(tree[root][0]) #left
        postorder(tree[root][1]) #right
        print(root, end="")

        

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

풀이

0. 노드의 개수만큼 트리의 정보를 입력받는다. -> map 형태로 저장, tree[root] = [left값, right값] 을 집어넣음

root가 key이고 left,right가 value값이다.

1. 전위순회 함수 : 루트 - 왼쪽 - 오른쪽

root 출력

tree[root][0] = 왼쪽 자식을 인수로 하여 함수 호출

    root 출력 (왼쪽 자식을 출력하게됨)

    tree[root][0] = 왼쪽자식의 왼쪽자식을 root로 하는 함수 호출

        root 출력 (왼쪽 자식의 왼쪽 자식)

    왼쪽 자식이 없을 때까지 계속 호출 

tree[root][1] = 오른쪽 자식을 인수로 하는 함수 호출

    root 출력 (오른쪽 자식 출력)

    tree[root][0] = 오른쪽 자식의 왼쪽 자식을 인수로 함수 호출 ---> 없다면 함수 빠져나옴

    tree[root][1] = 오른쪽 자식의 오른쪽 자식을 인수로 함수호출

루트 - 왼쪽 자식 - 오른쪽 자식 순으로 출력되게끔 함수를 구성

 

2. 후위, 중위 순회로 전위순회와 같은 방식으로 함수 생성

    중위순회는 왼쪽 - 루트 - 오른쪽 순이므로

    print(tree[root][0])

    print(root)

    print(tree[root][1]) 

    후위 순회는 왼쪽 - 오른쪽 - 루트 순이므로

    print(tree[root][0])

    print(tree[root][1])

    print(root)

    로 구성된다.