이진트리(Binary Tree)

<이진트리(Binary Tree)>
- 이진트리는 많은 응용프로그램에서 사용되며 트리의 대표적인 구조로서 트리의 기본을 이룬다

- 이진트리의 특성
  - 모든 노드의 자식 노드의 개수가 2개 이하

- 엄격한 이진트리(Strictly binary tree) 
  - 말단 노드를 제외한 모든 노드의 차수가 2인 트리

- Knuth binary tree 
  - 노드의 차수가 0, 1, 2인 tree로 일반적인 binary tree

- 포화 이진트리(Full binary tree)
  - 깊이가 k인 이진트리에서 노드의 수가 (2^k)-1(k>0)로서 모든 말단 노드는 k번째 레벨이 존재

- 완전 이진트리(Complete binary tree)
  - 깊이가 k인 이진 트리에서 k-1 레벨까지는 포화 이진트리(Full binary tree)이고, 각 노드들이 깊이 k인 포화 이진트리의 
    노드 번호들과 일대일로 일치하는 경우 그 역도 성립한다

- 포화 이진트리의 노드 개수 
  - 2^0 + 2^1 + 2^2 + ... + 2^(k-1)

- 깊이가 k인 포화이진 트리의 노드 수
  - (2^k)-1
  따라서, 임의의 레벨 i(i>=1)의 최대 노드 수는 (2^i)-1

- 트리를 구성하는 노드의 수(n)를 알고 이진 트리의 깊이를 구할 때
  - 포화이진 트리의 깊이 k는 
    n = (2^k) -1
    n + 1 = 2^k
    log2 (n+1) = k

  - 완전 이진트리의 경우
    - k = [log2 (n+1)] -> 자리수 올림
      즉, log2 (n+1)은 노드 수가 n인 포화이진 트리의 깊이가 된다. 만일 그 값보다 하나라도 많아지면
      소수점 이하 값이 발생하고 자리 수 올림에 의해 깊이가 1증가하게 된다

- 포화이진 트리의 부모 자식 노드 사이의 관계는 아래와 같다
  - 전체 노드 수가 n일 때,
    i번 노드의 부모 노드는
    [i/2] ->자리수 내림,    1<=[i/2]<=n 범위를 만족
    범위 밖의 경우 부모 노드가 존재하지 않는다
  - i번 노드의 왼쪽 자식은 2i번 노드이고 1<=2i<=n의 범위이며, 이 범위 밖의 경우 왼쪽 자식 노드가 없다
  - i번 노드의 오른쪽 자식은 (2i+1)번 노드이고 1<=(2i+1)<=n 의 범위이며, 이 범위 밖의 경우 오른쪽 자식은 없다

- 이진 트리의 표현
  - 이진 트리의 구현은 배열을 이용한 방법과 포인터를 이용한 연결리스트 방법이 있다

- 배열에 의한 표현
  - 완전 이진트리의 레벨 오더에 의한 순서를 첨자로 1차원의 배열에 순차적으로 입력 시켜 표현을 한다
    즉, 완전 이진트리로서 공간을 확보한다
   *레벨 오더(Level Order) : 노드에 번호를 지정한다 -> '배열'로 구현하기 위해서 첨자는 '0' 부터 시작한다
    레벨은 위에서 아래로, 왼쪽에서 오른쪽으로 증가
    데이터의 크기와 상관없이 예시를 들기위해서 번호(첨자)를 지정한다

- C언어의 배열 첨자 규칙(첨자가 0부터 시작)에 따르기 위해 위에서 주어진 부모/자식 노드 사이의 관계를 약간 수정한다
  - i번 노드의 부모 노드는 [(i-1)/2] -> 자리수 내림 이고,
    0<=[(i-1)/2]<=n-1 범위를 만족한다
  - i번 노드의 왼쪽 자식은 2i+1번 노드이고 0<=(2i+1)<=n-1의 범위이며, 이 범위 밖의 경우 왼쪽 자식 노드가 없다
  - i번 노드의 오른쪽 자식은 2(i+1)번 노드이고 0<=2(i+1)<=n-1의 범위이며, 이 범위 밖의 경우 오른쪽 자식은 없다



<배열의 특징>
- x[i] -> 데이터 공간을 확보
- scanf "%d", &[i] -> 외부에서 받아드리는 정보를 저장할 수 있다
- 배열의 각각의 공간에 찾아들어가기 위해서 쓰이는 것 :  배열의 첨차를 사용, 임의의 정보에 저장 또는 위치시킬 수 있다
- 데이터가 저장될 공간(0~(n-1))은 연속된 공간에 저장되어 있으며
  동일한 데이터 타입(Type)이어야 하며, 배열의 크기가 미리 고정되어 있어야한다(유연성이 떨어짐)
- int x[100] 일 때, 메모리를 10개만 쓰인다면 상당히 비효율적인 구조이다
  또는 int x[10]일 때, 메모리를 100개를 쓴다면 데이터를 저장하기에 공간이 부족하다
- 부모와 자식의 위치를 배열의 첨자를 계산하므로써 데이터를 넣을 수 있다
  *트리(Tree)는 동적인 구조이다. 즉, 크기나 구조가 가변적으로 변화할 수 있다는 의미이다