54. 트리(Tree)

정점(Node, 노드)과 선분(Branch, 가지)을 이용하여 사이클을 이루지 않도록 구성한 Graph의 특수한 형태로 가족의 계보(족보), 연산 수식, 회사 조직 구조도, 히프(Heap) 등을 표현하기에 적합하다. 

 

노드 : 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지를 합친 것

예) A B C D E F G H I J K L M

 

근 노드(Root Node) :  트리의 맨 위에 있는 노드

예) A

 

디그리(Degree, 차수) : 각 노드에서 뻗어나온 가지의 수

예) A=3 B=2 C=1 D=3

 

트리의 디그리 : 노드들의 디그리 중에서 가장 많은 수

예) 노드 A나 D가 3개의 디그리를 가지므로 위 트리의 디그리는 3이다

 

단말 노드(Terminal Node) = 잎 노드(Leaf Node) : 자식이 하나도 없는 노드, 즉 디그리가 0인 노드

예) K L F G M I J

 

비단말 노드(Non-Terminal Node) : 자식이 하나라도 있는 노드, 즉 디그리가 0이 아닌 노드

예) A B C D E H

 

자식 노드(Son Node, Children Node) :  어떤 노드에 연결된 다음 레벨의 노드들

예) D의 자식 노드 : H I J

 

부모 노드(Parent Node) : 어떤 노드에 연결된 이전 레벨의 노드

예) E, F의 부모 노드는 B

 

형제 노드(Brother Node, Sibling) : 동일한 부모를 갖는 노드들

예) H의 형제 노드는 I, J

 

Level : 근 노드의 레벨을 1로 가정한 후 어떤 레벨이 L이면 자식 노드는 L+1 이다 

예) H의 레벨은 3

 

깊이(Depth, Height) : 어떤 Tree에서 노드가 가질 수 있는 최대의 레벨

예) 위 트리의 깊이는 4