알고리즘 - Python / 백준 - 1991번 : 트리 순회

1991번: 트리 순회 (acmicpc.net)

1991번: 트리 순회

 

---

풀이

• 이진트리를 입력받고 각각 전위 순회, 중위 순회, 후위 순회의 결과를 출력하면 된다.
• 이진트리를 배열에 입력받고 그에 따라 전위 순회 , 중위 순회, 후위 순회를 구현하여 정답을 출력하였다.
• 전위 순회, 중위 순회, 후위 순회의 경우 재귀 함수를 이용해 쉽게 구현할 수 있다.

 

import sys
n = int(sys.stdin.readline())
stack = [[] for i in range(n)]
for _ in range(n):
    a,b,c = input().split(" ")
    aa = ord(a) - 65
    if b == ".":
        bb = -1
    else:
        bb = ord(b) - 65
    if c == ".":
        cc = -1
    else:
        cc = ord(c) - 65
    stack[aa] = stack[aa] + [bb,cc]

visited_1 = []
visited_2 = []
visited_3 = []

def first(stack,root_node):
    global visited_1
    if root_node == -1:
        return
    else:
        visited_1.append(root_node)
        first(stack,stack[root_node][0])
        first(stack,stack[root_node][1])

def second(stack,root_node):
    global visited_2
    if root_node == -1:
        return
    else:
        second(stack, stack[root_node][0])
        visited_2.append(root_node)
        second(stack,stack[root_node][1])

def third(stack,root_node):
    global visited_3
    if root_node == -1:
        return
    else:
        third(stack,stack[root_node][0])
        third(stack,stack[root_node][1])
        visited_3.append(root_node)

first(stack,0)
second(stack,0)
third(stack,0)

ans_1 = ""
ans_2 = ""
ans_3 = ""
for i in range(0,n):
    ans_1 += chr(visited_1[i]+65)
    ans_2 += chr(visited_2[i] + 65)
    ans_3 += chr(visited_3[i] + 65)
print(ans_1)
print(ans_2)
print(ans_3)

---