[algorithm] binary tree

• binary tree 정의
• binary tree 종류
  • full binary tree
    • 모든 node는 0개 혹은 2개의 child
  • perfect binary tree
    • 모든 interior node는 2개의 child, 모든 leaf는 같은 level에 존재
  • complete binary tree
    • 마지막 level 이전은 perfect binary tree, 마지막 level(h)은 왼쪽부터 채워지고 1 ~ (2^h - 1)까지만 가능
• binary tree 특징
  • 일반적으로 array로 표현 가능하다.
    • root : 0
    • left child : 2*i + 1
    • right child : 2*i + 2
    • parent : (i-1)/2
    • level(depth) : h (0은 root)
    • level h에 가능한 node의 최대값 : 2^h
    • perfect binary tree에서 node의 수가 n일 때, depth는 log(n+1) - 1
• binary tree 순회
  • stack (recursive call)
    • in-order : left -> parent -> right
    • pre-order : parent -> left -> right
    • post-order : left -> parent -> right
  • queue