이진트리 순회(DFS)

---

전위순회, 후위순회, 중위순회를 구현한 코드이다.

 

 

이진트리를 순회할 때는 재귀함수를 두번 호출하게 되는데 이 때 실행문을 어느 위치에 작성하는지에 따라

위 세가지 방법으로 출력할 수 있다.

# 전위순회 출력
def dfs(v):
    if v > 7:
        return
    #함수 호출 전 현재 노드 출력 -> 탐색 순서대로 찍힌다.
    print(v)
    dfs(v * 2)
    dfs(v * 2 + 1)

# 후위순회 출력
def dfs(v):
    if v > 7:
        return
    dfs(v * 2)
    dfs(v * 2 + 1)
    #모든 재귀호출이 끝나야 루트노드가 출력됨 -> 먼저 리턴된 재귀함수 순으로 출력된다.
    print(v)


# 중위순회 출력
def dfs(v):
    if v > 7:
        return
    #첫번째로 호출한 함수가 리턴되면 현재 노드를 출력하고 다음 재귀함수를 호출
    dfs(v * 2)
    print(v)
    dfs(v * 2 + 1)

재귀함수는 스택 자료구조를 사용하기 때문에 함수 호출 시 선입후출의 원칙에 따라 가장 늦게 호출된 함수가 가장 먼저 리턴된다.

 

이 원리에 입각해서 출력순서가 결정되는 것이다.

 

이진트리를 순회할 때 뿐만아니라 그래프를 순회할 때도 DFS탐색이라면 이 원칙을 따르기 때문에 필요에 따라 실행문의 위치를 자유자재로 사용할 수 있어야한다.