Напишите программу, которая формирует бинарное дерево поиска, выводит построенное дерево на экран. Данные для построения дерева могут вводиться с клавиатуры, из файла или генерироваться с помощью генератора случайных чисел. Выбор способа ввода данных выполняется во время работы программы. В построенном дереве необходимо подсчитать число элементов, больше заданного, которое вводится с клавиатуры. Также реализовать возможность удаления произвольного элемента сформированного дерева. Для реализации АТД «Дерево» используйте динамическое распределение памяти. Перед завершением работы программы освободить занимаемую динамическую память. Для этого используйте поэлементное удаление элементов динамической структуры данных.
- Алгоритм решения задачи
- Спросить пользователя о способе заполнения АТД «бинарное дерево»;
- Инициализировать объект «бинарное дерево» с фиктивным элементом и пустыми ветвями;
- Если это выбор «Ввод данных с клавиатуры», то перейти в функцию, считывающую данные из стандартного потока;
- Если это выбор «Считывание из файла», то перейти в функцию, открывающую файл по переданной строке-названию файла и изъять данные для заполнения АДТ «бинарное дерево»;
- Если это выбор «Заполнение рандомными элементами», то перейти в функцию, принимающую желаемое количество элементов и заполнить дерево случайно сгенерированными элементами;
- После заполнения по выбору, вывести с помощью метода заполненное бинарное дерево;
- Выяснить у пользователя значение элемента, с которым будет решаться поставленная задача по нахождению количества элементов, больших заданного;
- Выполнить поставленную задачу с помощью метода, подсчитывающий количество элементов, больших заданного элемента;
- Вывести вычисленное число;
- Запросить у пользователя значение, которое следует удалить из дерева;
- Освободить динамически выделенную память поэлементно начиная с самой левой ветки, поочерёдно вызывая деструкторы сначала для неё, потом для правых ветвей до тех пор, пока все ветви не будут освобождены вместе с выделенными в объекте кучами под указатель на целочисленное значение;
- Программная реализация Последовательность действий при программной реализации:
- Задать класс с необходимыми полями для корня дерева;
- Реализовать алгоритм решения поставленной задачи;
- Реализовать основные функции работы с бинарным деревом, реализованным на указателях (Конструктор – инициализация, Деструктор – уничтожение дерева, AddNode(), Delete(), Del());
- Реализовать в главной функции корректное считывание данных в соответствии с выбором и вывод данных в консоль подсчитанного количества больших чем заданный элементов в дереве, а также протестировать метод удаления заданного элемента;