이진트리 레벨탐색
이진트리 탐색이란, Tree의 형태를 가진 자료구조에서 탐색을 수행하는 것을 의미하며 방법에 따라 BFS(Breadth-First Search) DFS(Depth-First Search)가 존재한다.
그 중에서도 레벨 탐색은 BFS에 해당하는 탐색 방법이다.
위 그림에 대해, 레벨탐색을 수행하는 경우
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7의 순서로 탐색을 진행한다.
레벨 탐색이란 말 그대로, 각 트리의 레벨에 따라 순서대로 탐색하는 것을 의미한다.
위 그래프에서는 다음과 같다.
Level 0 --> 1
Level 1 --> 2 3
Level 2 --> 4 5 6 7
코드로 이를 나타내면 아래와 같다.
from collections import deque
def BFS():
Q = deque() # deque 자료형 선언
Q.append(1) # 초기 노드 (root) 할당
L = 0 # 레벨 선언
while Q: # queue에 값이 존재하는 경우에만
n = len(Q)
print(L, end = " : ")
for i in range(n):
v = Q.popleft()
print(v, end = " ")
for nv in [v*2, v*2+1]: # 자식 노드 탐색
if nv > 7:
continue
Q.append(nv)
print()
L += 1
-----------
BFS()
1 2 3 4 5 6 7 8재귀 함수
재귀 함수란 자기 자신을 호출하는 함수를 의미한다.
코드로서 보면 다음과 같다.
def DFS(n):
if n == 0:
return
else:
print(n, end=' ')
DFS(n-1) # <-- 재귀 함수 호출 부분
-----
DFS(5)
5 4 3 2 1이러한 재귀함수는, 코드 내에서 위치하는 라인에 따라 다른 결과를 불러온다.
def DFS(n):
if n == 0:
return
else:
DFS(n-1) # <-- 재귀 함수 호출 부분
print(n, end=' ')
-----
DFS(5)
1 2 3 4 5이러한 이유는, 재귀함수가 스택을 사용해서 동작하기 때문에 print()문을 수행하기 전에 재귀를 호출한경우, 해당 함수가 종료되기 전까지 print문을 수행하지 않고 sleep상태로 전환되기 때문이다.
예를 들어 print()문의 위에서 수행한 경우
DFS(1) ... 1
DFS(2) ... DFS(1) 끝나기를 기다리는 중..
DFS(3) ... DFS(2) 끝나기를 가디리는 중..
DFS(4) ... DFS(3) 끝나기를 기다리는 중..
DFS(5) ... DFS(4) 끝나기를 기다리는 중..위와 같이 스택의 형태로 재귀함수가 쌓인다.
이진트리 깊이우선탐색
이진트리 깊이우선탐색은 DFS라고 불리는 탐색방법이며, 레벨탐색과 다르게 가장 깊은 레벨까지 들어간 뒤, 더 이상 내려갈 곳이 없으면 다시 올라오는 방식을 취한다.
위의 트리를 탐색하는 경우
1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7
위의 경로로 탐색을 수행한다.
깊이 우선 탐색은 부모 노드를 언제 탐색하는 지에 따라 3가지의 탐색 방법이 존재한다.
대중적으로 사용하는 전위 순회, 부모를 중간에 탐색하는 중위 순회, 마지막에 탐색하는 후위 순회가 있다.
전위 순회 : 1 - 2 - 4 - 5 - 3 - 6 - 7
중위 순회 : 4 - 2 - 5 - 1 - 6 - 3 - 7
후위 순회 : 4 - 5 - 2 -6 - 7 - 3 - 1
이를 코드로 구현하면 다음과 같다.
def DFS(v):
if v > 7:
return
else:
print(v, end= '')
DFS(v*2)
DFS(v*2+1)
-----
DFS(1)
