시작하며
오늘은 어제 배운 자료구조를 이어서 트리 순회의 종류와 실제 구현하는 방법을 실습하며 자료구조에 대해 더 깊게 이해할 수 있도록 학습하였다.
자료구조
Tree traversal(트리 순회)
특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 하며 모든 노드를 순회하는 방법엔 크게 세 가지가 있다.
-
전위 순회 : 가장 먼저 루트노드를 방문하고 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색을 한다.
-
중위 순회 : 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색한다.
-
후위 순회 : 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문한다.
BFS / DFS
DFS(Depth-First Search)
깊이를 우선적으로 탐색하는 방법으로, 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색한 후 다음 노드를 탐색한다.
하나의 경로를 끝까지 들어가서 확인하고 다음으로 넘어가기 때문에, 운이 좋다면 단 몇 번만에 경로를 찾을 수 있으며 BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색할 수 있다.
BFS(Breadth-First Search)
가까운 정점부터 탐색하는 방식으로 같은 레벨의 정점을 모두 탐색한 이후의 다음 레벨의 정점들을 탐색하는 방식이다. 주로 두 정점 사이의 최단 경로를 찾을 때 사용하며, 만약 경로를 하나씩 전부 방문한다면 최악의 경우에는 모든 경로를 다 살펴보아야 한다.
마치며
순회 방법을 이해하는 것은 어렵지 않았으나 자료구조를 javaScript로 구현하는 것과 같이 실제 코드로 작성하는 것이 쉽지 않았다. 재귀함수를 사용해야 한다는 것은 파악했지만 어떤 식으로 구조를 짜야하고 호출 종료 조건을 어떤 변수로 정해야 하는지가 어려웠다. 구글링을 통해 관련된 코드들이 어떠한 형식으로 짜여져 있는지 찾아보면서 확실하게 이해할 수 있었다.
