5. 이번에는 insert() 함수를 작성하겠습니다. 이 함수는 find() 함수 구현처럼 재귀적으로 하위 노드로 이동하면서 삽입할 위치의 부모 노드를 찾습니다. 그리고 이 노드의 자식 노드로서 새 원소를 추가합니다.
public:
void insert(int value)
{
if (!root)
root = new node {value, NULL, NULL};
else
insert_impl(root, value);
}
private:
void insert_impl(node* current, int value)
{
if (value < current->data)
{
if (!current->left)
current->left = new node {value, NULL, NULL};
else
insert_impl(current->left, value);
}
else
{
if (!current->right)
current->right = new node {value, NULL, NULL};
else
insert_impl(current->right, value);
}
}
위 코드를 보면 왼쪽 또는 오른쪽 서브 트리 중에서 어디에 값을 삽입해야 하는지를 확인합니다. 만약 값을 삽입해야 할 쪽이 비어 있으면 새로운 노드를 추가합니다. 그렇지 않고 이미 다른 노드가 있다면 삽입 함수를 재귀적으로 호출합니다.