[자료구조] 트리 순회(Tree traversal) , BFS와 DFS

트리 순회 :

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것

 

모든 노드를 순회하는 방법에는 크게 세 가지가 있다!

루트 노드를 방문하는 순서에 따라 나뉨.

 

전위 순회 (preorder traverse) / 중위 순회 (inorder traverse) / 후위 순회 (postorder traverse)

 

*트리구조 노드 순차 조회 시 항상 왼쪽 -> 오른쪽 순서이다. 

Search	순서
pre-	ROOT	left	right
in-	left	ROOT	right
post-	left	right	ROOT

 

 

전위 순회

 

 

중위 순회

 

 

후위 순회

 

 

---

BFS와 DFS

 

그래프의 탐색 시 : 모든 정점들을 한 번씩 방문(탐색) 하는 것이 목적

 

배열 처럼 정렬이 되어 있지 않기 때문에, 하나씩 모두 방문하여 찾아야 함

BFS와 DFS는 데이터 탐색 순서가 다르다! -

각각의 장단점이 분명함

 

너비 우선 탐색 

(BFS : Breadth-First Search)

 

탐색 방식 : 자신과 연결된 주변 정점부터 탐색해 나감

특징 : 깊이가 깊은 그래프에 대해 높은 성능

제약 조건 : 너비가 넓은 그래프에 대해 낮은 성능

                  (너비 위주로 탐색하므로 너무 넓은 그래프면 시간 오래걸림..)

이용 자료 구조 : 큐(Queue)

 

 

 

깊이 우선 탐색

(DFS : Depth-First Search)

 

탐색 방식 : 자신과 연결된 정점을 선택,

그 정점에서 연결된 모든 정점을 파고들어가며 끝날때까지 들어가 탐색

 

특징 : 넓이가 넓은 그래프에 대해 높은 성능

제약 조건 : 깊이가 깊은 그래프에 대해 낮은 성능

                  (깊이가 깊을 수록 탐색에 시간이 오래 걸려서)

이용 자료 구조 : 스택(Stack)

 

 

 

gif 출처 : https://dev.to/jenshaw/binary-trees-discussing-in-depth-first-traversals-4a8n