728x90
문제 제목: 이진 트리 순회(깊이 우선 탐색)
개념
- 전위 순회 방식: 함수 출력시 부모 -> 왼쪽 자식 -> 오른쪽 자식 순서로 출력
- 중위 순회 방식: 함수 출력시 왼쪽 자식 -> 부모 -> 오른쪽 자식 순서로 출력
- 후위 순회 방식: 함수 출력시 왼쪽 자식 -> 오른쪽 자식 - >부모 순서로 출력
1. 전위 순회 방식
함수 출력시 부모 -> 왼쪽 자식 -> 오른쪽 자식 순서로 출력
def DFS(v):
if v>7:
return
else:
print(v, end=' ')
DFS(v*2)
DFS(v*2+1)
if __name__=="__main__":
DFS(1)
2. 중위 순회 방식
함수 출력시 왼쪽 자식 -> 부모 -> 오른쪽 자식 순서로 출력
def DFS(v):
if v>7:
return
else:
DFS(v*2)
print(v, end=' ')
DFS(v*2+1)
if __name__=="__main__":
DFS(1)
3. 후위 순회 방식
함수 출력시 왼쪽 자식 -> 오른쪽 자식 - >부모 순서로 출력
def DFS(v):
if v>7:
return
else:
DFS(v*2)
DFS(v*2+1)
print(v, end=' ')
if __name__=="__main__":
DFS(1)
대표적으로 병합정렬이 있음
왼쪽 자식 처리 후 오른쪽 자식 처리 후 부모(본인) 처리
이제 더이상 더 갈 수가 없으니 DFS(4)는 pop되어 반환됨 그리고나서 D(5) 순회
※ 알아야 할 것
- 재귀함수는 모두 DFS라고 칭함.
- 링크 게시글을 모두 이해했으면 쉽게 이 글도 이해할 수 있을 것임
https://sillon-coding.tistory.com/211
728x90
'coding test - python > 기본기 문제' 카테고리의 다른 글
문제 / 합이 같은 부분집합(DFS) / Python 파이썬 (0) | 2022.08.05 |
---|---|
문제 / 부분집합 구하기 (DFS) / Python 파이썬 (0) | 2022.08.03 |
문제 / 재귀 함수를 이용한 이진수 출력 / Python 파이썬 (0) | 2022.08.03 |
문제 / 회의실 배정 (그리디) / Python 파이썬 (0) | 2022.08.02 |
문제 / 최대힙 / Python 파이썬 (0) | 2022.07.29 |