6. 이번에는 중위 순회 함수 inorder()를 작성하겠습니다. BST에서 중위 순회는 꽤 중요한 의미가 있습니다. 이에 대해서는 나중에 순회 결과를 보면서 다시 언급하겠습니다.
public:
void inorder()
{
inorder_impl(root);
}
private:
void inorder_impl(node* start)
{
if (!start)
return;
inorder_impl(start->left); // 왼쪽 서브 트리 방문
std::cout << start->data << " "; // 현재 노드 출력
inorder_impl(start->right); // 오른쪽 서브 트리 방문
}
7. 이번에는 후손 노드를 찾는 함수를 작성합니다.
public:
node* successor(node* start)
{
auto current = start->right;
while (current && current->left)
current = current->left;
return current;
}
위 코드 구현은 앞서 ‘BST에서 원소 삭제하기’ 부분에서 자세히 설명했습니다.