Tree : 개념 정리

1. Tree

  :  그래프 중 cycle이 없는 형태

 

 

2. Terminology

Node	Tree 구성요소
Ancestor	한 node의 parent, grandparent 모두
Offspring node	한 node의 child, grandchild 모두
Root	Node without Parents
Subtree	하나의 node와 그 descendants로 구성된 tree
Terminal node	Node without children
Non-terminal node	Node with at least one child
level	tree의 layer 수 (3)
height	maximum level of the tree
degree	그 node가 가진 child nodes의 수

 

 

 

 

3. Tree Type

Binary Tree	General Tree
degree ≤ 2 child node가 최대 2개	degree > 2 child node가 3개 이상

 

 

 

4. Binary Tree

① Full Binary Tree	② Complete Binary Tree	③ Other Binary Tree
level마다 node가 full  (node 개수 최대)	마지막 level 제외한 모든 level이 full	Full  & Complete  나머지