[자료구조] - 트리(Tree)[4] - 트리의 탐색 (순회)

 

 

 

트리의 탐색(순회)

트리를 탐색하는 방법으로는 다음과 같이 4가지 방법이 있습니다.

1. 중위 탐색 (Inorder traversal)
2. 전위 탐색 (Preorder traversal)
3. 후위 탐색 (Postorder traversal)
4. 레벨 순서 탐색 (Level order traversal)

 

이때 전위, 중위, 후위 탐색의 기준은 루트(Root)노드 입니다.

 

 

 

 

 

 

 

 

중위 탐색(Inorder Traversal)

다음과 같은 순서로 탐색합니다.

1. 왼쪽 서브트리를 재귀적으로 중위 탐색하여 모든 노드를 방문합니다.

2. 루트를 방문합니다.  

3. 오른쪽 서브트리를 재귀적으로 중위 탐색하여 모든 노드를 방문합니다.

즉 루트가 탐색 순서의 중간에 위치합니다.

 

 

 

 

 

 

 

 

 

 

 

전위 탐색(Preorder Traversal)

다음과 같은 순서로 탐색합니다.

1. 루트를 방문합니다.  

2. 왼쪽 서브트리를 재귀적으로 중위 탐색하여 모든 노드를 방문합니다.

3. 오른쪽 서브트리를 재귀적으로 중위 탐색하여 모든 노드를 방문합니다.

즉 루트가 맨 처음에 탐색됩니다.

 

 

 

 

 

 

 

 

 

 

 

후위 탐색(Postorder Traversal)

다음과 같은 순서로 탐색합니다.

1. 왼쪽 서브트리를 재귀적으로 중위 탐색하여 모든 노드를 방문합니다.

2. 오른쪽 서브트리를 재귀적으로 중위 탐색하여 모든 노드를 방문합니다.

3. 루트를 방문합니다.  

즉 루트가 맨 마지막에 탐색됩니다.

 

 

 

 

 

 

정리하면 다음과 같습니다.

 

 

 

 

 

위 3가지 탐색은 재귀함수를 사용하거나 Stack 자료구조를 사용하여 쉽게 구현할 수 있습니다.

(재귀함수가 가장 편하고 쉽습니다.)

 

 

 

 

 

 

 

 

 

레벨 순서 탐색 (Level Order Traversal)

트리의 레벨 순으로, 동일한 레벨의 경우 왼쪽부터 탐색하는 방법입니다.

이는 Queue 자료구조를 이용하면 편하게 구현할 수 있으며, 다음과 같은 과정으로 구현합니다.

1. Root 노드를 Queue에 삽입합니다.

2. Queue에서 노드를 하나 꺼냅니다.
3. 꺼낸 노드를 방문 처리 합니다.
4. 꺼낸 노드의 모든 자식들(Children)을 Queue에 삽입합니다.

2~4의 과정을 Queue가 빌 때까지 반복합니다.