2.1 이진 트리

두 개 이하의 자식 노드를 가지는 트리를 이진 트리라고 한다.

2.1.1 이진트리( 연결 리스트 )

# 연결리스트로 구현한 이진트리
class BinaryTree():
    class Node():
        def __init__(self, value):
            self.left = None
            self.right = None
            self.value = value

        def preorder(self):
            print(self.value)
            if not (self.left is None):
                self.left.preorder()
            if not (self.right is None):
                self.right.preorder()
        def inorder(self):
            if not (self.left is None):
                self.left.preorder()
            print(self.value)
            if not (self.right is None):
                self.right.preorder()

        def postorder(self):
            if not (self.left is None):
                self.left.preorder()
            if not (self.right is None):
                self.right.preorder()
            print(self.value)
        
        # 스택으로 구현한 전위 순회
        def preorder_stack(self):
            stack = []
            stack.append(self)
            while stack:
                node = stack.pop()
                print(node.value)
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)

    def __init__(self, value):
        self.root = self.Node(value)

2.1.2 이진트리 ( 리스트 )

# 리스트로 구현한 이진트리
BT_list = [0, 1, 2, 3, 4]
# left: 2n+1
# right: 2n+2 
# parent: (n-1)//2
idx = 0

def left(idx):
    return 2*idx + 1
def right(idx):
    return 2*idx + 2
def parent(idx):
    return (idx-1)//2

def preorder(idx):
    print(BT_list[idx])
    if left(idx) < len(BT_list):
        preorder(left(idx))
    if right(idx) < len(BT_list):
        preorder(right(idx))

2.2 힙

class Heap:
    class Node:
        def __init__(self, value):
            self.left = None
            self.right = None
            self.value = value

        def __str__(self):
            return str(self.value)

    def __init__(self):
        self.root = None

    def levelorder(self):
        if not self.root:
            print("Heap is empty.")
            return
        queue = [self.root]
        while queue:
            curr = queue.pop(0)
            print(curr.value, end=" ")
            if curr.left:
                queue.append(curr.left)
            if curr.right:
                queue.append(curr.right)
        print()

    def _empty_node(self):
        queue = [[self.root, [self.root]]]
        while queue:
            curr, path = queue.pop(0)
            if curr.left is None:
                return [curr, "l", path]
            queue.append([curr.left, path+[curr.left]])
            if curr.right is None:
                return [curr, "r", path]
            queue.append([curr.right, path+[curr.right]])

    def _last_node(self): # 레벨 순회를 하다가 None을 만나면 직전 노드의 경로를 반환한다.
        queue = [[self.root, []]]
        while queue:
            curr, path = queue.pop(0)
            if curr.left:
                queue.append([curr.left, path+[curr]])
                lr = "l"
            if curr.right:
                queue.append([curr.right, path+[curr]])
                lr = "r"
        return [path, lr]

    def append(self, value): # 가장 처음 만나는 빈 칸에 노드 삽입
        if self.root is None:
            self.root = self.Node(value)
            return
        node, lr, path = self._empty_node()
        new_node = self.Node(value)
        if lr == "l":
            node.left = new_node
        elif lr == "r":
            node.right = new_node
        self._heapify_up(new_node, path)

    def _heapify_up(self, node, path): # 말단에서 올리는 경우
        while path:
            parent = path.pop()
            if parent.value > node.value:
                parent.value, node.value = node.value, parent.value
                node = parent
            else:
                break

    def _heapify_down(self, node): # 루트에서 내리는 경우.
        while node:
            smallest = node
            if node.left and node.left.value < smallest.value:
                smallest = node.left
            if node.right and node.right.value < smallest.value:
                smallest = node.right
            if smallest == node:
                break
            # Swap values with the smallest child
            node.value, smallest.value = smallest.value, node.value
            node = smallest

    def pop(self):
        if self.root: value = self.root.value
        else: return None
        path, lr = self._last_node()
        parent = path.pop()
        if lr=="l":
            self.root.value, parent.left = parent.left.value, None
        elif lr=="r":
            self.root.value, parent.right = parent.right.value, None
        self._heapify_down(self.root)
        return value