트리의 기초

 

트리

 

계층 구조를 갖는 자료구조

부모 노드 - 자식 노드의 관계

 

 

트리의 용어

 

Root : 위치 상 맨 위 노드. 즉, 부모가 없는 노드. 

Internal node : 내부 노드. 자식이 적어도 하나 이상 있는 노드

External node(=Leaf) : 위치상 맨 끝 노드

Ancestors : 한 노드의 모든 상위 노드. 직속 상위+ root 까지의 모든 상위노드

Descendants : 한 노드의 모든 하위노드. 직속 하위 + leaf 까지의 모든 하위노드 

Depth(깊이) : 한 노드의 조상 수. root = 0부터 시작해서 아래로 갈수록 1씩 늘어남.

Height(높이) : 트리의 노드 중 Depth(0~)의 최댓값

Subtree(부분트리) : 한 노드와 그 노드의 후손을 전부 포함하는 트리 요소. 부분집합처럼 생각하면 편함.

Degree(차수): 자식 노드의 개수

Level: 같은 Depth를 가진 노드들의 집합. 가로로 묶으면 됨

 

 

사진 출처: 위키트리 - 트리 구조

 

---