트리(Tree)

• 비선형 자료구조
• 계측적 관계를 표현한 자료구조
• Node(노드) Edge(간선)으로 구성
• 특징
  • 사이클이 존재하지 않는다
  • 루트에서 한노드로 가는 경로는 유일하다
  • 노드의 개수가 n이라면 간선은 n-1개 이다
• 트리 순회
  • 전위순회(pre-order)
    • 부모노드를 먼저 탐색 후 왼쪽, 오른쪽 자식 노드로 탐색
  • 중위순회(in-order)
    • 왼쪽노드를 먼저 탐색 후 부모, 오른쪽 자식 노드로 탐색
  •  후위순회(post-order)
    • 왼쪽노드, 오른쪽 노드 탐색 후 부모노드 탐색
  • 레벨순회(level-order)
    • 루트부터 계층별로 탐색
• 이진 트리(Binary Tree)
  • 자식이 최대 두개인 트리
  • 포화 이진 트리
    • 모든 레벨이 꽉찬 트리
  • 완전 이진 트리
    • 왼쪽 부터 차례대로 채워진 이진트리