6.2 이진트리

main.py

"""
이진 트리를 구현하여라.
"""


class Node:

    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

    def __repr__(self):
        return str(self.data)


class BinarySearchTree:

    def __init__(self):
        self.__root = None

    def create_bst(self, nodes_list):

        nodes = [None if item is None else Node(item)
                 for item in nodes_list]

        for index in range(1, len(nodes)):
            node = nodes[index]

            if not node is not None:
                parent_index = (index - 1) // 2
                parent = nodes[parent_index]
                if parent is None:
                    raise ValueError(

                        f'Missing parent node at index {parent_index},'
                        f' Node({node.data}'
                    )
                if index % 2 == True:
                    parent.left = node
                else:
                    parent.right = node

    def insert(self, data, method='iterative'):
        if method in 'recursion':
            self.__root = self.insert_rec(self.__root, data)
        else:
            self._insert_iter(data)

    def inorder_traverse(self):
        result = []

        self._inorder_rec(self.__root, result)
        return result

    def _inorder_rec(self, node, result):
        if not node:
            return

        self._inorder_rec(node.left, result)
        result.append(node.data)
        self._inorder_rec(node.right, result)

    def inorder_iter(self):
        result = []
        stack = []

        node = self.__root

        while node or stack:
            while node:
                stack.append(node)
                node = node.left
            if stack:
                node = stack.pop()
                result.append(node)
                node = node.right
        return result

    def _insert_rec(self, node, data):
        if not node:
            node = Node(data)
        else:
            if node.data > data:
                node.left = self._insert_rec(node.left, data)
            else:
                node.right = self._insert_rec(node.right, data)
        return node

    def _insert_iter(self, data):
        if not self.__root:
            self.__root = Node(data)
            return

        new_node = Node(data)

        curr = self.__root
        parent = None

        while curr is not None:
            parent = curr

            if curr.data > data:
                curr = curr.left
            else:
                curr = curr.right
        if parent.data > data:
            parent.left = new_node
        else:
            parent.right = new_node

    def find(self, data):
        return self._find_data(self.__root, data)

    def _find_data(self, node, data):
        if not node:
            return False
        elif node.data == data:
            return True
        elif node.data > data:
            return self._find_data(node.left, data)
        else:
            return self._find_data(node.right, data)

    def find_min_node(self, node):
        while node.left:
            node = node.left
        return node

    def delete(self, data):
        self._delete_data(self.__root, data)

    def _delete_data(self, node, data):
        parent = None

        curr = node

        while curr and curr.data != data:
            parent = curr

            if curr.data > data:
                curr = curr.left
            else:
                curr = curr.right

        if curr is None:
            return node

        # 자식 노드가 없는 경우
        if not curr.left and not curr.right:
            if curr != node:
                if parent.left == curr:
                    parent.left = None
                else:
                    parent.right = None
            else:
                node = None
        # 오른쪽 왼쪽 모두 자식이 있는 경우
        elif curr.left and curr.right:
            # 지우려는 노드의 오른쪽 하위 트리에서 가장 작은 노드 찾기
            min_node = self.find_min_node(curr.right)

            min_data = min_node.data

            # 오른쪽 하위 트리에서 가장 작은 노드는
            # 항상 잎새 (leaf) 노드이므로 그냥 삭제 진행한다.
            self._delete_data(node, min_data)
            curr.data = min_data
        # 오른쪽 혹은 왼쪽 노드가 하나만 있는 경우
        else:
            if curr.left:
                child = curr.left
            else:
                child = curr.right

            if curr != node:
                if curr == parent.left:
                    parent.left = child
                else:
                    parent.right = child
            else:
                node = child
        return node


if __name__ == '__main__':
    bst = BinarySearchTree()

    bst.insert(20)
    bst.insert(25)
    bst.insert(14)
    bst.insert(30)
    bst.insert(23)
    bst.insert(18)
    bst.insert(11)
    bst.insert(21)
    bst.insert(15)

    bst.delete(15)
    bst.delete(21)

    print(bst.inorder_traverse())