[트리] 이진 트리 순회 6/24

~프로로그~
Microsoft Visual C++ 2010 Express, 즉, 체험판을 열심이 쓰고 있었는데.... 만료 됬다.
다시 다운 받아서 해야된다... ㅠ_ㅠ 귀차니즘에 구현은 둘째치고 트리의 순회에 대해서 알아보도록하자~
-----------------------------------------------------------------------------------------------------
*트리의 순회란?
 - 트리의 모든 노드를 한 번씩 방문 하는 것

*특징
 - 이진트리의 최대 차수가 2이기 때문에 현재 방문중인 V(Visit)노드
   왼쪽자식노드 L(Left node), 오른쪽자식노드 R(Right)로 나눠 일반화 하여 생각할수 있다.

*트리의 순회 종류
 ⓐ 전위 순회
  - 순회 순서 : V - L - R
  - 현재 노드를 방문 / 왼쪽 서브트리 방문 / 오른쪽 서브트리 방문
 
 ⓑ 중위 순회
  - 순회 순서 : L - V - R
  - 왼쪽 서브트리 방문 / 현재 노드를 방문 / 오른쪽 서브트리 방문

 ⓒ 후위 순회
  - 순회 순서 : L - R - V
  - 왼쪽 서브트리 방문 / 오른쪽 서브트리 방문 / 현재 노드를 방문

 ⓓ 레벨 순회
  - 순회 순서 : level 1부터 상위 레벨로 향하며, 같은 레벨에서는 왼쪽에서 오른쪽 방향으로 탐색

 ex)
 

전위 순회 : V - L - R
 : 1(루트) - 2(루트의 L) - 4(2의 L) - 5(2의 R) - 3(루트의 R) - 6(3의 L) - 7(3의 R)
중위 순회 : L - V - R
 : 4 - 2 - 5 - 1 - 6 - 3- 7
후위 순회 : L - R - V
 : 4 - 5 - 2 - 6 - 7 - 3 - 1
※전위/후위/중위 순회를 할시 이동을 하면 그 노드를 기준으로 다시 순회를 한다고 생각하자!!
레벨 순회 
 : 1 - 2 - 3 - 4 - 5 - 6 - 7

*이진 트리 순회의 구현
 ⓐ 재귀호출에 의한 구현 
  위에서 말했듯이(※전위/후위/중위 순회를 할시 이동을 하면 그 노드를 기준으로 다시 순회를 한다고 생각)
  이동과 동시에 반복적인 행동이 계속된다. 이는 재귀호출을 이용하여 구현할 수 있음을 시사한다.
  예를 들어 전위 순회를 의사코드로 정리하면
  
  void move(노드){
    printf("%d",V노드);  // 현재 노드를 출력한다.
    move(L노드);  // 왼쪽 노드를 간다.
    move(R노드);  // 오른쪽 노드를 간다.
  }
  각 순회에 따른 의사크도는 현재노드를 출력하는 위치의 변화에 따라서 달라지게 된다.
  어디로 이동을 먼저하고, 언제 출력하는지의 문제라는 것이다.
  각 알고리즘을 생각하며 의사코드를 따라서 트리 순회를 해보면 답이 보일 것이다.
  재귀 호출에 따른 basecase는 읽는 사람의 몫으로 남기도록 하겠다~

 ⓑ 반복에 의한 구현
  위에서 소개한 재귀호출에 의한 구현으로는 레벨 순회를 표현 할 수가 없다.
  반복호출 함수를 이용하여 구현하는 이 방법은 스택(전위/중위순회)과 큐(레벨순회)를 응용하며,
  반복작업으로 인해 중복방문을 방지하기위해 각 노드에 개발자 임의의 변수를 추가하여 경우를 나누도록한다.
  단,이 경우는 후위 순회의 구현이 어렵다.
 
----------------------------------------------------------------------------------------------------
~에필로그~

순회에 대해서 알아보고 그에 대한 구현방안을 제시하며 이번 공부를 마치고,
다음에는 힙과 이진 탐색트리에 대해서 알아보도록 하겠다~