[파이썬 알고리즘 문제풀이 입문] 완전탐색 (백트랙킹, 상태트리와 CUT EDGE) / DFS(깊이우선탐색) 기초 - 이진트리 순회 (DFS)

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다.

 

 

 

문제

아래 그림과 같은 이진트리를 전위순회와 후위순회를 연습해보세요.

1) 전위순회 출력 : 1 2 4 5 3 6 7
2) 중위순회 출력 : 4 2 5 1 6 3 7
3) 후위순회 출력 : 4 5 2 6 7 3 1

cf.) 전위 / 중위 / 후위 가 결정되는 기준 :  Root 노드에 방문을 하는 시점 (제일 먼저 / 중간에 / 나중에)

 

 

 

풀이

• 내 풀이 - 전위순회

import sys
input = sys.stdin.readline

def DFS(num):
    if num > 7:
        return
    else:
        print(num, end=" ")
        DFS(num*2)
        DFS(num*2+1)
    
DFS(1)

• 내 풀이 - 중위순회

import sys
input = sys.stdin.readline

def DFS(num):
    if num > 7:
        return
    else:
        DFS(num*2)
        print(num, end=" ")
        DFS(num*2+1)
    
DFS(1)

• 내 풀이 - 중위순회

import sys
input = sys.stdin.readline

def DFS(num):
    if num > 7:
        return
    else:
        DFS(num*2)
        DFS(num*2+1)
        print(num, end=" ")
    
DFS(1)

- 기본적으로 재귀함수를 이용하되, 조건은 num이 7을 초과할 경우에 return을 해준다.

- 트리의 노드의 값을 따져보면,

  왼쪽(L) 노드 = 가운데 노드 x 2 / 오른쪽(R) 노드 = 가운데 노드 x 2 + 1   로 구성되어 있다.

- print의 시점을 전위 / 중위 / 후위 에 따라서 위치시켜주면 된다.