5. 이진 트리 Binary Trees

학교 수업 '자료구조' 복습입니다.

        Binary Trees란?

• 이진 트리의 정의
  각 노드가 자식 노드를 최대 두 개까지만 가지는 트리.
  두 자식 노드는 각 각 왼쪽 자식, 오른쪽 자식이라고 부름.
  *왼쪽, 오른쪽이라고 위치를 명시하기 때문에, 같은 두 개의 자식을 가지고 있는 트리라도 일반적인 트리와 이진 트리는 서로 다름.

• 정 이진 트리 full binary tree : 각 노드의 자식 노드 수가 2 또는 0인 트리
• 완전 이진 트리 complete binary tree : 
  가장 깊은 레벨을 제외한 모든 레벨이 가득 차 있음
  마지막 레벨의 노드들은 가능한 왼쪽에 존재

• 포화 이진 트리 perfect binary tree :
  모든 단말 노드의 레벨이 같음
  모든 내부 노드의 자식의 수가 2임
  Q1) 포화 이진 트리는 정 이진 트리인가? True
  Q2) 포화 이진 트리는 완전 이진 트리인가? True
  Q3) 정 이진 트리이면서 완전 이진 트리이면 포화 이진 트리인가? False

perfect binary tree

---

        Full Binary Tree Theorem ( 정 이진 트리 정리)

• 정의 : 비어있지 않은 정 이진 트리의 리프 노드의 수는 내부 노드의 수보다 한 개 많다.
  
  

        Full Binary Tree Corollary ( 정 이진 트리 정리의 따름 정리)

• 정의 : 비어있지 않은 이진 트리에서 null pointer의 수는 노드 수보다 1개 많다.

---

        Binary Tree Traversals

• 순회 Traversals : 정해진 순서대로 노드를 방문하는 과정
• 열거 enumeration : 트리의 각 노드를 정확히 한번씩 나열하는 순회 방법
• 순회는 왜 하는가?
  구현을 했을 때, 저장된 자료 전체를 보지 못하고 노드 하나씩만 보게 된다.
  그렇다면 전체를 보고 싶다면 어떻게 하는게 좋을까?
• 밑의 그림을 선으로 이어서 왼쪽, 가운데, 오른쪽으로 점을 찍어서 연결하면 왼쪽은 전위, 가운데는 중위, 오른쪽은 후위순회이다.

위 트리를 어떻게 순회할까?

        전위순회 preorder traversal

• 정의 : 노드를 방문하고, 자식들을 순회한다.
• 재귀적으로 실행된다고 생각하면 됨.
• A-B-D-E-G-C-F-H-I 의 순서로 방문한다.

void preorder(BinNode rt) {
    if(rt == null) return; // Empty subtree - do nothing
    visit(rt); // Process root node
    preorder(rt.left()); // Process all nodes in left
    preorder(rt.right()); // Process all nodes in right
}

        후위순회 postorder traversal

• 정의 : 자식들을 방문하고, 노드를 방문한다.
• D-G-E-B-H-I-F-C-A

void postorder(BinNode rt) {
    if(rt == null) return; // Empty subtree - do nothing
    preorder(rt.left()); // Process all nodes in left
    preorder(rt.right()); // Process all nodes in right
    visit(rt); // Process root node
}

        중위순회 inorder traversal

• 정의 : 왼쪽 subtree를 방문하고, 노드를 방문하고, 오른쪽 subtree를 방문한다.
• D-B-E-G-A-C-H-F-I (왼쪽 자식이 있으면 그 노드를 먼저 방문하는 것, 그림 꼭 숙지)

void inorder(BinNode rt) {
    if(rt == null) return; // Empty subtree - do nothing
    preorder(rt.left()); // Process all nodes in left
    visit(rt); // Process root node
    preorder(rt.right()); // Process all nodes in right
}