[알고리즘/백준] 1991번 : 트리 순회(python)

재귀를 이용했다.

1. 노드를 만들기 위해 딕셔너리를 사용하여 노드를 저장했다.

2. 전위 순회는 루트, 왼쪽 자식, 오른쪽 자식순으로 방문한다.

3. 만약 왼쪽이 비어있지 않으면 왼쪽 자식을 넣고 재귀를 돌린다.

4. 전위 순회는 방문하면 바로 출력한다.

5. 더이상 가지 못하면 오른쪽 자식으로 간다.

이런 방법으로 전위 순회는 방문 하면 바로 출력하고

중위 순회는 왼쪽 자식 - 루트 - 오른쪽 자식 순이기 때문에 왼쪽 끝까지 가서 반대로 출력해온다.

후위 순회 또한 왼쪽 자식 끝까지 갔다가 루트가 아닌 오른쪽 자식으로 간다.

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


def pre(node):
    print(node.data, end='')
    if node.left != '.':
        pre(tree[node.left])
    if node.right != '.':
        pre(tree[node.right])


def inorder(node):
    if node.left != '.':
        inorder(tree[node.left])
    print(node.data, end='')
    if node.right != '.':
        inorder(tree[node.right])


def post(node):
    if node.left != '.':
        post(tree[node.left])
    if node.right != '.':
        post(tree[node.right])
    print(node.data, end='')


N = int(input())
tree = {}
for _ in range(N):
    d, l, r = input().split()
    tree[d] = Node(d, l, r)

pre(tree['A'])
print()
inorder(tree['A'])
print()
post(tree['A'])```