그림 14-6은 데이터 5의 삽입이 끝난 이진 트리의 모습입니다.

그림 14-6 insert() 메서드 알고리즘 ④

지금까지 알아본 알고리즘을 코드로 작성해 보겠습니다.

코드 14-2 bst/BST.py ②(insert() 메서드)

    def insert(self, data):
        # 삽입할 노드 생성 및 데이터 설정
        new_node = TreeNode()
        new_node.data = data

        cur = self.root
        # 루트 노드가 없을 때
        if cur = = None:
            self.root = new_node
            return

        # 삽입할 노드의 위치를 찾아 삽입
        while True:
            #parent는 현재 순회 중인 노드의 부모 노드를 가리킴
            parent = cur
            # 삽입할 데이터가 현재 노드 데이터보다 작을 때
            if data < cur.data:
                cur = cur.left
                # 왼쪽 서브 트리가 None이면 새 노드를 위치시킨다
                if not cur:
                    parent.left = new_node
                    return
            # 삽입할 데이터가 현재 노드 데이터보다 클 때
            else:
                cur = cur.right
                # 오른쪽 서브 트리가 None이면 새 노드를 위치시킨다
                if not cur:
                    parent.right = new_node
                    return

알고리즘을 살펴보았으므로 코드에 대한 설명은 주석만으로 충분할 것입니다. 그림과 함께 비교해 보세요.