트리

• 노드와 링크로 구성된 자료 구조
• 그래프의 일종
  -> 순환하면 그래프 , 순환하지 않으면 트리
• 계층적 구조를 나타낼 때 사용
  -> 폴더구조, 조직도, 가계도

트리의 구조

• 노드
  트리 구조의 자료값을 담는 단위
• 에지 = 엣지 = 간선 = edge = branch = link
  노드간의 연결선
• 루트 노드 = Root
  부모가 없는 노드. 최상위 노드
• 잎새 노드 = 단말 노드 = Leaf
  자식이 없는 노드
• 내부 노드
  잎새노드를 제외한 모든 노드
• 부모 노드
  연결된 두 노드 중 상위인 노드
• 자식 노드
  연결된 두 노드 중 하위인 노드
• 형제 노드
  같은 부모를 가지는 노드
• 레벨
  트리의 특정 깊이를 가지는 노드 집합
• 깊이
  루트에서 어떤 노드까지의 간선 수
• 높이
  트리에서 가장 큰 레벨 값
• 크기
  자신을 포함한 자식 노드의 개수
• 차수
  각 노드가 지닌 가지의 수
• 트리의 차수
  트리의 최대 차수

트리의 특징

• 하나의 노드에서 다른 노드로 이동하는 경로는 유일하다
• 노드가 N개인 트리의 간선의 개수는 N - 1개
• Cycle이 존재하지 않음 = Acyclic
• 모든 노드는 서로 연결되어있다.
• 하나의 Edge를 끊으면 2개의 Sub Tree로 분리됨

이진 트리

• 각 노드는 최대 2개의 자식을 가질 수 있음
• 자식 노드는 좌우를 구분함
  -> 왼쪽 자식 : 부모의 왼쪽 아래 위치
  -> 오른쪽 자식 : 부모의 오른쪽 아래 위치

이진트리 종류

• 포화 이진 트리
  모든 레벨에서 노드들이 꽉 채워져있음
• 완전 이진 트리
  마지막 레벨을 제외하고 노드들이 모두 채워져있음
• 정 이진 트리
  모든 노드가 0개 또는 2개의 자식노드를 갖는다.
• 편향 트리 = 사향 트리
  한쪽으로만 가지가 이어진 트리. ( 왼쪽 자식만 있는 트리 / 오른쪽 자식만 있는 트리 )
• 균형 이진 트리
  모든 노드의 좌우 서브 트리 높이가 1 이상 차이나지 않는 트리

이진트리 특징

• 포화 이진 트리의 높이가 h 일 때, 노드의 수는 2^(h+1) - 1 개
• 포화 이진 트리의 노드가 N개 일 때, 높이는 logN
• 이진 트리의 노드가 N개 일 때, 최대 가능 높이는 N-1

이진트리의 순회

• 모든 노드를 빠뜨리거나, 중복하지 않고 방문하는 연산

• 순회 종류는 4가지

  1. 전위 순회 Pre-Order : 현재 -> L -> R 순서로 움직임
  2. 중위 순회 In-Order : L -> 현재 -> R 순서로 움직임
  3. 후위 순회 Post-Order : L -> R -> 현재 순서로 움직임
  4. 레벨순회 Level-Order : 레벨 마다 L->R 로 움직임. 일반 배열의 형태

  여기서
  전위순회,중위순회,후위순회를 DFS: 깊이 우선 탐색
  레벨순회를 BFS: 너비 우선 탐색라고 분류한다.

(조..조금 나중에 다시봐야겠다..!)

이진트리의 구현

-> 레벨 순회 순서로 배열에 구성한다.
( 루트가 1일때 )
* 부모 노드 = idx / 2
* 왼쪽 자식 = 2 idx + 0
* 오른쪽 자식 = 2 idx + 1