이진 트리 Binary Tree

우선순위 큐에서 이진 트리 (Binary Tree) 를 이용한 힙 자료구조에 대해 다루었다.

 

이전에 배웠던 이진 트리를 정리해보며 복습하는 시간을 가졌다.

 

이진 트리는 Tree 자료구조의 한 종류로 자식 (child) 를 최대 2개만 가지는 (left, right) 트리 자료구조이다.

 

Tree 자료구조는 비선형적 자료 구조 이며 계층 구조를 표현 할 수 있다.

 

이 계층 구조의 특성으로 인해 우선순위 큐에서 활용 될 수 있다.

출처 : 위키백과

 

• 구현 

파이썬으로 구현한 이진 트리

from collections import deque

class Node():

    def __init__(self, value=0, left=None, right=None):

        self.value = value

        self.left = left

        self.right = right

class BinaryTree():

    def __init__(self):

        self.root = None

bt = BinaryTree()

bt.root = Node(value=1)

# 메서드 활용

bt = BinaryTree()

bt.root = Node(value=1)

bt.root.left = Node(value=2)

bt.root.right = Node(value=3)

bt.root.left.left = Node(value=4)

bt.root.left.right = Node(value=5)

bt.root.right.right = Node(value=6)

bt.root.right.left = Node(value=7)

 

여기서 이진 트리에도 다양한 종류가 있다.

 

 

• 완전 이진 트리

완전 이진 트리 출처 : https://velog.io/@seochan99/

완전 이진트리는 높이가 h 일 때 레벨 h-1까지는 Full BT이고, 레벨 h에서는 왼쪽부터 노드가 순서대로 채워진 이진트리이다.

노드의 개수 :  2^(h-1)-1 <= n <= 2^h-1

 

쉽게 말해 왼쪽부터 빈칸없이 채워져있는 이진트리를 완전 이진 트리라고 부른다..

 

 

• 정리

1. 이진 트리는 트리의 한 종류이며 child 노드를 2개 이하를 가지는 트리이다.

 

2. 이진 트리 중에서도 다양한 종류가 있다.

 

3. 완전 이진 트리는 왼쪽 부터 노드가 순서대로 채워진 이진트리이다.