자료구조 - 이진트리

- 모든 노드가 2개의 서브 트리를 가지고 있는 트리

- n개의 노드를 가진 이진 트리는 정확하게 n-1개의 간선을 가짐

- 포화 이진 트리(full binary tree)
   : 각 레벨에 노드가 꽉 차 있는 이진트리
  완전 이진 트리(complete binary tree)
   : 높이가 k일 때 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨에서는 노드가 꽉 차 있지 않아도 되지만 중간에 빈 곳이 있으면 안 된다. 
  기타 이진 트리

- 배열 사용 시 1부터 사용, 포인터 사용 시 왼쪽, 오른쪽 자식 노드를 가리키는 포인터 필요

- 이진트리 순회
 V: 부모, L: 왼쪽 자식 노드, R: 오른쪽 자식노드
  ■ 전위 순회 : VLR
  ■ 중위 순회 : LVR
  ■ 후위 순회 : LRV
  => 큐, 재귀를 이용하여 구현 가능
 : 수신 트리를 처리하는 데 사용

- 스레드 이진트리 : 중위 후속자를 저장시켜 놓은 트리

- 이진 탐색 트리(binary search tree)
 : 모든 노드의 키는 유일하다.
 : 왼쪽 서브 트리의 키들은 루트의 키보다 작다.
 : 오른쪽 서브 트리의 키들은 루트의 키보다 크다.
 : 왼쪽과 오른쪽 서브 트리로 이진 탐색 트리이다.
 : 삽입, 삭제 시 노드를 재정렬한다.


 : 높이가 4이면,    
 : 평균 

 : 한 노드만 계속 하위 레벨로 붙어나가는 최악의 경우 O(n)이 발생
  => AVL 트리 등 사용
 : strcmp를 기준으로 사전식 정렬 가능