참고 자료는 다음과 같습니다.
- 파이썬 자료구조와 알고리즘 (한빛미디어, 2019)
트리 순회
○ 순회 : 트리, 그래프 같은 연결된 구조에서 노드에 접근할 때 사용되는 알고리즘
● 모든 노드에 접근하는 방법 또는 특정 노드만 접근하는 방법을 찾는 것임
깊이 우선 탐색
○ 깊이 우선 탐색 : 그래프 또는 트리에서 깊이를 우선하여 탐색하는 알고리즘
○ 시간 복잡도 : O(도달할 수 있는 노드 수 + 도달한 노드에서 나가는 간서너 수)
○ 후입선출 구조의 스택 사용해 구현함
전위 순회
○ 루트 노드 -> 왼쪽 노드 -> 오른쪽 노드 순으로 접근
ex)
* 노드 위의 숫자가 접근 순서임
후위 순회
○ 왼쪽 노드 - 오른쪽 노드 -> 루트 노드 순으로 접근
중위 순회
○ 왼쪽 노드 -> 루트 노드 -> 오른쪽 노드 순으로 접근
너비 우선 탐색
○ 트리, 그래프에서 너비를 우선하여 탐색하는 알고리즘
○ 시작 노드에서 특정 노드에 도달하는 데 필요한 최단 경로 찾는 문제에 활용
○ 접근한 노드를 저장하는 데 리스트 사용하며, 아직 접근 안한 노드는 선입선출 구조의 큐로 저장
○ 시간 복잡도 : O(도달할 수 있는 노드 수 + 도달한 노드에서 나가는 간서너 수)
