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

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

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