[자료구조] 이진 트리 (Binary Tree)

이진 트리 (Binary Tree)

• 모든 노드의 차수가 2 이하인 트리

​

이진 트리 종류

1. 포화 이진 트리 (Full Binary Tree)

• 모든 레벨의 노드가 꽉 차있는 이진 트리
• n = 2 ^ h - 1 ( 높이가 h 인 이진 포화 트리의 노드 개수)

레벨 3짜리 포화 이진 트리

 

​

2. 완전 이진 트리 (Complete Binary Tree)

• 높이가 h 일 때, 레벨1 ~ 레벨 h-1까지는 포화 이진트리처럼 꽉 채워져 있고 마지막 레벨 h(단말 노드) 에서는 중간에 빈 노드 없이 노드가 왼쪽부터 차례로 채워져 있어야함.
• n < 2 ^ h - 1 (높이가 h인 완전 이진 트리의 노드 개수)

완전 이진 트리 조건 만족

 

완전 이진 트리 조건 만족(만약 4가 2의 오른쪽에 있었다면 불만족)

 

​

3. 편향 이진 트리 (Skewed Binary Tree)

• 같은 높이의 이진 트리 중에서 최소 개수의 노드 개수를 가지면서 왼쪽 혹은 오른쪽 서브트리만을 가지는 이진트리

왼쪽 편향 이진 트리

 

오른쪽 편향 이진 트리

 

​

배열을 이용한 이진 트리 구현

• 노드 i의 부모 노드 : floor(i/2)
• 노드 i의 왼쪽 자식 노드 : i * 2
• 노드 i의 오른쪽 자식 노드 : i * 2 + 1