Tree

개념

• Stack, Queue와 같은 선형 자료구조는 연속적으로 값이 분포하지만 Tree는 비선형, 계층적 자료 구조를 가짐
• 노드들 간에 부모-자식 관계를 가짐
• Linked List와 유사한 구조를 가지지만 tree의 노드의 링크 필드는 자식과 연결됨
• 일반적인 경우 자식 노드의 개수에 제한은 없음
• 이진 트리(Binary Tree)는 최대 2개의 자식만 가짐

Level

• 부모-자식 관계를 1 단계 떨어진 관계로 볼때 tree의 층위의 개수
• 특정 노드가 루트 노드의 자식 노드라면 Level 2에 위치한 것임
  (루트 노드는 Level 1)

Height

• 전체 tree의 최대 Level

Degree

• 특정 노드가 가진 자식 노드의 개수

Forest

• 여러 tree들의 집합

구성 요소

Node

• 트리를 구성하는 기본 단위

Parent Node

• 하나 이상의 자식 노드와 연결된 노드

Child Node

• 부모 노드로부터 바로 연결된 노드

Sibling Node

• 같은 부모를 공유하는 노드 집합

Ancestor Node

• 특정 노드로부터 루트 노드까지 연속적으로 부모 관계에 있는 노드들의 집합

Descendant Node

• 특정 노드로부터 리프 노드까지 연속적으로 자식관계에 있는 노드들의 집합

Root

• 시작 지점 노드
• 다른 모든 노드들의 조상 노드

Subtree

• 한 노드와 해당 노드의 모든 자식 노드

Terminal Node (Leaf)

• tree의 마지막에 위치한 노드
• 자식 노드를 갖지 않는 노드

Nonterminal Node

• 자식 노드를 가진 노드