트리(Tree)?

트리는 노드와 링크로 구성된 비선형 자료구조이다. 계층적 구조를 나타낼 때 사용한다.
BFS / DFS 와 같은 문제를 푸는 경우 비-선형 구조의 형태를 많이 활용 한다.
먼저 선형구조와 비선형구조의 차이점을 알아보자.

	선형	비선형
데이터 저장형태	순차적으로 순회하도록 저장	계층적으로 연결되어 저장
순회	단일 동작으로 모든 데이터 순차적 순회 가능	복수의 동작 필요
구현 복잡도	쉬움	어렵다
메모리 활용	낮음	높음
시간 복잡도	저장 공간에 비례하여 증가	선형보다 적게 증가

트리의 구조

• 노드(Node):트리 구조의 자료 값을 담고 있는 다위
• 엣지(Edge):노드 간의 연결 선(=link)
• 루트 노드(Root):최상위 노드, 부모가 없는 노드
• 리프 노드(Leaf):최말단 노드, 자식이 없는 노드
• 내부 노드(Internal):리프노드를 제외한 모든 노드
• 형제(Sibling):같은 부모를 가지는 노드
• 깊이(Depth):루트에서 현재 노드까지의 엣지 수
• 레벨(Level):트리의 특정 깊이를 가지는 노드 집합
• 높이(Height):트리에서 가장 큰 레벨 값
• 크기(Size):자신을 포함한 자식 노드의 개수
• 차수(Degree):각 노드가 지닌 엣지의 수
• 트리의 차수:트리의 최대 차수

트리의 특징

• 하나의 노드에서 다른 노드로 이동하는 경로는 유일하다.
• 노드가 N개인 트리의 Edge 수는 N-1개.
• Cycle이 존재하지 않음.(트리와 그래프의 차이점, Cycle이 있다면 그래프이다.)
• 모든 노드는 서로 연결되어 있다.
• 하나의 Edge를 끊으면 2개의 Sub-Tree로 분리된다.

---

이진 트리(Binary Tree)

• 각 노드는 최대 2개의 자식을 가진다.
• 자식 노드의 좌우를 구분한다.
  
• 포화 이진 트리 : 모든 레벨에서 노드들이 꽉 채워져 있는 트리.
• 완전 이진 트리 : 마지막 레벨을 제외하고 노드들이 모두 채워져 있는 트리.
• 정 이진 트리 : 모든 노드가 0 or 2개의 자식 노드를 갖는 트리.
• 편향 트리(사향 트리) : 한 쪽으로 기울어진 트리.
• 균형 이진 트리 : 모든 노드의 좌우 서브 트리 높이차이가 1 이하인 트리.
  

이진 트리의 특징

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

이진 트리의 순회

모든 노드를 중복하지 않고 방문하는 연산.

1. 전위 순회(Preorder Traversal)

• 현재 노드 -> 왼쪽 노드 -> 오른쪽 노드
  

순회 경로 : A > B > D > H > E > C > F > J > G

2. 중위 순회(Inorder Traversal)

• 왼쪽 노드 -> 현재 노드 -> 오른쪽 노드
  

순회 경로 : H > D > B > E > A > F > J > C > G

3. 후위 순회(Postorder Traversal)

• 왼쪽 노드 -> 오른쪽 노드 -> 현재 노드
  

순회 경로 : H > D > E > B > J > F > G > C > A

4. 레벨 순회(Levelorder Traversal)

• Queue 자료구조를 사용
• 위 쪽 레벨부터 왼쪽->오른쪽
  

이진 트리 구현

• 배열(레벨 순회순으로 구성) - 완전 이진 트리만 가능.
  - 현재노드 index : i, 왼쪽 자식노드 index : i x 2 + 1, 오른쪽 자식노드 index : i x 2 + 2, 부모노드 index : i / 2
• 연결리스트(값과 간선을 가진 노드들로 구성)로 구현할 수 있다.