[자료구조] 트리(Tree)의 기본 개념 및 종류, 그림으로 쉽게 알기

---

트리

• 계층적인 구조를 나타내는 자료구조
• 부모 - 자식 관계의 노드들로 구성

 

---

트리 용어

• 노드(node) : 트리의 구성요소
• 간선(edge) : 노드를 연결하는 관계
• 루트(root) : 부모가 없는 노드(A)
• 단말 노드(terminal node) : 자식이 없는 노드( E, F, G, H, I, J )
• 비 단말 노드(non-terminal node) : 적어도 하나의 자식을 가지고 있는 노드( A, B, C, D )
• 서브 트리(subtree) : 하나의 노드와 그 노드들의 자손들로 이루어진 트리(점선)

 

• 자식/부모/형제/조상/자손 노드 : 인간과 동일함
• 레벨(level) : 트리의 각 층 번호
• 높이(height): 트리의 최대 레벨(3)
• 차수(degree) : 노드가 가지고 있는 자식 노드의 개수

 

---

트리의 종류

해당 트리를 연결 리스트로 표현하는 방법

• 일반 트리

 

• K차 트리 (ex 2차 트리, 3차 트리)
  • 해당 그림에서는 3차 트리
    
    • 사용하는 링크 필드의 개수 : 8개
    • NULL인 링크필드의 개수 : 19개

3차 트리

 

• 이진(binary) 트리
  • NULL인 링크 필드의 개수 : 10개
  • K차 트리 중 이진트리가 링크 필드 사용률이 가장 좋음.

이진 트리