Binary Tree Traversal - Inorder, Preorder, Postorder, Levelorder

Binary Tree Traversal, 즉 2진트리 탐색에 대해 알아보자.

정보처리기사 시험문제에도 나오는 이론이기 때문에 중요할듯 싶다 ㅋ

이진트리탐색에서 항상 나오는 3가지 방법, Inorder Traversal, Preorder Traversal, Postorder Traversal이 있고,

한가지 더 추가적으로 보자면 Levelorder Traversal을 이야기 할 수 있을 것이다

이들의 방법은 각각 이렇다.

먼저 그림을 보고 이해하자면

다음과 같은 Binary Tree, 즉 2진트리가 있을 때

Inorder는 Left child -> Root -> Right child 순으로,

Preorder는 Root -> Left child -> Right child 순으로,

Postorder는 Left child -> Right child -> Root 순으로 탐색을 하는 방식이다.

각각 Root를 기준으로 Root가 언제 탐색되는지에 따라서 기억 하면 쉬울 것 같다.

그리고 Level Order방식은 트리의 레벨에 따라서 차례대로 탐색하면 된다.

각각의 방식으로 탐색을 하게 되면 결과는 다음과 같을 것이다.

Tree와 비교하면서 순서를 따져보면 쉽게 이해할 수 있을 것이다.