[자료구조] 트리(tree) 용어 정리하기

 

<트리의 구성>

1) root가 아닌 노드들은 보모가 하나이다.

2) leaf가 아닌 노드들은 자식을 하나 이상 가지고 있다.

 

 

 

용어 정리 (괄호 안에 있는 노드가 위의 트리에서 용어에 해당하는 노드이다)

 

root node: 가장 위에 있는 노드로 부모 노드(parent)가 없다. ( = A)

leaf node: 자식 노드(child)가 없는 노드 (= E, C, F, K, I, J)

interior node: root 와 leaf노드가 아닌 노드 (= B, D, G, H)

 

Depth == Height == Level: 노드의 높이

( level 0 = A

level 1 = B, C, D

level 2 = E, F, G

level 3 = H, I, J

level 4 = K)

 

Degree: 자식 노드의 개수

(A: degree = 3

B: degree = 1

C: degree = 0

D: degree = 2

E: degree = 0

F: degree = 0

G: degree = 3

H: degree = 1

I: degree = 0

J: degree = 0)

 

트리 표현 방법: 괄호 안에는 child node를 적고 쉼표 옆에 sibiling(같은 level에 있는 노드) 적기 

(A(B(E),C,D(F,G(H(K),I,J))))