[알고리즘] 이진트리 순회 깊이우선 탐색 (DFS)

(문제) 이진트리 순회 깊이우선 탐색 (DFS)

---

아래 그림과 같은 이진트리를 전위순회와 후위순회를 하시오.

출력설명

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

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

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

---

해결방법

전위 순회 방식

부모 node에서 시작하여 왼쪽으로 뻗는다.

위의 이진트리를 보면 루트 노드가 1이다.

깊이우선탐색 함수를 dfs로 정의하면 dfs(1)이 루트 노드인 것이다.

왼쪽 자식은 dfs(2), 오른쪽 자식은 dfs(3) 이다.

dfs(2)가 부모로 기준을 잡으면 왼쪽 자식은 dfs(4)이고, 오른쪽 자식은 dfs(5)이다.

식으로 풀어써보면 dfs(n) 이 부모일 경우, 왼쪽 자식은 dfs(n*2) 오른쪽 자식은 dfs(n*2+1)이다.

중위 순회 방식

왼쪽자식 --> 부모 --> 오른쪽자식

부모가 아니며 왼쪽자식인 경우 먼저 출력 –> 해당 왼쪽자식의 부모 출력 –> 해당 왼쪽자식 부모의 오른쪽 자식 출력

후위 순회 방식

왼쪽자식 --> 오른쪽자식 --> 부모

부모가 아니며 왼쪽자식인 경우 먼저 출력 –> 해당 왼쪽자식 부모의 오른쪽 자식 출력 –> 해당 왼쪽자식의 부모 출력

동작 시각화 (예 : 후위 순회 방식)

위의 방식과 같이 재귀적으로 반복한다면 후위 순회 방식으로 깊이우선탐색을 한다!

---

코드

전위 순회 방식

# 재귀함수 이용
def dfs(v):
    if v > 7:
        return
    else:
        # 전위 순회
        print(v, end=' ')
        # 왼쪽 자식 콜
        dfs(v*2)
        # 오른쪽 자식 콜
        dfs(v*2+1)

dfs(1)

중위 순회 방식

# 재귀함수 이용
def dfs(v):
    if v > 7:
        return
    else:
        # 왼쪽 자식 콜
        dfs(v*2)
        # 중위 순회 방식
        print(v, end=' ')
        # 오른쪽 자식 콜
        dfs(v*2+1)

dfs(1)

후위 순회 방식

# 재귀함수 이용
def dfs(v):
    if v > 7:
        return
    else:
        # 왼쪽 자식 콜
        dfs(v*2)
        # 오른쪽 자식 콜
        dfs(v*2+1)
        # 후위 순회
        print(v, end=' ')

dfs(1)