파이썬 백준 1991 트리 순회

n = int(input()) dic = {} for i in range(n) :     x, y1, y2 = input().split()     dic[x] = [y1, y2] def preorder(x) :     print(x, end = '')     if dic[x][0] != '.' :         preorder(dic[x][0])     if dic[x][1] != '.' :         preorder(dic[x][1]) def inorder(x) :     if dic[x][0] != '.' :         inorder(dic[x][0])     print(x, end = '')     if dic[x][1] != '.' :         inorder(dic[x][1]) def postorder(x) :     if dic[x][0] != '.' :         postorder(dic[x][0])     if dic[x][1] != '.' :         postorder(dic[x][1])     print(x, end = '') preorder('A') print() inorder('A') print() postorder('A')

몇몇 재귀함수 문제를 풀때 만들던 DFS와 구조가 같다. 이 문제에서는 문제의 요구사항이 그냥 'print'인 셈이다.

셋 모두 함수를 실행했을 때 자식이 '.'가 아니라면 그 자식에 대해 재귀하는 재귀함수를 구현하는건 똑같은데,

이때 print의 위치가 어디인지에 따라서 전위 중위 후위가 결정된다.

 

재귀함수보다 print 구문이 위에 있다면, 재귀하기 전에 자신을 먼저 출력하고 그 후 자식으로 재귀하는 함수가 실행되므로 전위 순회가 된다.

재귀함수 밑에 print 구문이 있다면, 재귀함수가 print보다 먼저 실행되는 것이 계속 반복되며 더이상 재귀가 안되는 맨 밑의 자식에 도달한다. 그리고 막내의 print 구문부터 역순으로 실행되며 재귀함수가 닫히니 후위 순회가 된다.

마지막으로 print 구문이 두 재귀함수의 사이에 있다면 왼쪽 자식의 출력보다는 나중, 오른쪽 자식의 출력보다는 먼저 print가 실행되니 중위 순회가 된다.

 

즉, 두 개의 가지로 분기하는 재귀함수 F(k, x)를 정의할 때

def F(k, x) : 

      (전위 순회가 될 부분)

      F(k-1, x)

      (중위 순회가 될 부분)

      F(k-1, x)

      (후위 순회가 될 부분)

인 셈이다.