각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조
자식 노드를 왼쪽 자식 노드와 오른쪽 자식 노드라고 부른다.
이진 트리의 종류
- 루트 이진 트리 : 하나의 루트 노드를 가지며 모든 노드가 최대 두 개의 자식 노드를 갖는다.
- 정 이진 트리 : 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리다.
- 포화 이진 트리 : 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 리프 노드가 동일한 깊이 또는 레벨을 갖는다.
- 완전 이진 트리 : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있다.
- 무한 완전 이진 트리 : 모든 노드는 두 개의 자식 노드를 갖는다. 모든 노드 집합은 가산 무한이지만, 루트로부터의 모든 무한한 경로 집합은 연속체의 원소 개수를 가지고 있어 셀 수 없다.
- 균형 이진 트리 : 리프 노드에 대해 가능한 한 최대의 깊이를 갖는데, 주어진 수의 리프 노드에 대해, 리프 노드가 가능한 가장 큰 높이에 위치하기 때문이다.
- 변질 트리 : 각 부모 노드는 오직 한 개의 연관 자식 노드를 갖는다. 이는 성능 면에서 트리가 연결 리스트 데이터 구조처럼 동작한다.
이진 트리의 속성
- 정 이진 트리에서 노드 개수 n은 최소 2h + 1, 최대 2^(h+1) - 1이며, 여기서 h는 트리의 높이다.
- 이진 트리의 높이가 h라면, 노드의 수는 최소 h, 최대 2^(h+1) - 1이다.
- 완전 이진 트리의 높이가 h라면, 노드의 수는 최소 2^h, 최대 2^(h+1) - 1이다.
- 완전 이진 트리의 노드에 0부터 시작하여 번호를 매긴다면, i번째 노드의 자식노드는(존재한다면) 2i + 1, 2i + 2번째 노드이며, 부모노드는(존재한다면) (i - 1) / 2 의 최대정수 번째 노드이다.
이진 트리의 표현 방법
- 1차원 배열 표현 : 이진 트리의 i번째 노드를 배열의 i번째 요소에 저장하는 방법이다.
1. 장점: 노드의 위치를 색인에 의하여 쉽게 접근할 수 있다.- 단점: 특정 트리에서 기억 공간의 낭비가 심할 수 있다.
- 연결리스트 표현: 왼쪽 자식을 가리키는 포인터 필드와 오른쪽 자식을 가리키는 포인터 필드를 포함하는 노드로 표현하는 방법이다.
1. 장점 : 기억 장소를 절약할 수 있고, 노드의 삽입과 삭제가 용이하다.- 단점 : 이진 트리가 아닌 일반 트리의 경유에는 각 노드의 차수만큼 가변적인 포인터 필드를 가져야 하기 때문에 접근상의 어려움이 따른다.
