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