[트리순회] 후위탐색(postorder)

저번까지 트리탐색방법 중 하나인 전위탐색과 중위탐색을 살펴봤었다

https://coding-juuwon2.tistory.com/441

[트리순회] 전위탐색

https://coding-juuwon2.tistory.com/442

[트리순회] 중위탐색(inorder)

 

 

 

 

 

이번에는 이번에는 후위탐색을 살펴볼것이다!!

후위탐색(postorder) 순서

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

 

 

 

전위탐색,중위탐색을 했던 트리와 같은 트리로 후위탐색을 진행해볼거다

 

저번 게시글에서도 말했다시피,

탐색방식과 상관없이 항상 시작은 루트노드부터 시작!! 한다!

그래서 A노드부터 시작하고, A노드의 왼쪽 서브트리인 B노드로 이동한다. B노드도 자식을 갖고있기때문에 왼쪽 자식인 D노드로 이동하게된다. D노드는 더이상 이동할 왼쪽 자식이 없기때문에 바로 오른쪽 서브트리인 H노드로 이동하게된다.

H노드는 왼쪽,오른쪽 노드 모두 없기때문에 루트노드인 자기자신을 방문한다.

따라서 후위탐색에서는 H노드를 가장먼저 탐색하게된다.

 

제일 처음 H노드 방문

 

H노드를 방문하면서 D노드를 루트로하는 서브트리는 오른쪽 서브트리에대해 후위탐색을 마치게 되었고,

그래서 이번엔 루트인 D노드를 탐색하게된다.

이렇게 하면 D노드를 루트로하는 서브트리의 탐색이 종료되게된다.

 

 

D노드 방문

 

이제 B노드를 기준으로 왼쪽 서브트리 탐색이 끝났으므로, 오른쪽 서브트리인 E노드를 방문할것이다.

E노드는 왼쪽,오른쪽 서브트리가 모두 없기때문에 루트노드인 자신을 방문하게 된다

 

E노드 방문

 

 

여기까지하면 B노드를 기준으로 오른쪽 서브트리까지의 탐색이 종료된것을 확인할 수 있다

이제 루트노드인 B노드를 방문하게된다

 

 

B노드 방문

 

 

B노드를 방문함으로써

A노드를 루트로하는 전체 트리에서 왼쪽 서브트리에 대한 탐색이 종료되게된다.

이제 A노드를 기준으로 오른쪽 서브트리에 대해 탐색할 차례다

C노드로 이동했더니 왼쪽 자식이 있기때문에 F로 이동하고, F도 또 왼쪽 자식이 있기때문에 I노드로 이동한다.

I노드는 아무 자식노드가 없기때문에 루트노드인 자기자신을 탐색한다.

 

I노드 방문

 

이제 F노드를 기준으로 왼쪽 서브트리에 대한 탐색이 끝났기때문에 F노드의 오른쪽 자신인 J노드로 이동한다.

J노드 역시 자식이 없기때문에 자기자신을 탐색한다

F노드를 기준으로 왼쪽,오른쪽 서브트리 후위참색이 종료되었기때문에 자기자신 루트노드인 F노드를 탐색한다.

 

J,F노드 방문

 

 

이제 F노드까지의 탐색이 끝났으므로, C를 루트로하는 서브트리의 오른쪽 노드를 방문할 차례다

따라서 G노드로 이동했는데, G노드는 왼쪽 자식노드가 없기때문에 오른쪽 자식노드인 K로 바로 이동한다.

K는 자식노드가 없기때문에 자기자신을 탐색한다.

 

K노드 방문

 

 

K노드까지 탐색이 종료되면서, G노드를 기준으로 오른쪽 서브트리에 대한 탐색까지 종료되었다.

이제 루트노드인 G노드를 탐색한다. G노드를 방문하게 됨으로써 C노드를 기준으로 오른쪽 서브트리 탐색 또한 종료되었다.

따라서 루트노드인 자기자신 C노드를 탐색하게되고, A노드를 기준으로 오른쪽 서브트리에 대한 탐색이 종료되었기때문에

마지막으로 루트노드인 자기자신 A노드를 방문하게 되면서 전체 후위탐색이 종료되게 된다!!!

 

G,C,A 노드 방문

 

 

A노드를 기준으로 왼쪽,오른쪽 서브트리를 모두 탐색했으므로, 모든 서브트리에 대한 탐색이 종료되게된다!

따라서 결과적으로 H - D - E - B - I - J - F - K - G - C - A의 순서로 노드탐색이 이루어지는것을 확인할 수 있다.

 

 

 

 

 

트리탐색  순서 비교

최종적으로 전위탐색, 중위탐색, 후위탐색의 노드 방문순서를 비교해보겠다!

 

전위탐색
A - B - D - H - E - C - F - I - J - G - K

 

중위탐색
D - H - B - E - A - I - F - J - C - G - K

 

후위탐색
H - D - E - B - I - J - F - K - G - C - A

 

루트노드인 A를 기준으로 보면

전위탐색에서는 루트노드를 가장 먼저 방문한것을 알 수 있고,

중위탐색에서는 루트노드를 중간에 방문,

후위탐색에서는 루트노드를 마지막에 방문한 것을 확인할 수 있다.

 

루트노드의 방문 위치에 기반하여 탐색이름이 정해진것을 알수있다.