트리 구조

• 트리 : 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조
  - 루트노드(root node) : 부모가 없는 최상위 노드 (A)
  - 단말노드(leaf node) : 자식이 없는 노드 (G, E, F)
  - 크기(size) : 트리에 포함된 모든 노드의 개수 (7개)
  - 깊이(depth) : 루트 노드부터의 거리 (A의 깊이 : 0, B C의 깊이 : 1, D E F의 깊이 : 2 ...)
  - 높이(height) : 깊이 중 최댓값 (3)
  - 차수(degree) : 각 노드의 (자식방향) 간선 개수 (A의 차수 : 2, B의 차수 : 2, C의 차수 : 1 ...)
• 기본적으로 트리의 크기가 N일 때, 전체 간선 개수는 N - 1 개

• 이진 탐색 트리 (Binary Search Tree)
  - 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조
  - 특징 : 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
     - 부모 노드보다 왼쪽 자식 노드가 작음
     - 부모 노드보다 오른쪽 자식 노드가 큼
• 이진 탐색 트리에서 데이터를 조회하는 과정

   Ex) 37이라는 원소를 찾고자 할 때!

1. 루트 노드(30)부터 방문하여 탐색을 진행
   1) 현재 노드와 찾고자 하는 원소 37을 비교
   2) 찾는 원소가 더 크므로 오른쪽 노드 방문
2. 현재 노드(48)와 값을 비교 
   1) 현재 노드와 찾고자 하는 원소 37을 비교
   2) 찾는 원소가 더 작으므로 왼쪽 노드 방문
3. 현재 노드(37)와 값을 비교
   1) 현재 노드와 찾고자 하는 원소 37을 비교
   2) 찾고자 하는 원소를 찾았으므로 탐색 종료

• 트리의 순회 : 트리 자료구조에 포함된 노드를 특정한 방법으로 한번씩 방문하는 것!
  - 전위 순회 : 루트를 먼저 방문
  - 중위 순회 : 왼쪽 자식을 방문한 뒤에 루트를 방문하고 오른쪽 노드 방문
  - 후위 순회 : 왼쪽 자식을 방문한 뒤에 오른쪽 노드를 방문하고 루트 방문

• 전위 순회 : A - B - D - E - C - F - G
• 중위 순회 : D - B - E - A - F - C - G 
• 후위 순회 : D - E - B - F - G - C - A