Решение Задание №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(), в итоге у Вас должен получиться следующий код:
Протестируйте программу на своих тестах. Отправьте преподавателю скриншот консоли.