이진 트리(Binary Tree)의 개념
-이진 트리(Binary Tree) : 모든 노드의 자식 노드가 최대 두 개인 트리
이진 트리(Binary Tree)의 종류
- 완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있고, 마지막 노드는 왼쪽부터 있는 이진 트리
- 정 이진 트리(Full Binary Tree) : 모든 노드가 0개 혹은 2개의 자식 노드를 갖는 이진 트리
- 포화 이진 트리(Perfect Binary Tree) : 모든 레벨이 전부 채워져 있는 이진 트리
- 사향 이진 트리(Skewed Binary Tree) : 모든 내부 노드가 한쪽 방향으로 1개의 자식 노드만을 가진 이진 트리
1. 완전 이진 트리(Complete Binary Tree)
-마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있고, 마지막 노드는 왼쪽부터 있는 이진 트리
- 위 그림의 이진 트리는 마지막 레벨을 제외한 모든 레벨이 완전히 채워져있다.
- 마지막 레벨의 노드는 왼쪽부터 있는다.
-위 이진 트리처럼, 이 두 가지 조건을 만족하는 이진 트리를 완전 이진 트리라고 한다.
- 위 이진 트리는 완전 이진 트리가 아니다.
-마지막 레벨을 제외한 모든 레벨은 완전히 채워져있지만, 마지막 레벨의 노드들이 왼쪽부터 있지 않다.(노드 L)
2. 정 이진 트리(Full Binary Tree)
-모든 노드가 0개 혹은 2개의 자식 노드를 갖는 이진 트리
- 위 이진 트리의 모든 노드는 0개 혹은 2개의 자식 노드를 가진다.
- 즉, 모든 내부 노드는 2개의 자식 노드를 가진다.
-위의 조건을 만족하는 이진 트리를 정 이진 트리라고 한다.
- 위 이진 트리는 정 이진 트리가 아니다.
-노드 E가 하나의 자식 노드를 가지고 있기 때문이다. 정 이진 트리의 모든 내부 노드는 2개의 자식 노드를 가져야 한다.
3. 포화 이진 트리(Perfect Binary Tree)
-모든 레벨이 전부 채워져 있는 이진 트리
-즉, 모든 리프 노드의 레벨이 동일하다.
- 위 이진 트리의 모든 레벨이 전부 채워져 있다.
- 즉, 모든 리프 노드의 레벨이 동일하다.
-위의 조건을 만족하는 이진 트리를 포화 이진 트리라고 한다.
-포화 이진 트리라면 정 이진 트리이자 완전 이진 트리라고 할 수 있다.
- 위 이진 트리는 포화 이진 트리가 아니다.
-노드 G가 하나의 자식 노드를 가지고 있기 때문이다. 포화 이진 트리의 모든 내부 노드는 2개의 자식 노드를 가져야 한다.
-마지막 레벨이 전부 채워져 있지 않기 때문이라고도 할 수 있다.
4. 사향 이진 트리(Skewed Binary Tree)
-모든 내부 노드가 한쪽 방향으로 1개의 자식 노드만을 가진 이진 트리
- 위 그림의 이진 트리에서 모든 내부 노드는 한쪽 방향으로 하나의 자식 노드만을 가진다.
-위와 같은 조건을 만족시키는 이진 트리를 사향 이진 트리라고 한다.
-간선의 방향에 따라서 좌 사향 이진 트리와 우 사향 이진 트리가 있다.
- 위의 두 이진 트리는 사향 이진 트리가 아니다.
- 간선의 방향이 서로 다른 경우가 있기 때문이다. 사향 이진 트리의 모든 내부 노드는 한쪽 방향으로 하나의 자식 노드를 가져야 한다.
'자료구조' 카테고리의 다른 글
| [자료구조]완전 이진 트리를 배열로 나타내기 (0) | 2023.05.24 |
|---|---|
| [자료구조]두 이진 트리가 같은지 판별하는 법(Testing for Equality of Binary Trees) (0) | 2023.05.23 |
| [자료구조]이진 트리를 복사하는 법(Copying Binary Trees) (0) | 2023.05.23 |
| [자료구조]트리 순회(Tree Traversals) (0) | 2023.05.23 |
| [자료구조]트리(Tree)의 개념 (0) | 2023.05.18 |
