Краткая постановка задания

Необходимо написать модуль, содержащий решения $16$ задач для работы с бинарными деревьями, и программу, демонстрирующую работу этого модуля. Программа должна быть выполнена либо в качестве консольного приложения (тогда обязателен командно-текстовый интерфейс), либо иметь графический интерфейс пользователя.

При необходимости можно использовать вспомогательные функции. В разработанном модуле не должны применяться интерфейсные функции (исключение возможно только для функций вывода дерева).

Комментарий от разработчиков программы

Мы частично разработали решение данной задачи для всех студентов, изучающих данную тему. Программа реализована в среде MS Visual Studio на языке программирования C++ (консольный проект).

В коде учтены все пожелания и требования к данной задаче, выдвигаемые составителями. Соблюдены названия переменных, порядок выполнения операторов и пр.нюансы.

Закодированы следующие операции над бинарным деревом поиска:

Смысл операцииНазвание функции в коде
1Создание бинарного дерева поиска. Формируется бинарное дерево поиска, состоящее из $n$ элементов ($n$ вводится с клавиатуры).

void MakeBinaryTree(bintree** proot, const int pn)

2Добавление узла в бинарное дерево поиска. Пользователь вводит число, необходимо добавить его в дерево, руководствуясь принципами построения бинарного дерева поиска.void Insert(bintree** proot, const int pinf)
3Вывод бинарного дерева. Элементы дерева необходимо вывести в порядке возрастания ключей узлов. Реализован симметричный обход дерева (ЛКП). Способ вывода простой, а не «красивый».void LKP(bintree* proot)
4Поиск образца в бинарном дереве.bool SearchNodeByKey(bintree* proot, const int pkey)
5Подсчет количества узлов дерева. Использовать для решения подзадачи рекурсивный алгоритм.int GetCountNodes(bintree* proot)
6
Подсчет числа листьев дерева. Использовать для решения подзадачи рекурсивный алгоритм.int GetCountLeaves(bintree* proot)
7
Генерация случайного целого числа на заданном отрезке.int irand(const int pa, const int pb)
8
Ввод с клавиатуры значения ключа добавляемого узла.int InputIntValue(void)
9
Создание узла бинарного дерева поиска с заданным ключом.bintree* CreateNode(const int pinf)
10
Проверка добавляемого узла на дубликатность.bool IsUniqueValueInsert(bintree* proot, const int pinf)
11
Вывод бинарного дерева. Реализован прямой обход дерева (КЛП).void KLP(bintree* proot)
12
Вывод бинарного дерева. Реализован обратный обход дерева (ЛПК).void LPK(bintree* proot)
13
Удаление всех узлов из бинарного дерева (полная очистка дерева).void RemoveBinaryTree(bintree** proot)
14
Главная функция программы (точка входа).int main(void)

Операции, имеющие желтоватый фон, — вспомогательные операции, которые так или иначе были использованы при кодировании основных операций обработки бинарного дерева поиска.

Стоимость доработки программы

ОперацияКонсольный форматВизуальный формат
1.Создание бинарного дерева поиска из $n$ элементов.Бесплатно (см.реализацию ниже)$250$ рублей
2.Добавление узла в бинарное дерево поиска.Бесплатно (см.реализацию ниже)$250$ рублей
3.Вывод бинарного дерева в порядке возрастания ключей его элементов («красивый» формат).$400$ рублей$700$ рублей
4.Поиск образца в бинарном дереве поиска.Бесплатно (см.реализацию ниже)$250$ рублей
5.Подсчет количества узлов дерева.Бесплатно (см.реализацию ниже)$150$ рублей
6.Подсчет числа листьев дерева.Бесплатно (см.реализацию ниже)$150$ рублей
7.Расчет степени вершины, используя рекурсивный обход.$100$ рублей$250$ рублей
8.Расчет уровня вершины.$100$ рублей$250$ рублей
9.Расчет высоты дерева.$100$ рублей$250$ рублей
10.Поиск образца в бинарном дереве (любом дереве).$100$ рублей$250$ рублей
11.Удаление узла дерева с поддеревом.$100$ рублей$250$ рублей
12.Удаление всего дерева (с использованием п.11).$100$ рублей$250$ рублей
13.Удаление узла с перестройкой дерева.$250$ рублей$600$ рублей
14.Обход дерева в глубину (не рекурсивный). Требуется использовать стек, реализованный в предыдущей лабораторной работе.

$200$ рублей, если стек уже закодирован.

$700$ рублей, если стек не закодирован и его нужно кодировать.

$500$ рублей, если стек уже закодирован.

