[트리순회] 전위탐색(preorder)

트리순회(트리탐색)이란?

트리순회란 트리를 탐색하는 방법인데, 트리구조에서 각 노드를 한번씩 방문하는 과정을 말한다.

트리순회에는 3가지 방법이 있다

1) 전위탐색 (preorder)
2) 중위탐색 (inorder)
3) 후위탐색 (postorder)

이는 노드방문을 언제하는지를 기준으로 구분할 수 있다.

 

 

 

이번에는 전위탐색을 먼저 살펴볼것이다!!

전위탐색(preorder) 순서

1. 루트 노드 방문 
2. 왼쪽 서브트리를 preorder
3. 오른쪽 서브트리를 preorder

 

전위탐색(preorder)은 루트노드 방문이 제일먼저 이뤄지고

그 다음 왼쪽 서브트리를 preorder하고, 그 후에 오른쪽 서브트리를 preorder하는 방식으로 이뤄진다.

서브트리를 preorder한다는것은 재귀호출로 탐색이 이뤄지는 것을 의미한다.

 

 

 

예시를 통해서 전위탐색 순서를 알아보자!

 

방문순서가 루트노드 -> 왼쪽 -> 오른쪽 이므로

아래 트리에서 루트노드인 A를 제일먼저 방문할것이다.

그리고 A의 왼쪽 서브트리인 B로 가고, B를 기준으로 왼쪽 서브트리인 D를 방문하게 될것이다.

그런데 이제 D노드는 왼쪽 서브트리가 없기때문에 바로 오른쪽 서브트리인 H노드를 preorder하게 된다.

그리고 H를 보면 H는 왼쪽,오른쪽 자식노드가 없기때문에 preorder를 마무리하게 된다.

 

 

 

 

 

이렇게 지금까지 A-B-D-H의 순서로 방문했고,

D노드를 기준으로는 preorder가 마무리되었으니깐, 다시 B노드로 올라오면 B노드 기준으로는 왼쪽 서브트리의 preorder는 다 끝나게 된것이다. 그럼 이제 B노드의 오른쪽 서브트리를 방문해야되니깐 E노드를 방문해야한다.

E노드 또한 왼쪽,오른쪽 서브트리가 없기때문에 preorder가 종료되게된다

 

 

여태까지 A-B-D-H-E의 순서로 방문했고,

B노드를 기준으로 했을때 왼쪽과 오른쪽 서브트리 모두 preorder가 종료되었기 때문에 B노드도 끝나게되는것이다

전체를 봤을때 A의 왼쪽 서브트리 preorder과정이 끝나는것이다.

 

 

 

 

 

이제 A노드를 기준으로 오른쪽 서브트리를 preorder하게 될것이다

그래서 C노드 방문 -> F노드 -> I노드 순으로 먼저 방문하게되고, I노드는 왼쪽,오른쪽 서브트리가 없기때문에 탐색을 종료하게된다.

 

 

 

 

이제 F노드를 기준으로 왼쪽의 트리탐색은 끝났다.

이제 오른쪽 서브트리를 탐색해야되므로 J노드를 탐색한다.

J노드 역시 자식노드가 아무것도 없으니 preorder를 종료한다.

여기까지하면 C노드의 왼쪽 서브트리의 탐색이 종료되는것이다.

 

 

 

이젠 C노드를 기준으로 오른쪽 서브트리를 preorder해야한다

그래서 G노드 방문하고, G노드는 왼쪽 서브트리가 없기때문에 바로 오른쪽 서브트리인 K를 방문한다.

K노드도 자식노드가 없기떄문에 preorder를 종료하게되고,

K노드가 종료되면서 C노드의 오른쪽 서브트리 탐색이 종료되었고,

A노드를 기준으로보면 왼쪽,오른쪽 서브트리를 모두 방문했기때문에 트리 전체의 preorder를 완전히 종료하게된다.

 

 

 

이렇게 최종적으로 모든 노드에대해서 방문이 완료되었고, preorder도 종료되었다.

최종적으로 전위탐색 방문순서는 A - B - D - H - E - C - F - I - J - G - K가 될것이다.