반응형
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와 비교하면서 순서를 따져보면 쉽게 이해할 수 있을 것이다.
반응형
'Computer Science > 자료구조' 카테고리의 다른 글
Preorder, Inorder, Postorder 방식으로 출력하기 (0) | 2012.08.30 |
---|---|
Linked List를 이용한 다항식 덧셈연산 (Polynomial Add) (0) | 2012.08.03 |
Linked List (링크드 리스트) 이해 및 기본적인 생성 (0) | 2012.08.03 |
Infix to Postfix - 중위표기식을 후위표기식으로 변환 (0) | 2012.07.31 |
Postfix Evaluation, 후위표기식 연산 (0) | 2012.07.31 |