🤍
트리 구조
1) 직접 클래스를 구현하기
2) 배열로 표현하기
: 완전 이진 트리는 왼쪽부터 데이터가 쌓이므로 이를 순서대로 배열에 쌓으면서 표현하는 것. (BFS 순으로 배열에 넣는다)
- 완전 이진 트리(단, 각 레벨에 노드가 꽉 차있다고 가정할 때)
: 레벨이 k이, 각 레벨에 최대로 들어갈 수 있는 노드의 개수는 2^k개.
즉, 높이가 h일 때 최대 노드의 개수(N)는 2^(h+1) - 1 개이다. *트리의 높이는 레벨 0(루트 노드)부터 센다.
N = 2^(h+1) - 1 일 때, h = log₂(N=1) - 1 완전 이진트리 노드의 경우에 이렇고,
이진 트리의 높이는 최대 O(log(N))이다.
이진 트리 구현
# 트리 구현
from binarytree.structures import TreeNode
def make_tree_by(lst, idx):
parent = None
if idx < len(lst):
value = lst[idx] # 부모노드의 인덱스 값 전달
if value is None:
return
# 부모 노드가 None이 아니라면.
parent = TreeNode(value)
parent.left = make_tree_by(lst, 2 * idx + 1) # 왼쪽에 트리노드를 만들어 붙임.
parent.left = make_tree_by(lst, 2 * idx + 2) # 오른쪽에 트리노드를 만들어 붙임.
return parent
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right# 이진트리의 최대 깊이 구하기
from collections import deque
from binarytree.prac import make_tree_by
def test_max_depth(lst):
root = make_tree_by(lst, 0) # 리스트를 트리로.
if not root: # 루트가 없으면 0 반환.
return 0
q = deque([root]) # 루트가 있으면 queue에 넣는다.
depth = 0
while q:
depth += 1 # 레벨 개수
for _ in range(len(q)):
cur = q.popleft()
if cur.left: # 왼쪽 노드가 있다면.
q.append(cur.left) # 레벨의 노드들을 넣어줌
if cur.right: # 오른쪽 노드가 있다면.
q.append(cur.right)
return depth
이진 트리 반전시키기
from binarytree.prac import make_tree_by, make_lst_by
def test_invert_btree(lst):
if not lst:
return []
def invert(parent): # 반전시키기.
if parent:
parent.left, parent.right = invert(parent.right), invert(parent.left)
return parent
root = make_tree_by(lst, 0)
return make_lst_by(invert(root))
'''
테스트케이스
assert test_invert_btree(lst=[]) == []
assert test_invert_btree(lst=[2]) == [2]
assert test_invert_btree(lst=[2, 1, 3, 5, 6, 2, 3]) == [2, 3, 1, 3, 2, 6, 5]
assert test_invert_btree(lst=[4, 2, 7, 1, 3, 6, 9]) == [4, 7, 2, 9, 6, 3, 1]
'''
이진 탐색 트리
Input: root = [8, 3, 10, 1, 6, 14, None, None, 4, 6, 13, None]