Задача №3557. Бинарное дерево (вставка, поиск, удаление)
Напишите программу, которая будет реализовывать действия в бинарном дереве поиска «вставить», «удалить» и «найти» (по значению). Программа должна обрабатывать запросы четырёх видов:
ADD n — если указанного числа еще нет в дереве, вставлять его и выводить слово «DONE», если уже есть — оставлять дерево как было и выводить слово «ALREADY».
DELETE n — если указанное число есть в дереве, удалять его и выводить слово «DONE», если нет — оставлять дерево как было и выводить слово «CANNOT». При удалении элемента, имеющего два сына, обязательно обменивать значение с максимальным элементом левого поддерева.
SEARCH — следует выводить слово «YES» (если значение найдено в дереве) или слово «NO» (если не найдено). Дерево при этом не меняется.
PRINTTREE — выводить все дерево, обязательно используя алгоритм, указанный в формате вывода результатов.
В каждой строке входных данных записан один из запросов ADD n или DELETE n или SEARCH n или PRINTTREE. Гарантируется, что запросы PRINTTREE будут вызываться только в моменты, когда дерево не пустое. Общее количество запросов не превышает 1000, из них не более 20 запросов PRINTTREE.
Для каждого запроса выводите ответ на него. Для запросов ADD, DELETE и SEARCH — соответствующее слово в отдельной строке. На запрос PRINTTREE надо выводить дерево, обязательно согласно такому алгоритму:
template<class T> void print_tree(Node<T> *p, int level)
{
if(p==NULL)
return;
print_tree(p->left, level+1);
for(int i=0; i<level; i++)
cout << ".";
cout << p->data << endl;
print_tree(p->right, level+1);
}
(Изначальный вызов этой функции — print_tree(root,0).)
ADD 2 ADD 7 ADD 5 PRINTTREE ADD 5 DELETE 3 ADD 0 PRINTTREE DELETE 7 PRINTTREE
DONE DONE DONE 2 ..5 .7 ALREADY CANNOT DONE .0 2 ..5 .7 DONE .0 2 .5