Синергия, Структуры и алгоритмы компьютерной обработки данных, задание 2

Раздел
Программирование
Просмотров
38
Покупок
0
Антиплагиат
Не указан
Размещена
28 Янв в 10:47
ВУЗ
Синергия
Курс
2 курс
Стоимость
200 ₽
Демо-файлы   
1
pdf
4_algo_dzdocx 4_algo_dzdocx
1.5 Мбайт 1.5 Мбайт
Файлы работы   
1
Каждая работа проверяется на плагиат, на момент публикации уникальность составляет не менее 40% по системе проверки eTXT.
docx
задание 2
122.3 Кбайт 200 ₽
Описание

Решение Задание №2

Оглавление

Задание №2

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

1. Определите класс, пропишите поля и сигнатуры методов. Поскольку наши методы будут напрямую работать с узлами дерева, то они должны быть закрытыми, то есть приватными. Поэтому нужно будет реализовать публичные методы, которые вызывают соответствующие приватные.

#include <iostream>

class BinarySearchTree {

public:

// Конструктор для создания пустого дерева

BinarySearchTree() : root(nullptr) {}

// Публичный метод для вставки нового значения в дерево

void insert(int value) {

root = insert(root, value);

}

// Публичный метод для удаления значения из дерева

void remove(int value) {

root = remove(root, value);

}

// Публичный метод для поиска значения в дереве

bool search(int value) {

return search(root, value) != nullptr;

}

// Публичный метод для печати дерева в консоль

void print() {

inorder();

std::cout << std::endl;

}

private:

// Определение структуры узла дерева

struct Node {

};

Node* root; // Корень дерева

// Приватный метод для вставки нового значения в дерево

Node* insert(Node* root, int value) {

// ...

}

// Приватный метод для удаления значения из дерева

Node* remove(Node* root, int value) {

// ...

}

// Приватный метод для поиска значения в дереве

Node* search(Node* root, int value) {

// ...

}

// Приватный метод для печати узлов дерева в порядке возрастания

void inorder() {

// ...

}

};

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

// Определение структуры узла дерева

struct Node {

int value; // Значение узла

Node* left; // Указатель на левого потомка

Node* right; // Указатель на правого потомка

// Конструктор для создания нового узла с заданным значением

Node(int value) : value(value), left(nullptr), right(nullptr) {}

};

3. Создайте функцию для вставки нового узла в дерево. Эта функция должна принимать корень дерева и значение нового узла в качестве аргументов и возвращать новый корень дерева.

// Приватный метод для вставки нового значения в дерево

Node* insert(Node* root, int value) {

// Если дерево пустое, создаем новый корень

if (root == nullptr) {

return new Node(value);

}

// Если значение меньше значения корня, вставляем его в левое поддерево

if (value < root->value) {

root->left = insert(root->left, value);

} // Иначе вставляем его в правое поддерево

else {

root->right = insert(root->right, value);

}

// Возвращаем новый корень дерева

return root;

}

4. Создайте функцию для поиска значения в дереве. Эта функция должна принимать корень дерева и значение для поиска в качестве аргументов и возвращать указатель на узел с этим значением или nullptr, если значение не найдено.

// Приватный метод для поиска значения в дереве

Node* search(Node* root, int value) {

// Если дерево пустое или значение найдено, возвращаем корень

if (root == nullptr || root->value == value) {

return root;

}

// Если значение меньше значения корня, ищем его в левом поддереве

if (value < root->value) {

return search(root->left, value);

} // Иначе ищем его в правом поддереве

else {

return search(root->right, value);

}

}

5. Создайте функцию для удаления узла из дерева. Эта функция должна принимать корень дерева и значение для удаления в качестве аргументов и возвращать новый корень дерева. Так как нам нужно сохранить свойства бинарного дерева, то для удаления элементов с обоими детьми нам понадобится вспомогательный метод, который ищет преемника. В качестве преемника будем выбирать наименьший элемент левого поддерева.

// Приватный метод для нахождения узла с минимальным значением в дереве

Node* findMin(Node* root) {

while (root->left != nullptr) {

root = root->left;

} return root;

}

