[자료구조] 트리(Tree)

트리(Tree)

• 노드와 링크로 구성된 자료구조
• 계층적 구조를 나타낼 때 사용
  ex) 폴더 구조, 조직도, 가계도, etc.

트리의 특징

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

이진 트리 종류

1. 이진 트리(Binary Tree)

• 각 노드는 최대 2개의 자식을 가질 수 있다.
• 자식 노드는 좌우를 구분한다.

2. 포화 이진 트리(Perfect Binary Tree) : 모든 레벨에서 노드들이 꽉 채워져 있는 트리

3. 완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외하고 노드들이 모두 채워져 있는 트리

4. 정 이진 트리(Full Binary Tree) : 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

5. 편향 트리(Skewed Binary Tree) = 사향 트리 : 한쪽으로 기울어진 트리

6.균형 이진 트리(Balanced Binary Tree) : 모든 노드의 좌우 서브 트리 높이가 1이상 차이 나지 않는 트리

이진 트리 특징

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

트리 순회 방식

• 모든 노드를 빠뜨리거나 중복하지 않고 방문하는 연산
• 순회의 4가지 종류
  • 전위 순회, 중위 순회, 후위 순회 → DFS
  • 레벨 순회 → BFS

1. 전위 순회(Preorder Traversal)

• 방문 순서 : 현재 노드 → 왼쪽 노드 → 오른쪽 노드

2. 중위 순회(Inorder Traversal)

• 방문 순서 : 왼쪽 노드 → 현재 노드 → 오른쪽 노드

3. 후위 순회(Postorder Traversal)

• 방문 순서 : 왼쪽 노드 → 오른쪽 노드 → 현재 노드

4. 레벨 순회(Levelorder Traversal)

• 방문 순서 : 위쪽 레벨 부터 왼쪽 노드 → 오른쪽 노드

이진 트리 구현

• 배열
  • 레벨 순회 순으로 배열에 구성

• 연결 리스트
  • 값과 간선을 관리하기 위한 노드로 연결리스트 구성
  • 값을 넣을 공간 1개, 왼쪽 노드를 가리킬 공간 1개, 오른쪽 노드를 가리킬 공간 1