Algorithm - 이진트리 순회(DFS : Depth First Search)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[이진트리 순회(DFS)]

 

아래와 그림을 참조하여, 이진트리의 전위순회·중위순회·후위순회를 출력하는 프로그램을 작성하시오.

 

이진트리

 

 

*입력 설명

첫 번째 줄에 이진트리의 루트노드 값이 주어진다.

 

*출력 설명

첫 번째 줄에 전위순회·중위순회·후위순회의 결과 값을 출력한다.

 

 

---

 

 

풀이(Python)

답안(전위순회)

import sys
sys.stdin = open('AA/input_44.txt', 'rt')

def DFS(v):
    if v > 7:
        return
    else:
        print(v, end=' ')
        DFS(v*2)
        DFS(v*2+1)
        
if __name__ =="__main__":
    n = int(input())
    DFS(n)

# 출력 : 1 2 4 5 3 6 7

 

답안(중위순회)

import sys
sys.stdin = open('AA/input_44.txt', 'rt')

def DFS(v):
    if v > 7:
        return
    else:
        DFS(v*2)
        print(v, end=' ')
        DFS(v*2+1)
        
if __name__ =="__main__":
    n = int(input())
    DFS(n)
    
# 출력 : 4 2 5 1 6 3 7

 

답안(후위순회)

import sys
sys.stdin = open('AA/input_44.txt', 'rt')

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

if __name__ =="__main__":
    n = int(input())
    DFS(n)
    
# 출력 : 4 5 2 6 7 3 1

 

input_44.txt(입력)

1

 

 

중요내용

1. 이진트리를 탐색하는 방법에는 DFS(깊이우선탐색)와 BFS(넓이우선탐색)가 있다.
2. 깊이우선탐색은 이진트리를 밑으로 파고들면서 탐색하는 방법이다.
3. 넓이우선탐색은 이진트리를 레벨순으로 내려가면서 탐색하는 방법이다. (추후에 다룰 예정)
4. DFS에서 전위순회는 자신의 노드(부모노드)를 출력하고, 왼쪽 자식노드와 오른쪽 자식노드 순서로 방문하여 출력한다. (부모노드 -> 왼쪽 자식노드 -> 오른쪽 자식노드)
5. DFS에서 중위순회는 왼쪽 자식노드를 출력하고, 부모노드와 오른쪽 자식노드 순서로 방문하여 출력한다. (왼쪽 자식노드 -> 부모노드 -> 오른쪽 자식노드)
6. DFS에서 후위순회는 왼쪽 자식노드를 출력하고, 오른쪽 자식노드와 부모노드 순서로 방문하여 출력한다. (왼쪽 자식노드 -> 오른쪽 자식노드 -> 부모노드)
7. 단, 중위순회와 후위순회는 가장 밑 레벨의 왼쪽 자식노드부터 탐색을 시작한다.
8. 또한, 중위순회와 후위순회는 자식노드가 존재하면 무조건 부모노드보다 우선적으로 자식노드를 탐색한다.
9. 부모노드 값에 2를 곱하면 왼쪽 자식노드 값이 되고, 부모노드 값에 2를 곱한 후 1을 더하면 오른쪽 자식노드 값이 된다. (ex. DFS(v*2) : 왼쪽 자식노드 값, DFS(v*2+1) : 오른쪽 자식노드 값)
10. 참고로, 후위순회는 주로 병합정렬에서 사용되며 가장 많이 사용되는 순회방식은 전위순회이다.
11. 위의 세 가지 순회방식은 당연히 스택 자료구조를 활용한다.