Напишите программу, которая будет реализовывать действия в бинарном дереве поиска «вставить», «удалить» и «найти» (по значению). Программа должна обрабатывать запросы четырёх видов:
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 void print_tree(Node *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).)
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
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
|