[파이썬/알고리즘]이진트리 - 전위순회 중위순회 후위순회

DFS(Depth First Search) : 깊이우선탐색

깊이우선탐색이란, 가장 깊은 레벨까지 우선적으로 탐색하는 것!

https://ko.wikipedia.org/wiki/깊이_우선_탐색

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전

깊이우선탐색은 아래 세가지 종류가 있다.

전위순회: a → b → c

중위순회: b → a → c

후위순회: b → c → a

이진트리

다음과 같은 이진트리가 있다고 할 때, 전위순회, 중위순회, 우휘순회는 어떻게 출력값이 나오는지 알아보도록 하자.

전위순회

def DFS(x):
    if x>7:
        return
    else:
    	print(x, end=" ")      #호출하기 전에 프린트
        DFS(x*2)
        DFS(x*2+1)
        
DFS(1)

출력값: 1 2 4 5 3 6 7

- 출력 과정

DFS(1) 호출, print(1), DFS(2)호출, DFS(3) 실행 못하고 넘어감.

DFS(2) 호출, print(2), DFS(4) 호출, DFS(5) 실행 못하고 넘어감.

DFS(4) 호출, print(4), DFS(8) 호출 -> return 함수 종료.

실행 못한 DFS(5) 호출, print(5), DFS(10) 호출 -> return 함수 종료.

실행 못한 DFS(3) 호출, print(3), DFS(6) 호출, DFS(7) 실행 못하고 넘어감.

DFS(6) 호출, print(6), DFS(12) 호출 -> return 함수 종료.

 

실행 못한 DFS(7) 호출, print(7), DFS(14) -> return 함수 종료.

 

중위순회

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

 

출력값: 4 2 5 1 6 3 7 

 

후위순회

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

DFS(1)

출력값: 4 5 2 6 7 3 1

ex. 병합정렬