$1\ 200$ рублей, если стек не закодирован и его нужно кодировать.

15.Обход дерева в ширину (не рекурсивный). Требуется использовать очередь, реализованную в предыдущей лабораторной работе.

$200$ рублей, если очередь уже закодирована.

$700$ рублей, если очередь не закодирована и ее нужно кодировать.

$500$ рублей, если очередь уже закодирована.

$1\ 200$ рублей, если очередь не закодирована и ее нужно кодировать.

16.Балансировка дерева.$500$ рублей$900$ рублей

Данная работа предполагает написание программы на языке C++. При заказе нужных вам операций над бинарным деревом поиска вы получите качественно написанную и хорошо прокомментированную программу.

➡ Дополнительно заказав алгоритм решения задачи (мы крайне рекомендуем это сделать), получите аккуратно оформленный отчет-алгоритм, поясняющий все тонкости решения поставленной задачи.

Структура проекта

В результате частичного кодирования данной задачи получился проект, состоящий из $3$ файлов:

  • tree.h — пользовательские описания (типы данных и прототипы функций).
  • tree.cpp — модуль для работы с бинарным деревом поиска.
  • source.cpp — программа, демонстрирующая работу модуля tree.cpp.

Реализация задачи на языке С++

 

Результаты работы программы

Смысл операции и результат
1САФУ. Практикум на С++ (Латухина). Лабораторная работа №3 (бинарные деревья). Попытка получить общее количество узлов в дереве (изначально дерево пустое).Попытка получить общее количество узлов в дереве (изначально дерево пустое).
2САФУ. Практикум на С++ (Латухина). Лабораторная работа №3 (бинарные деревья). Добавление узла в дерево с ключом, равным 27.Добавление узла в дерево с ключом, равным $27$.
3САФУ. Практикум на С++ (Латухина). Лабораторная работа №3 (бинарные деревья). Добавляем последовательно узлы со значениями: 11, 45, 33, -5, 21. После этого печатаем узлы дерева на экран.Добавляем последовательно узлы со значениями: $11$, $45$, $33$, $-5$, $21$. После этого печатаем узлы дерева на экран.
4САФУ. Практикум на С++ (Латухина). Лабораторная работа №3 (бинарные деревья). Попытка получить общее количество листьев в дереве.Попытка получить общее количество листьев в дереве.
5САФУ. Практикум на С++ (Латухина). Лабораторная работа №3 (бинарные деревья). Создаем дерево, состоящее из 8 узлов.Создаем дерево, состоящее из $8$ узлов.
6САФУ. Практикум на С++ (Латухина). Лабораторная работа №3 (бинарные деревья). Печатаем узлы дерева на экран.Печатаем узлы дерева на экран.
7САФУ. Практикум на С++ (Латухина). Лабораторная работа №3 (бинарные деревья). Завершаем работу с программой.Завершаем работу с программой.

Варианты индивидуальных заданий их стоимость реализации

Задание для всех вариантов звучит так (или, возможно, немного изменено, так как могут быть разные издания учебного пособия):

За индивидуальную задачу при работе по БРС можно получить до 5 баллов. Для ее решения рекомендуется использовать подготовленный ранее программный модуль.

💡 ВАЖНО!

  • Задания обладают не одинаковой сложностью. Есть достаточно нетривиальные операции, требующие кодирования дополнительных функций.
  • Стоимость каждой операции обозначена в таблице ниже в самой правкой колонке «Стоимость».

ФормулировкаСтоимость
1.Определите, есть ли в данном бинарном дереве два одинаковых элемента (дерево не является бинарным деревом поиска).$350$ рублей
2.Выведите номера уровней данного бинарного дерева, на которых имеются листья.$300$ рублей
3.Выведите номера вершин, у которых количество потомков в леввом поддереве не равно количеству потомков в правом поддереве.$300$ рублей
4.Выведите номера вершин, для которых высота левого поддерева не равна высоте правого поддерева.$250$ рублей
5.Выведите номера вершин, у которых количество потомков в левом поддереве отличается от количества потомков в правом поддереве на $1$.

Бесплатно
(см. пример ниже)

