트리(Tree)

<트리(Tree)>
​

원소들 간에 1:多 관계를 가지는 비선형 자료구조이며, 원소들 간에 계층관계를 가지는 계층형 자료구조이다. 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무)모양의 구조

[트리관계 해설]

① 노드(node) – 트리의 원소
−트리 A의 노드 - A,B,C,D,E,F,G,H,I,J,K,L
② 루트 노드(root node) – 트리의 시작 노드 (루트노드 - A)
③ 간선(edge) – 노드를 연결하는 선. 부모 노드와 자식 노드를 연결
④ 형제 노드(sibling node) – 같은 부모 노드의 자식 노드들 (B,C,D는 형제 노드)
⑤ 조상 노드 – 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들 (K의 조상 노드 : F, B, A)
⑥ 서브 트리(subtree) – 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
−각 노드는 자식 노드의 개수 만큼 서브 트리를 가진다.
⑦ 자손 노드 – 서브 트리에 있는 하위 레벨의 노드들 (B의 자손 노드 – E,F,K,L)

⑧ 차수(degree) - 노드의 차수 : 노드에 연결된 자식 노드의 수.
A의 차수=3, B의 차수=2, C의 차수=1, D의 차수=3
⑨ 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
트리 A의 차수=3
⑩ 단말 노드(리프 노드) : 차수가 0인 노드. 자식 노드가 없는 노드

 

노드의 높이 : 루트에서 노드에 이르는 간선의 수. 노드의 레벨
B의 높이=1, F의 높이=2

포리스트(forest) : 서브트리의 집합
−트리A에서 노드 A를 제거하면, A의 자식 노드 B, C, D에 대한 서브 트리가 생기고, 이들의 집합은 포리스트가 된다.

Copyrightⓒ2014 By 한빛아카데미(주)