[Algorithm] Tree 기초개념

>다양한 트리를 배우기전에 트리에 나오는 명칭에 대해 알아보는 시간을 가져보자.

 

node란 A, B, C, D, E, F, G, H, I, J, K, L처럼 데이터를 가지는 분기점을 말하고,
node와 node사이의 연결선을 edge라 한다.

B의 parent node는 A 이며, parent node가 없는 node를 root라하며 여기서는 A이다.

B의 child는 E, F 이다.

 

degree(차수)란 child node의 수를 말한다.  A의 Degree는 3, C의 Degree는 1이다.

leaf node란 child node를 가지지 않는 node로서, 여기선 K, L, F, G, M, I, J 를 말한다.

 

B 의 subtree는 위 그림과 같이 E, K, L과 F 이다.

 

 

level이란 root node를 1은 가진다고 가정하고 child node갈때마다 1을 더한값이다.

즉, root node로 부터의 거리 + 1 이다.