이진 탐색 트리에서 전체 방문하는 방법은?(Pre-Order, In-Order, Post-Order, Reverse In-Order)

Q. 이진 탐색 트리에서 전체 방문하는 방법은?

 

CS 지식을 묻는 시험에서 자주 나오는 문제이다, 재귀적인 구조를 이해한다면 쉽게 답을 유추할 수 있다.

 

각 Order의 주체가 되는 것은 루트 노드라는 것을 잊지 않으면 된다.

 

Pre-Order은 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순으로 방문한다.

 

In-Order은 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순으로 방문한다.

 

Post-Order은 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 순으로 방문한다.

 

각 노드의 방문 순서를 출력할 수 있는데, 루트 노드의 위치에 printf를 호출해주면 된다.

 

 

Q. 부모 노드를 출력하는 것이 모든 노드의 순서를 볼 수 있을까?

 

어떤 노드든 루트 노드가 될 수 있다. (물론 모든 트리에서 루트 노드는 하나이다.) 

 

왼쪽 서브트리와 오른쪽 서브트리에 대해서도 동일한 구조로 진행될 것이기 때문에, 모두 방문될 수 있다.

 

이게 바로 재귀함수의 매력이다.

 

재귀함수가 정확히 이해되지 않는다면, 피보나치를 떠올려보자. 구조는 같다, 다만 호출하는 함수의 개수가 다를뿐.

 

 

Q. 가장 큰 노드부터 가장 작은 노드까지 차례대로 방문하는 방법은?

 

Reverse InOrder를 이용하면 된다. 이진 탐색 트리에서 루트노드보다 오른쪽 트리는 무조건 크다, 왼쪽 트리는 무조건 작다. 이 성질을 이용해서, Reverse InOrder를 만들면 된다.