이진 트리

목차

 

📍 정의 및 특징

각 노드의 자식 노드(=차수)가 2 이하인 트리

- 어떤 노드를 선택했느냐에 따라 결과가 달라지므로, 항상 같은 결과 보장 X

- 시간 복잡도 : O(V + E)

 

#사이클X  #방향그래프

 

📍 종류

① 편향 이진 트리

② 포화 이진 트리 - 트리 높이 모두 일정 & 리프 노드 꽉 참

③ 완전 이진 트리 - 마지막 레벨 제외 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 트리

 

 

📍 순차 표현

   - 1차원 ‘배열’ 형태로 표현

  - 트리의 노드와 배열의 인덱스 간 상관 관계

 

 

➕ 예제

[백준/JAVA] 1991번: 트리 순회