더북(TheBook)

8.4 이진 탐색 트리의 구현

먼저 몇 가지 필요한 편의 함수와 전위·중위 순회 메서드를 만들어 둡시다.

코드 8-3

class BST:
    def __init__(self):
        self.root = None

    def get_root(self):
        return self.root

    def preorder_traverse(self, cur, func):
        if not cur:
            return

        func(cur)
        self.preorder_traverse(cur.left, func)
        self.preorder_traverse(cur.right, func)

    # key가 정렬된 상태로 출력
    def inorder_traverse(self, cur, func):
        if not cur:
            return

        self.inorder_traverse(cur.left, func)
        func(cur)
        self.inorder_traverse(cur.right, func)

    # 편의 함수
    # cur의 왼쪽 자식을 left로 만듭니다.
    def __make_left(self, cur, left):
        cur.left = left
        if left:
            left.parent = cur

    # 편의 함수
    # cur의 오른쪽 자식을 right로 만듭니다.
    def __make_right(self, cur, right):
        cur.right = right
        if right:
            right.parent = cur

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.