이진 트리

이진 트리의 특성

• 한 노드는 최대 두 개의 가지
• 왼쪽 서브트리와 오른쪽 서브트리 구별
• 0개의 노드를 가질 수 있음

이진 트리의 정의

• 공백이거나 루트와 두 개의 분리된 이진 트리로 구성 된 노드의 유한 집합

이진 트리와 일반 트리의 차이점

• 공백 이진 트리 존재
• 자식의 순서 구별
  • 서로 다른 두 이진 트리

편향 이진 트리와 완전 이진 트리

이진 트리의 성질

• 최대 노드의 수
  • 레벨 i에서의 최대 노드 수 : 2^i-1 (i >= 1)
  • 깊이가 k인 이진 트리가 가질 수 있는 최대 노드 수 : 2^k - 1 (k >= 1)
• 리프 노드 수와 차수가 2인 노드 수와의 관계
  • n₀ = n₂ + 1 (n : 리프 노드 수, n₂ : 차수가 2인 노드 수)
  • n₁ : 차수 1인 노드 수, n : 총 노드 수, B : 총 가지 수
  • n = n + n₁ + n₂
  • 루트를 제외한 모든 노드들은 들어오는 가지가 하나씩 있으므로 n = B + 1
  • 모든 가지들은 차수가 2 또는 1인 노드에서 뻗어 나오므로 B = n₁ + 2n₂

포화 이진 트리 (full binary tree)

• 깊이가 k이고, 노드 수가 2^k - 1 (k >= 0)인 이진 트리
• 노드 번호 1, ... , 2^k - 1 까지 순차적 부여 가능

완전 이진 트리 (Complete binary tree)

• 깊이가 k이고 노드 수가 n인 이진 트리의 각 노드들이 깊이가 k인 포화 이진 트리에서 1부터 n까지 번호를 붙인 노드와 1대 1로 일치
• n개 노드를 갖는 완전 이진 트리의 높이 :⌈log₂(n+1)⌉

이진 트리 배열 표현

• 1차원 배열에 노드를 저장
• n개의 노드를 가진 완전 이진 트리가 순차적으로 표현되고 인덱스가 1 <= i <= n 일 때
  1. parent(i) : ⌊i / 2⌋                       if i ≠ 1
  2. leftChild(i) : 2i                          if 2i ≤ n
                    왼쪽 자식 없음          if 2i > n
  3. rightChild(i) : 2i + 1                   if 2i + 1 ≤ n
                    오른쪽 자식 없음        if 2i + 1 > n
• 완전 이진 트리 : 낭비 되는 공간 없음
• 편향 트리 : 공간 낭비 (최악의 경우, 깊이 k 편향 트리는 2^k - 1 중 k개만 사용

이진 트리 연결 표현

• 노드 표현

leftChild

data

rightChild

• 부모 알기 어려움

트리 순회 (tree traversal)

• 트리에 있는 모든 노드를 한 번씩만 방문
• 순회 방법 : LVR, LRV, VLR, VRL, RVL, RLV (L : 왼쪽 이동, V : 노드 방문, R : 오른쪽 이동)
• 왼쪽을 오른쪽보다 먼저 방문 (LR)
  • LVR : 중위 (inorder) 순회
  • VLR : 전위 (preorder) 순회
  • LRV : 후위 (postorder) 순회

class TreeNode:

    def __init__(self, data, leftChild=None, rightChild=None):
        self.data = data
        self.leftChild = leftChild
        self.rightChild = rightChild

    def hasLeftChild(self):
        return self.leftChild

    def hasRightChild(self):
        return self.rightChild

class Tree:

    def __init__(self):
        self.root = None

    def Put(self, data):
        if self.root:
            self._put(data, self.root)
        else:
            self.root = TreeNode(data)

    def _put(self, data, currentNode):
        if data < currentNode.data:
            if currentNode.hasLeftChild():
                self._put(data, currentNode.leftChild)
            else:
                currentNode.leftChild = TreeNode(data)
        else:
            if currentNode.hasRightChild():
                self._put(data, currentNode.rightChild)
            else:
                currentNode.rightChild = TreeNode(data)

    # 중위 순회
    def Inorder(self, currentNode):
        if currentNode is not None:
            self.Inorder(currentNode.leftChild)
            self.Visit(currentNode)
            self.Inorder(currentNode.rightChild)

    # 전위 순회
    def Preorder(self, currentNode):
        if currentNode is not None:
            self.Visit(currentNode)
            self.Preorder(currentNode.leftChild)
            self.Preorder(currentNode.rightChild)

    # 후위 순회
    def Postorder(self, currentNode):
        if currentNode is not None:
            self.Postorder(currentNode.leftChild)
            self.Postorder(currentNode.rightChild)
            self.Visit(currentNode)

    # 출력
    def Visit(self, currentNode):
        print(currentNode.data)