[알고리즘] 이진 트리 순회 알고리즘 / 백준 파이썬 1991번

이진트리

데이터의 탐색 속도 증진을 위해 사용하는 구조

포화 이진 트리(Full Binary Tree)

완전 이진 트리(Complete Binary Tree)

오른쪽 노드부터 차례로 없는 트리

이진트리 순회 알고리즘

전위 순회(Preorder Traversal)

루트 ‣ 왼쪽 ‣ 오른쪽

중위 순회(Inorder Traversal)

왼쪽 ‣ 루트 ‣ 오른쪽

후위 순회(Postorder Traversal)

왼쪽 ‣ 오른쪽 ‣ 루트

백준 1991 파이썬

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


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

for _ in range(N):
    value, left, right = input().split()
    node = Node(value, left, right)
    dic[value] = node


# 뿌리 -> 왼 -> 오
def pre_order(key):
    node = dic[key]
    print(node.value, end="")  
    # 왼쪽 먼저 진행이므로 left 이후 right
    if node.left != ".":
        pre_order(node.left)
    if node.right != ".":
        pre_order(node.right)


# 왼 -> 뿌리 -> 오
def in_order(key):
    node = dic[key]
    if node.left != ".":
        in_order(node.left)
    print(node.value, end="") 
    if node.right != ".":
        in_order(node.right)


# 왼 -> 오 -> 뿌리
def post_order(key):
    node = dic[key]
    if node.left != ".":
        post_order(node.left)
    if node.right != ".":
        post_order(node.right)
    print(node.value, end="")  


pre_order("A")
print()
in_order("A")
print()
post_order("A")

출처:
https://www.youtube.com/watch?v=z_tzHoPfllA
https://sites.google.com/site/cbnualgorithm2019/home/project/binarytreeijinteuli