이진 트리

정의

이진 트리는 각 노드의 자식노드가 최대 2개인 트리를 의미한다.

요소

• 데이터
• 좌측 자식 노드 포인터
• 우측 자식 노드 포인터

property

(*루트 노드 레벨 0 기준)

• 최대 노드 개수
  • 이진 트리의 'l' 레벨에 있는 최대 노드 수 는 2^l
  • 이진 트리의 'l' 레벨을 갖는 트리의 최대 노드 수는 2^(h+1) - 1
• 최대 깊이
  • N개의 노드가 있는 이진 트리의 최소 레벨는 log2(n+1) - 1

순회

• DFS
  • 전위 순회(preorder)
    • root -> left -> right
    • 순서
      1. 루트 노드를 방문한다.
      2. 왼쪽 서브 트리를 전위 순회한다.
      3. 오른쪽 서브 트리를 전위 순회한다.
    • (1 - 2 - 4 - 5 - 3 - 6 - 7)
  • 중위 순회(inorder)
    • left -> root -> right
    • 순서
      1. 왼쪽 서브트리를 중위 순회한다.
      2. 루트 노드를 방문한다.
      3. 오른쪽 서브 트리를 중위 순회한다.
    • (4 - 2 - 5 - 1 - 6 - 3 - 7)
  • 후위 순회(postorder)
    • left -> right -> root
    • 순서
      • 왼쪽 서브트리를 후위 순회한다.
      • 오른쪽 서브트리를 후위 순회한다.
      • 루트 노드를 방문한다.
    • (4 - 5 - 2 - 6 - 7 - 3 - 1)
• BFS
  • 층별 순회(level order)
    • 같은 레벨의 노드들을 전부 탐색한 후 다음 레벨의 노드들을 탐색하는 방식
    • (1 - 2 - 3 - 4 - 5 - 6 - 7)

참고자료

geeksforgeeks-binary tree