마지막으로 부모의 왼쪽 자식이 현재 노드라면 루트를 만나든가 부모의 오른쪽 자식이 현재 노드가 될 때까지 계속 부모를 타고 올라갑니다. 부모의 오른쪽 자식이 현재 노드란 의미는 부모 노드가 현재 노드의 이전 노드임을 의미합니다.

next()도 prev() 메서드와 유사합니다. 다만 방향이 반대일 뿐이지요. 시간을 내어 그림 8-7과 같이 꼭 그려 보기 바랍니다.

코드 8-9

    bst = BST()

    bst.insert(6)
    bst.insert(3)
    bst.insert(2)
    bst.insert(4)
    bst.insert(5)
    bst.insert(8)
    bst.insert(10)
    bst.insert(9)
    bst.insert(11)

    f = lambda x: print(x.key, end=' ')
    bst.inorder_traverse(bst.get_root(), f)

코드 8-9는 예제 코드의 일부를 가져온 것입니다. 이진 탐색 트리는 그림 8-3이 됩니다. 이 트리에 대해 중위 순회를 실행하면 다음 결과가 출력됩니다.

2  3  4  5  6  8  9  10  11