6.Найдите высоту дерева $H$ и удалите из него (с перейстройкой) все вершины на уровне $\frac{H}{2}$.$500$ рублей
7.Найдите минимальный путь между двумя произвольными листьями.$250$ рублей
8.Найдите минимальный путь между двумя произвольными вершинами дерева.$250$ рублей
9.Найдите высоту дерева $H$ и удалите в нем все вершины (с перейстройкой) на глубине $\frac{H}{2}$, у которых высота левого поддерева равна высоте правого поддерева.$500$ рублей
10.Найдите путь максимальной длины и отразите дерево зеркально относительно этого пути.$400$ рублей
11.Найдите путь максимальной длины между двумя произвольными вершинами с разным числом потомков.$350$ рублей
12.Найдите путь максимальной длины между двумя произвольными вершинами разной высоты.$300$ рублей
13.Найдите пути минимальной длины между корнем и листьями.$300$ рублей
14.Определите, являются ли два дерева зеркальным отражением друг друга.$450$ рублей
15.Найдите среднюю по значению вершину в дереве (вершину, у которой значение ближе всего по модулю к среднему арифметическому значений всех вершин).$300$ рублей
16.Найдите вершины, у которых высоты поддеревьев равны, а количество потомков в правом и левом поддеревьях не равны.$250$ рублей
17.Найдите вершины, у которых высоты поддеревьев равны, а количество потомков в правом и левом поддеревьях не равны.$250$ рублей
18.Удалите все вершины, для которых количество потомков в левом поддереве отличается от количества вершин в правом поддереве на $2$ и более.$250$ рублей
19.Удалите все вершины, у которых высота левого поддерева отличается от высоты правого поддерева на $2$.$250$ рублей
20.Выясните, является ли дерево симметричным.$300$ рублей
21.Вычислите количество вершин, для которых высота левого поддерева равна высоте правого поддерева.$250$ рублей
22.Вычислите количество вершин, у которых равны или высоты поддеревьев, или количество потомков в правом и левом поддеревьях.$250$ рублей

Лабораторная работа $№3$ предполагает написание программы на языке C++. При заказе работы своего варианта вы получите качественно написанную и хорошо прокомментированную программу.

➡ Дополнительно заказав алгоритм решения вашей задачи (мы крайне рекомендуем это сделать), получите аккуратно оформленный отчет-алгоритм, поясняющий все тонкости решения поставленной задачи.

Образец выполнения (вариант №5)

Условие задания

Выведите номера вершин, у которых количество потомков в левом поддереве отличается от количества потомков в правом поддереве на $1$.

Алгоритм решения задачи

Прежде чем переходить непосредственно к кодированию данного задания, нужно провести его алгоритмизацию. Данный этап является обязательным и ни один профессиональный программист не опускает его в своей работе.

Предположим, что мы получили бинарное дерево поиска следующей конфигурации:

САФУ. Практикум на С++ (Латухина). Лабораторная работа №3 (бинарные деревья). Бинарное дерево поиска, состоящее из 12 вершин

Данное дерево состоит из $12$ узлов, образующих $4$ уровня, кстати, является почти сбалансированным (для решения данной задачи это не важно).

Очевидно, что придется просмотреть все узлы данного дерева. Для этого можно воспользоваться любым из вариантов обхода дерева (прямой, обратный, симметричный). Выбираем симметричный порядок обхода, чтобы при печати номеров вершин они шли по возрастанию.

Далее нужно вспомнить, что в нашем распоряжении (в разработанном ранее модуле для работы с двоичным деревом поиска) есть замечательная функция, подсчитывающая количество узлов в заданном дереве/поддереве:

➡ Благодаря данной функции мы достаточно просто решим поставленную задачу! Начинаем последовательно сканировать в симметричном порядке все вершины дерева и для каждого узла подсчитывать количество потомков из левого и правого поддерева. Затем сравниваем модуль разности этих количеств на $1$, т к нам не важно, в каком из поддеревьев будет больше потомков на одного, главное, чтобы отличие было строго на один потомок.

Для приведенного дерева оранжевые узлы удовлетворяют этому условию:

САФУ. Практикум на С++ (Латухина). Лабораторная работа №3 (бинарные деревья). Количество потомков у оранжевых вершин не равно друг другу
Значение вершиныКоличество потомков в левом поддеревеКоличество потомков в правом поддеревеРазностьУсловие
-7011принято
14000 
25220 
36011принято
39000 
50561принято
61011принято
62000 
77231принято
94000 
100101принято
123202 

Реализация задачи на языке С++

Результаты работы программы

САФУ. Практикум на С++ (Латухина). Лабораторная работа №3 (бинарные деревья). Получение вершин, у которых количество потомков в левом поддереве отличается от количества потомков в правом поддереве на 1

➡  Для реализации индивидуального задания $№5$ мы воспользовались лишь одной готовой функцией (GetCountNodes — подсчет количества потомков), обход дерева пришлось кодировать с нуля, т к в модуле нет на $100\%$ подходящей функции обхода бинарного дерева поиска. Также программа, приведенная в задании $№5$, предназначена только для нахождения нужных вершин двоичного дерева поиска.