TIL no.7-Python 이진트리순회(DFS:Depth First Search)

재귀함수와 스텍(중요)

DFS를 알아보기 전에 꼭 재귀 함수와 스택에 대한 개념을 꼭 알고 있어야 한다.

사진과 같이 재귀 함수란 함수 안에서 함수 자기 자신을 호출하는 방식이고, 일반적인 상황에서는 잘 사용하지 않지만 알고리즘을 구현할 때 매우 유용하게 사용된다. 재귀 함수가 운영될 때 스텍이라는 자료구조가 주로 이용되며, 스텍에 대한 설명은 이전 TIL no.6를 참조하면 될 것 같다.

재귀함수를 이용한 이진수 출력

def DFS(x):
    if x==0:
        return
    else:
        print(x%2, end='')
        DFS(x//2)

n=11
DFS(n)

#1101

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

1. 트리

기본 단위는 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드이며 이러한 기본 단위가 모여 트리를 이룬다. 이런 하 트리를 탐색하는 것을 DFS 혹은 BFS라 한다.

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

DFS는 쉽게 생각해 최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동하여 탐색하는 방식이다. 이 탐색은 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리지만 너비 우선 탐색(BFS)보다 좀 더 간단하다.

3. 간단한 예제

def DFS(v):
    if v>7:
        return
    else:
        DFS(v*2)  #왼쪽 자식 노드
        DFS(v*2+1)  #오른쪽 자식 노드

DFS(1)