Tree

1. Tree란?

• Node와 Edge로 구성되어 있는 자료구조
• 스택, 큐, 리스트 와 달리 비선형 구조로 되어있음

2. 용어

• 부모 노드 (parent)
  어떤 노드의 바로 위로 연결된 노드

• 자식 노드 (child)
  어떤 노드의 바로 밑으로 연결된 노드

• 루트 노드 (root)
  부모 노드가 없는 노드. 트리의 맨 위에 있는 노드로 트리의 시작점이 됨

• 리프 노드 (leaf nodes)
  자식 노드가 없는 노드

• 내부 노드 (internal nodes)
  부모 노드와 자식 노드가 둘 다 존재하는 노드
  

• 노드의 수준 (level)
  루트 노드와의 거리
  

• 노드의 차수 (degree)
  자식 노드들의 갯수
  

• 트리의 높이 (height/depth)
  트리가 갖는 최대 수준

• 부분 트리 (서브트리; subtrees)
  트리 구조를 갖는 부분집합

3. 특수한 트리

• 이진 트리 , 포화 이진 트리 , 완전 이진 트리