[자료구조] 이진트리 정의 (in python)

강의 출처) 숙명여자대학교 소프트웨어융합전공 강의 "자료구조", 이현자 교수님

1. 트리

: 계층적 자료의 표현에 적합한 자료 구조
= 루트 노드 + 서브 트리

 

---

2. 이진트리

1) 이진트리란 ?

: 모든 노드가 2개의 서브 트리(노드)를 갖는 트리

• 서브 트리는 공집합일 수도 있음
• 루트와 왼쪽 서브트리 & 오른쪽 서브트리로 구성된 노드들의 집합
• 이진트리의 서브트리는 모두 이진트리

 

2) 허프만 코드 트리

: 문자에 대한 컴퓨터 내부 표현 중 하나 -> 텍스트 문서 압축

• 빈도수가 높은 문자에 대해서는 짧은 코드를 부여
• 빈도수가 적은 문자에 대해서는 긴 코드를 부여
• 결론적으로 최대한 적은 비트만 차지하도록 하는 것

 

3) 트리 관련 용어

• 노드 : 데이터와 연결선으로 구성된 트리의 한 유닛
• 노드의 차수 : 해당 노드의 자식 노드 개수
• 트리의 차수 : 모든 노드의 차수 중 최대값
• 단말 노드 (leaf [terminal] node) : 자식 노드가 없는 트리의 가장 끝에 위치한 노드
• 비단말 노드 : 단말 노드를 제외한 모든 노드
• 깊이 (level) : 루트 노드(0) ~> 단말 노드 방향으로 1씩 증가
• 부모 노드 : 노드의 부모노드라면 노드보다 level이 1만큼 작은 노드를 의미
• 자식 노드 : 노드의 자식노드라면 노드보다 level이 1만큼 큰 노드를 의미
• 형제 노드 : 같은 부모 노드를 가지는 노드들
• 조상 노드 : 노드 ~ 루트 노드 사이의 노드들
• 후손 노드 : 노드의 자식노드 이후의 모든 노드들
• 노드의 깊이 : 루트노드 ~ 노드 연결선의 수
• 노드의 높이 : 노드 ~ 단말노드 연결선의 수
• 트리의 높이 = 트리의 깊이 (루트노드 ~ 단말노드)

 

4) 최대 노드의 수

(1) 각 레벨에서의 최대 노드 수

 

• i: 트리의 레벨
  ex) 루트 노드의 level = 0 -> 1

(2) 트리 높이에 따른 최대 노드 수

• 포화 이진트리
  -> -1의 의미 : 루트노드는 한 개니까 !
   

 

5) 트리 종류

(1) 포화 이진 트리

• 모든 노드가 2개의 자식 노드를 가지는 트리
• 모든 리프 노드의 레벨이 동일함

 

(2) 완전 이진 트리

• 포화 이진 트리의 leaf들이 오른쪽부터 제거되면서 얻어진 트리
• 높이가 h일 때, 레벨 1부터 h-1까지는 노드가 모두 채워져 있고
• 마지막 레벨 h에서는 왼쪽 -> 오른쪽 방향으로 노드가 채워져 있음