이진 트리

트리란?

순환구조를 갖지않는 루트가 하나인 그래프
나무를 거꾸로 둔 모습으로 계층형 비선형 자료구조

트리용어정리

Node: 트리에서 데이터를 저장하는 기본 요소
Root Node: 트리 맨 위에 있는 노드
Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
Parent Node: 어떤 노드의 상위 레벨에 연결된 노드
Child Node: 어떤 노드의 하위 레벨에 연결된 노드
Leaf Node(Terminal Node): Child Node가 하나도 없는 노드
Sibling: 동일한 Parent Node를 가진 노드
Depth: 트리에서 Node가 가질 수 있는 최대 Level
height 트리의 높이로 depth와 동일

이진트리란?

각 노드가 최대 두 개의 자식을 가진다.
무조건 0~2개를 가져야 한다는 뜻이다.

  o
o o o 이런 구조면 이진트리가 아니다

이진트리탐색의 시간복잡도는 O(log(N))으로 일반적인 선형자료구조 스택 큐 배열은 시간복잡도가 O(N)으로 차이가 크다.

따라서 선형구조로 탐색보다는 비선형구조로 짜서 탐색을 하는것이 효율적이다.

파이썬으로 구현하기

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def make_tree_by(lst, idx):
    parent = None
    if idx < len(lst): # 재귀함수로 인덱스를 2* 부모 +1 해주니깐 리프노드에선 실행하지 않도록 걸러줌
        value = lst[idx]
        if value is None:
            return

        parent = TreeNode(value)
        #배열로 만들때 [0,1,2,null,null,5,6]
        #  0
        #1   2
        #   5 6
        parent.left = make_tree_by(lst, 2 * idx + 1) #왼쪽은 부모인덱스 * 2 + 1
        parent.left = make_tree_by(lst, 2 * idx + 2) #왼쪽은 부모인덱스 * 2 + 1

    return parent

완전 이진트리

이진트리에서 제일 아래 왼쪽부터 차근차근 채워야한다.

  o      Level 0
o   o    Level 1
 o o     Level 2  # -> 이진 트리 O 완전 이진 트리 X

   o      Level 0
 o   o    Level 1
o o o     Level 2  # -> 이진 트리 O 완전 이진 트리 O

파이썬으로 구현하기

from collections import deque

class TreeNode:
 def __init__(self, val, left=None, right=None):
     self.val = val
     self.left = left
     self.right = right

def sorted_array_to_bst(lst):
 if not lst:
     return None

 mid = len(lst) // 2

 node = TreeNode(lst[mid])
 node.left = sorted_array_to_bst(lst[:mid]) #0의 왼쪽 노드
 node.right = sorted_array_to_bst(lst[mid + 1:]) #0의 오른쪽노드
 return node


def make_lst_by_bst(root, limit):
 if not root:
     return []

 lst = []
 q = deque([root])

 while q:
     if len(lst) > limit: #none을 추가했기떄문에 limit로 제한
         break

     node = q.popleft()
     if node:
         lst.append(node.val)
         q.append(node.left)
         q.append(node.right)
     else:
         lst.append(None) #배열에 none추가를 위한 bfs의 변형

 return lst