목차

트리(tree)란 무엇인가?

출처 : Monsieur_Songsong

트리 구조는 비선형(Non-linear) 자료구조 중 하나이다. 비선형 자료구조에서는 하나의 자료 뒤에 여러 개의 자료가 존재할 수 있기 때문에 폴더 구조와 같은 계층적 구조를 나타내기에 적절하다.

트리 용어 정리

출처 : Velog

주로 사용하는 용어는 다음과 같다.

• 노드의 깊이(depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
  • D 의 깊이 : 2
  • H 의 깊이 : 3
• 노드의 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합. 0 또는 1부터 시작한다.
  • A 의 레벨 : 0
  • B, C 의 레벨 : 1
• 트리의 높이(height) : 루트 노드에서 가장 깊숙히 있는 노드의 깊이
  • 3

이진 트리(binary tree)

이진 트리란 모든 노드의 자식 노드가 최대 2개의 노드를 가지는 트리를 의미한다.

이진 트리의 종류

이진 트리는 아래의 그림처럼 형태에 따라 세부적으로 다르게 부르고 있지만, 결국 모두 이진 트리이다.

출처 : github.io

• 포화 이진 트리(full binary tree)
  • 모든 레벨에서 노드들이 모두 채워진 트리
• 완전 이진 트리(complete binary tree)
  • 마지막 레벨을 제외하고 노드가 모두 채워진 트리. 마지막 레벨도 다 채워져 있을 수도 있다.