#144 백준 파이썬 [1991] 트리 순회

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

 

#Solution

전위 중위 후위순위를 푸는 방법은 트리의 탐색 순서에 따라 다르다. 순회 순서가 명확해야 알고리즘도 짜기 쉬워진다.

https://codingstarter.tistory.com/6?category=935492를 참조하면 순서대로 쉽게 이해할 수 있다.

아울러 파이썬으로 짤 때는 딕셔너리를 이용하여 빠르게 찾았다. {'A': [B, C]} 이런 식으로 부모 자식간의 관계를 만들어줬다.

이해를 쉽게 하기 위해서 해당 딕셔너리를 node_graph로 바꾸다 보니 함수들이 길어졌다.

포인터가 없는 파이썬은 C와는 다르게 트리가 구현된다.

node = int(input())
node_graph = {i:[] for i in "ABCDEFGHIJKLMNOPQRSTUVWXYZ"}

#트리를 딕셔너리로 생성
for _ in range(node):
    node, left, right = map(str, input().split())
    node_graph[node] += [left, right]

#전위순회
def preorder(node_graph, root):
    stack = [root]
    result = ''

    while stack:
        node = stack.pop()
        result += node

        if node_graph[node][1] != '.':
            stack.append(node_graph[node][1])
            
        if node_graph[node][0] != '.':
            stack.append(node_graph[node][0])
            
    return result


#중위순회
def inorder(node_graph, root):
    stack = [root]
    result = ''
    
    while stack:
        if node_graph[stack[-1]][0] != '.' and node_graph[stack[-1]][0] not in result:
            stack.append(node_graph[stack[-1]][0])
            
        elif stack[-1] in result:
            stack.append(node_graph[stack[-1]][1])
            
        else:
            node = stack.pop()
            result += node
            if node_graph[node][1] != '.':
                stack.append(node_graph[node][1])
                
    return result

#후위순회
def postorder(node_graph, root):
    stack = [root]
    result = ''
    
    while stack:
        if node_graph[stack[-1]][0] != '.' and node_graph[stack[-1]][0] not in result:
            stack.append(node_graph[stack[-1]][0])
            
        elif node_graph[stack[-1]][1] == '.' or node_graph[stack[-1]][1] in result:
            result += stack.pop()
            
        else:
            stack.append(node_graph[stack[-1]][1])
            
    return result


print(preorder(node_graph, "A"))
print(inorder(node_graph, "A"))
print(postorder(node_graph, "A"))