이진트리(Binary Tree)란?

• 어떤 노드의 자식 노드의 수가 최대 2개인 트리

• 공집합 혹은 루트(root)와 왼쪽 서브 트리, 오른쪽 서브 트리로 이루어진 유한 집합, 각각의 서브 트리는 모두 이진 트리이다.

• 트리는 connected acyclic graph

  • 루트 노드(root)를 반드시 가진다.
  • 트리를 구성하는 노드 간 단순 경로가 존재한다.

• 트리는 1개 이상의 노드로 이루어진 유한 집합

  • 루트 노드(root)를 반드시 가진다.
  • 나머지 노드들은 분리집합 T1, …, Tn으로 분할 가능
    • T1, T2 등은 각각의 하나의 트리(서브 트리)가 된다.