2021년 7월 22일에 작성된 문서 3번 입니다.
자료 구조 배운 내용을 정리했습니다.
Tree traversal
특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것.
1에서 10까지의 정수로 구성된 트리에서 3이라는 숫자를 찾기 위해 모든 노드를 방문하는 경우는 트리 순회의 한 예시입니다. 트리 구조는 계층적 구조라는 특별한 특징을 가지기 때문에, 모든 노드를 순회하는 방법엔 크게 세 가지가 있습니다.
- 트리를 순회할 수 있는 세 가지 방법:
전위 순회
중위 순회
* 후위 순회 - 트리 구조에서 노드를 순차적으로 조회할 때의 순서는 항상 왼쪽부터 오른쪽!
BFS / DFS
그래프의 탐색의 목적 : 모든 정점들을 한 번씩 방문(탐색)
그래프의 데이터는 배열처럼 정렬이 되어 있지 않습니다. 그래서 원하는 자료를 찾으려면, 하나씩 모두 방문하여 찾아야 합니다.
- 그래프의 모든 정점 탐색 방법 :
DFS&BFS
BFS(Breadth-First Search) : 가까운 정점부터 탐색 (너비 우선 탐색)
주로 두 정점 사이의 최단 경로를 찾을 때 사용
DFS(Depth-First Search) : 깊이를 우선적으로 탐색하는 방법
한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용
- 데이터를 탐색하는 순서만 다를 뿐, 모든 자료를 하나씩 확인해 본다는 점은 같다.
Written with StackEdit
