work2/task2.cpp - develop - novd7/algirithms_sem2

work2/task2.cpp
77 строк2 KB
Новиков Владимир
work 2
03 апр 2026, 22:39
03 апр 2026, 22:3904518aa
#include <iostream>
#include <cstdlib>
#include <climits>
using namespace std;

// Структура узла двоичного дерева
struct Node {
    int data;     // Данные узла
    Node* left;   // Указатель на левое поддерево
    Node* right;  // Указатель на правое поддерево
};

// Функция для создания нового узла
Node* createNode(int value) {
    Node* newNode = new Node;
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Функция для добавления элемента в дерево
Node* insert(Node* root, int value) {
    if (!root) {
        root = createNode(value);  // Если дерево пустое, создаём корень
    } else if (value < root->data) {
        root->left = insert(root->left, value);  // Рекурсивно вставляем в левое поддерево
    } else {
        root->right = insert(root->right, value);  // Рекурсивно вставляем в правое поддерево
    }
    return root;
}

// Вспомогательная функция для поиска ближайшего значения
void findClosestHelper(Node* node, int x, int& closest) {
    if (!node) return;

    int diff = abs(node->data - x);
    int curDiff = abs(closest - x);

    if (diff < curDiff || (diff == curDiff && node->data < closest)) {
        closest = node->data;
    }

    findClosestHelper(node->left, x, closest);
    findClosestHelper(node->right, x, closest);
}

// Основная функция: возвращает ближайший балл к x (при равенстве — наименьший)
int findClosest(Node* root, int x) {
    int closest = root->data;
    findClosestHelper(root, x, closest);
    return closest;
}

// Главная функция
int main() {
    int n;
    cin >> n;

    Node* root = nullptr;

    // Чтение элементов дерева
    for (int i = 0; i < n; i++) {
        int value;
        cin >> value;
        root = insert(root, value);
    }

    int x;
    cin >> x;

    int result = findClosest(root, x);
    cout << result << endl;

    return 0;
}