이진트리 순회방법과 알고리즘

<이진트리의 순회(Traversal)>
- 이진트리를 순회하는 방법은 이진트리를 크게 루트 노드, 왼쪽 부트리, 오른쪽 부트리의 세 부분으로 나누고
  이 세 부분을 방문하는 순서는 3의 조합의 개수인 모두 6가지가 된다
1. 루트노드 -> 왼쪽 부트리 -> 오른쪽 부트리(D->L->R) //전순위
2. 루트노드 -> 오른쪽 부트리 -> 왼쪽 부트리(D->R->L) //전순위
3. 왼쪽 부트리 -> 루트노드 -> 오른쪽 부트리(L->D->R)  //중순위
4. 오른쪽 부트리 -> 루트노드 -> 왼쪽 부트리(R->D->L)  //중순위
5. 왼쪽 부트리 -> 오른쪽 부트리 -> 루트노드(L->R->D)  //후순위
6. 오른쪽 부트리 -> 왼쪽 부트리 -> 루트노드(R->L->D)  //후순위
  이 중에서 2,4,6번은 1,3,5번과 중복되므로 제외


<전위 순회(Preorder traversal)>
- 1번 방식
  - 루트 노드를 먼저 방문하고 왼쪽 부트리로 이동하고 왼쪽 부트리가 모두 처리 후 오른쪽의 부트리로 이동하는 순서
  - 루트 노드의 왼쪽 부트리로 이동한 다음에는 왼쪽 부트리의 최상위에 있는 노드가 루트노드가 되어 전위 순회를 반복
  - 전위 순회방식을 재귀함수로 구현
struct bin_node{
  char data;
  struct bin_node *I_child;
  struct bin_node *r_child;
};



<재귀 함수>
fact(int x)
{ 
  if(x==1)
    return(x);
  else
    return(x*fact(x-1);
}
...
- '재귀함수'라고 해서 즉, 함수 이름이 같다고 해서 동일한 함수가 아니다
  즉, 재귀함수가 호출할 때마다 자기가 자기 자신을 호출하는 것이 아니라 완전히 다른 새로운 함수를 만드는 것이다

- 'x'의 매개변수는 서로 다른 매개변수이다. 즉, 설정된 지역변수가 다른 변수이다
- 각 단계별로 과정을 단순화시켜서 논리를 쉽게 만들며, 
  함수를 호출했다가 돌아가는 경로가 그대로 간직될 수 있기 때문에 트리구조의 경우 모든 경로를 자동으로 간직할 수 있다(회귀성의 특징)

- 재귀함수는 자신과 동일한 함수를 반복해서 호출하며 반드시 호출이 종료되는 조건이 함수 안에 포함되어 있어야 한다
- 전위순휘는 가장 낮은 레벨까지 먼저 방문하는 방식이므로 깊이 우선순회(Depth first order traversal)라고도 한다



<재귀 함수와 반복문 비교 - 3! 구하기>
ex1) fact(3) :  =>재귀 함수
  fact(int x) //fact 함수 호출
{
  if(x == 1) //재귀함수의 호출을 끝내는 조건 
    return(x);
  else
    return(x*fact(x-1);  //3*fact(2) -> fact(x), x=2 호출, 자신과 동일한 함수를 호출(3번 반복 -> 3*2*1)
}

----------------------------
ex2) => 반복문
fact(int x)
{int f=1;
  for(; x>1; x--)
    f=f*x;
    return(f);
}


<전위순회를 호출하는 알고리즘>
void main()
{
struct bin_node *root; //root는 포인터 변수이며 주소(구조체 bin_node형의 구조)를 저장하는 공간이다. 포인터 변수 root는 시작주소(루트노드의 주소)값만을 저장한다
...
  preorder(root); //트리안에있는 모든 노드가 root노드에 저장되어 있기 때문에 트리 안에있는 모든 노드에 접근 가능하다
}                     //루트노드의 주소를 최초로 보내준다(루트노드의 주소가 100일 때)

void preorder(struct bin_node *tree) //전달해준 100(루트노드의 주소값)을 포인터변수 tree도 받는다. 
{
  if(tree == null) return;  //재귀함수가 무한히 반복해서 호출하다가 돌아오는 조건이 충족되는 조건문
  else{
    printf("%c", tree->data); //루트노드 방문 -> 루트노드를 인쇄하는 명령문
    preorder(tree->I_child);  //왼쪽 부트리로 -> 왼쪽 서브트리에 대한 재귀함수
    preorder(tree->r_child);  //오른쪽 부트리로 -> 오른쪽 서브트리에 대한 재귀함수
  }
}

----------------------------
<재귀함수 간략 표현> -> A(root node) - B - C 일 때
preorder() -1 
if()
else
  printf(); //root노드의 'A' 출력
  preorder();
  preorder();


preorder() -2
if()
else
  printf(); //root노드의 'B' 출력
  preorder();
  preorder();


preorder() -3
if()
else
  printf(); //root노드의 'C' 출력
  preorder();
  preorder(); 

preorder() -4
if() 
else
  printf(); 
  preorder(); //C노드의 왼쪽노드가 없으므로 Null값이 return된다. 호출한 장소(3번째 호출)로 들어간다
  preorder();


preorder() -3
if()
else
  printf(); 
  preorder();
  preorder(); -> 오른쪽노드에 대해서 호출했는데 Null값이므로 if조건이 충족되고 호출한 장소로 다시 return


preorder() -2
if()
else
  printf(); 
  preorder(); -> 왼쪽에 대해서 호출했는데 Null값이며 if조건이 충족되고 호출한 장소로 다시 return
  preorder(); 


preorder() -1
if()
else
  printf(); 
  preorder();    오른쪽에 대해서 호출했는데 Null값이며 if조건이 충족되고 호출한 장소로 다시 return
  preorder(); ->A의 오른쪽 서브트리도 Null값이기 때문에 이 경우도 if조건이 충족되고 return이 일어나며 자기자신을 호출했던 장소로 돌아간다 -> main함수로 돌아가고 재귀함수 종료 



<중위 순회(Inorder traversal)>
- 3번방식 
  - 왼쪽 부트리를 먼저 방문하고, 루트 노드를 방문하고 오른쪽의 부트리를 방문하는 순서이다
     왼쪽 부트리에 대해서도 동일한 순서를 반복
- 중위 순회방식 알고리즘을 재귀함수로 구현
- 노드의 데이터 필드를 출력하는 명령문의 순서가 중간으로 바뀐것만 제외하고 전위순회 알고리즘과 동일
void inorder(struct bin_node *tree)
{
  if(tree=null) return; 
  else{
    inorder(tree->I_child); //왼쪽 부트리로
    printf("%c", tree->data); //루트 노드 방문
    inorder(tree->r_chlid) //오른쪽 부트리로
  }
}


<후위 순회(Postorder traversal)>
- 5번 방식
  - 왼쪽 부트리를 먼저 방문하고, 오른쪽 부트리를 방문하고, 마지막으로 루트노드를 방문하는 순서이다
    왼쪽/오른쪽 부트리에 대해서도 마찬가지로 동일한 순서를 반복한다
  - 아래의 알고리즘은 후위 순회방식을 표현한 것으로 재귀함수로 구현되었다
    노드의 데이터 필드를 출력하는 명령문의 순서가 마지막으로 바뀐 것만 제외하고 전위순회 알고리즘과 동일
void postorder(struct bin_node *tree)
{
  if(tree==null) return;
  else{
    postorder(tree->I_child); //왼쪽 부트리로
    postorder(tree->r_child); //왼쪽 부트리로
    printf("%c", tree->data); //루트 노드 방문
  } 
}