// Приватный метод для удаления значения из дерева

Node* remove(Node* root, int value) {

// Если дерево пустое, возвращаем nullptr

if (root == nullptr) {

return nullptr;

}

// Если значение меньше значения корня, удаляем его из левого поддерева

if (value < root->value) {

root->left = remove(root->left, value);

} // Если значение больше значения корня, удаляем его из правого поддерева

else if (value > root->value) {

root->right = remove(root->right, value);

} // Иначе удаляем корень

else {

// Если у корня нет потомков или только один потомок

if (root->left == nullptr) {

Node* temp = root->right;

delete root;

return temp;

}

else if (root->right == nullptr) {

Node* temp = root->left;

delete root;

return temp;

} // Если у корня есть оба потомка

else {

// Находим узел с минимальным значением в правом поддереве

Node* temp = findMin(root->right);

// Копируем значение этого узла в корень

root->value = temp->value;

// Удаляем этот узел из правого поддерева

root->right = remove(root->right, temp->value);

}

}

// Возвращаем новый корень дерева

return root;

}

6. Создайте функцию для печати узлов дерева в порядке возрастания. Так как эта функция должна осуществлять обход дерева в глубину, что делается рекурсивно, то нам понадобится функция-помощник.

// Приватный метод для печати узлов дерева в порядке возрастания

void inorder() {

inorderHelper(root);

}

// Приватный рекурсивный метод-помощник для печати

void inorderHelper(Node* root) {

// Если дерево не пустое

if (root != nullptr) {

// Обходим левое поддерево

inorderHelper(root->left);

// Печатаем значение корня

std::cout << root->value << ' ';

// Обходим правое поддерево

inorderHelper(root->right);

}

}

7. Добавьте тесты в функцию main(), в итоге у Вас должен получиться следующий код:

 Протестируйте программу на своих тестах. Отправьте преподавателю скриншот консоли.

Вам подходит эта работа?
Похожие работы
Основы программирования
Отчет по практике Практика
31 Янв в 15:25
30
0 покупок
Основы программирования
Задача Задача
30 Янв в 12:26
35
0 покупок
Основы программирования
Тест Тест
30 Янв в 09:53
33
0 покупок
Основы программирования
Задача Задача
29 Янв в 21:00
26
0 покупок
Основы программирования
Курсовая работа Курсовая
29 Янв в 12:48
33
0 покупок
Другие работы автора
Бизнес-планирование
Тест Тест
31 Янв в 05:45
28
0 покупок
Управление персоналом
Тест Тест
30 Янв в 16:39
41 +4
0 покупок
Маркетинг
Тест Тест
30 Янв в 12:57
33 +1
0 покупок
Налоги, налогообложение и налоговое планирование
Тест Тест
28 Янв в 15:00
51 +1
2 покупки
Основы программирования
Задача Задача
28 Янв в 13:57
53 +2
0 покупок
Основы программирования
Задача Задача
28 Янв в 13:53
46 +1
0 покупок
Основы программирования
Задача Задача
28 Янв в 13:51
44 +1
0 покупок
Основы программирования
Задача Задача
28 Янв в 13:42
44
0 покупок
Аудит
Тест Тест
27 Янв в 05:47
44 +2
2 покупки
Интернет-маркетинг
Тест Тест
27 Янв в 05:14
22
0 покупок
Стратегический менеджмент
Тест Тест
17 Янв в 15:22
107 +2
6 покупок
Экономика предприятия
Ответы на билеты Билеты
17 Дек 2024 в 22:58
71 +1
4 покупки
Основы программирования
Тест Тест
26 Ноя 2024 в 12:16
59 +1
0 покупок
Управление персоналом
Тест Тест
30 Сен 2024 в 05:50
104
4 покупки
Дизайн
Тест Тест
26 Сен 2024 в 02:02
137 +1
4 покупки
Промышленное и гражданское строительство
Тест Тест
18 Сен 2024 в 18:14
123
4 покупки
Прикладная математика
Тест Тест
18 Сен 2024 в 04:18
152
3 покупки
Темы журнала
Показать ещё
Прямой эфир