자료구조 트리탐색 - 후위탐색(Postorder) 그림으로 쉽게 이해하기
안녕하세요.
로스윗의 코딩캠프입니다.
오늘은 많은 사람들이 궁금해하시고 헷갈려하시는 내용을 바탕으로
자료구조 트리탐색 - 후위탐색(Postorder) 그림으로 쉽게 이해하기에 대해서 같이 알아보겠습니다.
그림으로 쉽게 이해할 수 있으니 끝까지 잘 따라와주세요 :)
바로 시작하겠습니다.
- 후위탐색 Postorder
이번 시간에는 트리탐색의 방법 중 하나인 후위탐색(Postorder)에 대해서 알아보겠습니다.
후위탐색은 먼저 1)왼쪽 서브트리를 inorder하게 되고, 그 다음으로 2)오른쪽 서브트리를 방문한 다음에
마지막으로 3)루트 노드를 후위탐색(Postorder)하게 됩니다.
아래의 트리를 한 번 후위탐색 해보도록 하겠습니다.
- 항상 시작은 루트노드부터!
탐색 방식과 상관없이 시작은 항상 루트노드부터 시작하게 됩니다.
그래서 A노드부터 시작을 하게 되고, A노드의 왼쪽 서브트리인 B노드로 먼저 이동하게 됩니다.
B노드도 자식을 가지고 있기 때문에 여기서도 또 한 번 왼쪽 서브트리인 D로 이동하게 됩니다.
D노드는 더 이상 이동할 왼쪽 서브트리가 없기 때문에 바로 오른쪽 서브트리로 이동하게 됩니다.
그러면 H노드로 이동한 상태가 되고, H노드는 왼쪽 노드도 오른쪽 노드도 없기 때문에 루트노드인 자신을 방문하게 됩니다.
그래서 후위탐색에서는 H노드를 가장 먼저 방문하게 됩니다.
H노드를 방문하면서 D노드를 루트로하는 서브트리는 오른쪽 서브트리에 대한 후위탐색을 마치게 되었습니다.
그래서 서브트리의 루트인 D노드를 방문하면서 D노드가 두 번째 방문노드가 되었고,
D노드를 루트로하는 서브트리의 탐색도 종료가 되었습니다.
이제 B노드를 기준으로 왼쪽 서브트리의 탐색이 끝나게 되었으므로 오른쪽 서브트리를 방문하게 됩니다.
그래서 E노드로 이동하고, E노드는 왼쪽 오른쪽 서브트리를 모두 가지고 있지 않기 때문에 루트노드인 자신을 방문합니다.
그래서 현재까지 H - D - E 순서로 방문을 했습니다.
E노드가 탐색이 종료 되면서 이제 B노드를 기준으로 오른쪽 서브트리의 탐색이 종료 된 것을 알 수 있습니다.
그래서 이제 루트노드인 B노드를 방문하게 됩니다. 그래서 현재까지 H - D - E - B 순서로 방문을 했습니다.
B노드를 방문함으로써 A노드를 루트로하는 전체 트리에서 왼쪽 서브트리에 대한 탐색이 종료가 됩니다.
이제 A노드의 오른쪽 서브트리로 이동해서 후위탐색을 진행할 차례입니다.
그러면 먼저 C노드로 이동을 하게 되고, C노드는 왼쪽 자식이 있기 때문에 다시 F노드로 이동하게 되고,
F노드도 왼쪽 자식이 있기 때문에 I노드로 이동합니다.
그리고 I노드는 아무 자식노드가 없기 때문에 후위탐색의 1,2번 과정을 거넌뛰고
자기자신인 I노드르 방문하면서 현재까지 H - D - E - B - I 순서로 방문하게 되었습니다.
그러면 이제 F노드를 기준으로 왼쪽 서브트리에 대한 탐색이 끝났기 때문에 F노드의 오른쪽 자식인 J노드로 이동을 합니다.
J노드는 I노드와 마찬가지로 자식이 없는 리프노드이기 때문에 바로 자기자신을 방문을 하고 탐색을 종료합니다.
그래서 현재까지 H - D - E - B - I - J 의 순서로 방문했습니다.
J노드의 방문으로 F노드의 오른쪽 서브트리 후위탐색이 종료가 되었습니다.
고로 그 다음으로 자기자신인 F노드를 방문하게 됩니다.
그래서 현재까지 H - D - E - B - I - J - F 의 순서로 방문했습니다.
그리고 F노드의 탐색이 끝났으므로 C를 루트로 하는 서브트리의 오른쪽 노드를 방문할 차례겠지요.
그래서 G노드로 이동했는데 G노드는 왼쪽 자식 노드가 없기 때문에 바로 오른쪽 자식노드인 K노드로 이동을 합니다.
K노드는 리프노드이기 때문에 바로 자기자신을 방문하게 됩니다.
그래서 현재까지 H - D - E - B - I - J - F - K 의 순서로 방문했습니다.
K노드가 탐색이 종료 됨으로써 G노드를 기준으로 오른쪽 서브트리에 대한 탐색이 종료 되었습니다.
고로 자기자신인 G노드를 방문하게 되고, G노드를 방문하게 됨으로써 C노드를 기준으로 오른쪽 서브트리도 탐색이 종료되게 되었습니다. 그래서 루트노드인 자기자신 C노드도 방문을 하게 되고, C노드를 방문함으로써 A노드에 대한 오른쪽 서브트리 탐색이 종료되었기 때문에 마지막으로 자기자신인 A노드를 방문하게 되면서 전체 후위탐색을 종료하게 됩니다.
그래서 최종적으로는 H - D - E - B - I - J - F - K - G - C - A의 순서로 후위탐색을 하게 됩니다.
후위탐색에서 전체트리의 루트노드인 A노드는 가장 마지막에 방문하게 되었습니다.
- 트리탐색 노드 방문순서 비교
그래서 결과적으로 각각 전위탐색, 중위탐색, 후위탐색의 노드방문 순서를 비교해보면 다음과 같습니다.
전위탐색에서는 루트노드를 가장 먼저 방문한 것을 알 수 있고,
중위탐색에서는 루트노드를 중간에 방문 한것을 알 수 있고,
후위탐색에서는 루트노드를 가장 마지막에 방문한 것을 알 수 있습니다.
후위탐색에 대한 포스팅은 여기서 마치도록 하겠습니다.
다음 포스팅도 기대해주세요.
감사합니다.
'컴퓨터 공학 > 자료구조와 알고리즘' 카테고리의 다른 글
| 자료구조 - 힙(Heap) 그림으로 쉽게 이해하기 (0) | 2022.12.25 |
|---|---|
| 자료구조 - 이진탐색트리(BST) 그림으로 쉽게 이해하기 (0) | 2022.12.21 |
| 자료구조 트리탐색 - 중위탐색(inorder) 그림으로 쉽게 이해하기 (0) | 2022.12.18 |
| 자료구조 트리탐색 - 전위탐색(Preorder) 그림으로 쉽게 이해하기 (0) | 2022.12.09 |
| 자료구조 이진트리(Binary Tree) 그림으로 쉽게 이해하기 (3) | 2022.11.24 |
