Binary Tree   이진 트리

1. 이진 트리 (Binary Tree)

  ㅇ 모든 노드의 차수/자식이, 2 이하(최대 2)인 특수한 형태의 순서 트리
     - 자식이 0,1,2개 만을 갖음 
        . 빈 트리(자식이 0개)도 유효한 이진 트리임


2. 이진 트리의 특징

  ㅇ 각 노드의 차수가 2 이하의 자식 노드를 갖음
     - 자식 노드가 좌,우로 구분됨
  ㅇ 이진 트리는 순서 트리 임
     - 노드 위치 및 순서가 중요한 의미를 갖음
        
  ㅇ 루트 노드 레벨(level)은, 0 으로 함
  ㅇ 레벨 깊이(depth) i일 경우에, 
     - 갖을 수 있는 최대 노드 수는, 2i - 1


3. 이진 트리의 표현, 구현

  ㅇ 선형 자료구조인 `일차원 배열`로써 표현, 구현
     - 저장 공간 활용 비효율적, 부모 자식 노드 구분이 어려움
     - 다만, 완전이진트리에는 좋은 성능을 갖음
     - 프로그램 구현 용이

  ㅇ 비선형 자료구조인 `연결 리스트`로써 표현, 구현 
     - 저장 공간 효율적 활용 등으로 보다 유용함


4. 이진 트리의 순회 (Binary Tree Traversal)                                   ☞ 트리 순회 참조

  ㅇ 각 노드를 한번씩 만 방문하며 저장 정보를 확인하는 것

  ㅇ 순회 종류 : 방문 순서에 따른 구분
     - 중위 순회 (Inorder)  : 왼쪽 서브트리 → 자신 → 오른쪽 서브트리
     - 후위 순회 (Postorder)
     - 전위 순회 (Preorder)


5. 이진 트리의 종류

  ※ ☞ 이진 트리 종류 참조
     - 전 이진 트리, 포화 이진 트리, 완전 이진 트리, 이진 힙, 균형 트리 등