자료구조 트리탐색 - 전위탐색(Preorder) 그림으로 쉽게 이해하기
안녕하세요.
로스윗의 코딩캠프입니다.
오늘은 많은 사람들이 궁금해하시고 헷갈려하시는 내용을 바탕으로
자료구조 트리탐색 - 전위탐색(Preorder) 그림으로 쉽게 이해하기에 대해서 같이 알아보겠습니다.
그림으로 쉽게 이해할 수 있으니 끝까지 잘 따라와주세요 :)
바로 시작하겠습니다.
- 트리순회
--> 트리순회란 트리 구조에서 각 노드를 한 번씩 방문하는 과정을 말합니다.
이번 포스팅에서는 트리를 탐색할 때 어떤 방식으로 탐색하는지 알아 볼 것입니다.
트리를 탐색하는 방법에는 크게 3가지가 있습니다.
- 트리탐색의 3가지 방법
1) 첫번째는 전위탐색이라 하는 preorder
2) 두번째는 중위탐색이라 하는 inorder
3) 세번째는 후위탐색이라 하는 postorder
전위탐색, 중위탐색, 후위탐색은 노드 방문을 언제하느냐로 구분을 할 수 있습니다.
- 전위탐색 preorder 노드 방문 순서
첫번째 전위탐색인 preorder는 루트 노드 방문이 가장 먼저 이뤄집니다.
그리고 왼쪽 서브트리를 preorder하고 그 다음에 오른쪽 서브트리를 preorder합니다.
여기서 서브트리를 preorder한다는 말은 재귀호출로 탐색이 이뤄지는 것을 의미합니다.
트리의 특성에서 언급했던 것처럼 트리의 하위 노드는 서브트리를 구성하는 재귀적 형태이기 때문에
재귀호출로 탐색이 가능합니다.
- 중위탐색 inorder 노드 방문 순서
두번째로 중위탐색인 inorder방식입니다.
중위탐색은 루트노드 방문을 중간에 하게 됩니다.
그래서 제일 처음엔 왼쪽 서브트리를 inorder하게 되고,
그 다음에 루트 노드를 방문한 후 마지막 서브트리를 inorder합니다.
마찬가지로 서브트리를 inorder한다는 것은 재귀적으로 탐색한다는 말입니다.
- 후위탐색 postorder 노드 방문 순서
마지막으로 후위탐색인 postorder방식입니다.
후위탐색은 먼저 서브트리탐색을 다 한 후에 마지막으로 루트 노드를 방문하는 방식입니다.
그래서 제일 먼저 왼쪽 서브트리를 postorder하고 그 다음에 오른쪽 서브트리를 postorder한 후
마지막으로 루트 노드를 방문함으로써 postorder를 마무리하게 됩니다.
그러면 위 그림처럼 루트 노드가 A인 이진트리에서
전위탐색, 중위탐색, 후위탐색을 각각 했을 때 어떤 형태로 트리의 탐색이 이뤄지고,
또 노드 방문 순서가 어떻게 달라지는지 알아볼까요?
- 전위탐색
전위 탐색부터 알아보겠습니다.
먼저 전위탐색은 방문 순서가 루트 - 왼쪽 - 오른쪽입니다.
이 트리에서 루트노드인 A를 가장 먼저방문하게 될 것입니다.
그 다음에 A노드를 기준으로 왼쪽 서브트리를 방문하게 됩니다.
그러면 A의 왼쪽 서브트리인 B로 가게 됩니다.
그 다음으로 B의 기준으로 왼쪽 서브트리인 D를 방문하게 됩니다.
그래서 여기까지 A - B - D의 순서로 방문을 했습니다.
그런데 이제 D노드는 왼쪽 서브트리가 없기 때문에 바로 오른쪽 서브트리인 H노드를 preorder하게 됩니다.
그리고 H노드는 왼쪽도 오른쪽도 없기때문에 이것으로 preorder과정을 마무리하게 됩니다.
그러면 D노드를 기준으로 preorder가 마무리 되었고
다시 B노드로 올라와서 B노드 기준으로는 왼쪽 서브트리의 preorder과정이 모두 끝나게 된 것입니다.
그러면 이제 B노드의 오른쪽 서브트리를 preorder할 차례죠.
E노드를 방문합니다.
그리고 E노드 또한 H노드와 마찬가지로 왼쪽 오른쪽 서브트리가 없기 때문에 preorder가 종료가 됩니다.
또한 B노드를 기준으로 했을때 왼쪽과 오른쪽 서브트리 모두 preorder가 종료가 되었기 때문에
B노드도 preorder가 끝나게 되겠죠.
그리고 B노드는 A노드의 왼쪽 서브트리였죠?
그래서 루트노드인 A노드를 기준으로 했을때 2번과정인 왼쪽 서브트리를 preorder하는 것이 끝나게 되는 것입니다.
그러면 이제 A노드를 기준으로 오른쪽 서브트리를 preorder하게 되겠죠.
그래서 C노드를 방문하게 되고, 왼쪽 서브트리가 있으니 그 다음으로는 F노드를 방문하게 됩니다.
F노드도 왼쪽 서브트리가 있기 때문에 I노드를 탐색하게 되고,
I노드는 왼쪽 오른쪽 서브트리가 없기 때문에 탐색을 종료합니다.
F노드를 기준으로 왼쪽의 트리탐색은 끝났습니다.
이제 3번 동작인 오른쪽 서브트리를 전위탐색하기 위해서 J노드로 들어갑니다.
그리고 J노드는 왼쪽 오른쪽 서브트리가 없으니 preorder를 종료합니다.
이렇게 되면 F노드를 기준으로 왼쪽과 오른쪽 서브트리가 모두 방문이 끝나게 되서
F노드도 모두 전위탐색이 끝나게 되었습니다.
그리고 이 F노드는 C노드의 왼쪽 서브 트리였기 때문에
C노드를 기준으로 했을 때 왼쪽의 서브트리가 모두 탐새되었다고 볼 수 있습니다.
그러면 이번엔 C노드를 기준으로 오른쪽 서브트리를 preorder할 차례죠.
그래서 G노드를 방문할 차례고, G노드는 왼쪽 서브트리가 없기 때문에 바로 오른쪽 서브트리인 K노드를 방문합니다.
K노드는 왼쪽 오른쪽 서브트리가 모두 없기때문에 여기서 preorder를 종료하게 되고,
K노드가 종료 됨으로써 G노드의 오른쪽 서브트리 탐색이 종료가 되었고,
G노드가 종료 됨으로써 C노드의 오른쪽 서브트리 탐색이 종료가 되었습니다.
그러면 마지막으로 루트인 A노드로 돌아와 A노드를 기준으로 왼쪽 오른쪽 서브트리를 모두 방문했기 때문에
preorder를 완전히 종료하게 됩니다.
이렇게 위 트리의 전위탐색 방문 순서는 A - B - D - H - E - C - F - I - J - G - K 인 것을 알 수 있습니다.
이렇게 해서 모든 노드들에 대해서 방문이 완료되었고, preorder도 종료가 되었습니다.
이제 다음 포스팅에서는 같은 트리에 대해 전위탐색과 비교하여 중위탐색과 후위탐색은
어떤 순서로 노드 방문이 이뤄지는지 같이 알아보도록 하겠습니다.
감사합니다.
'컴퓨터 공학 > 자료구조와 알고리즘' 카테고리의 다른 글
| 자료구조 트리탐색 - 후위탐색(Postorder) 그림으로 쉽게 이해하기 (0) | 2022.12.19 |
|---|---|
| 자료구조 트리탐색 - 중위탐색(inorder) 그림으로 쉽게 이해하기 (0) | 2022.12.18 |
| 자료구조 이진트리(Binary Tree) 그림으로 쉽게 이해하기 (3) | 2022.11.24 |
| 자료구조 트리(Tree) 그림으로 쉽게 이해하기 (0) | 2022.11.21 |
| 알고리즘 퀵정렬(Quick sort) 그림으로 쉽게 이해하기 (0) | 2022.11.16 |
