BinarySearchTree.cpp

#include "BinarySearchTree.h"
#include <fstream>
#include <iomanip>

// Конструктор
BinarySearchTree::BinarySearchTree(const string& fileName) : root(nullptr), fileName(fileName) {
    buildTreeFromFile();
}

// Построение дерева из файла
void BinarySearchTree::buildTreeFromFile() {
    ifstream binaryFile(fileName, ios::binary);
    if (!binaryFile.is_open()) {
        cerr << "Failed to open binary file for building tree!" << endl;
        return;
    }

    long position = 0;
    DictionaryEntry entry;
    while (binaryFile.read(reinterpret_cast<char*>(&entry), sizeof(entry))) {
        if (entry.englishWord[0] != '\0' && entry.englishWord[0] != '*') { // Пропускаем удалённые и пустые записи
            insert(string(entry.englishWord.data()), position);
        }
        position += 1;
    }
    binaryFile.close();
}

// Вставка элемента
shared_ptr<TreeNode> BinarySearchTree::insertRecursively(shared_ptr<TreeNode> node, const string& key, long filePosition) {
    if (!node) {
        return make_shared<TreeNode>(key, filePosition);
    }
    if (key < node->key) {
        node->left = insertRecursively(node->left, key, filePosition);
    }
    else if (key > node->key) {
        node->right = insertRecursively(node->right, key, filePosition);
    }
    return node;
}

void BinarySearchTree::insert(const string& key, long filePosition) {
    root = insertRecursively(root, key, filePosition);
}

// Поиск элемента
void BinarySearchTree::search(const string& key) const {
    shared_ptr<TreeNode> current = root;
    while (current) {
        if (key == current->key) {
            cout << "Ключ найден: " << key << ", позиция в файле: " << current->filePosition << endl;
            return;
        }
        else if (key < current->key) {
            current = current->left;
        }
        else {
            current = current->right;
        }
    }
    cout << "Ключ не найден: " << key << endl;
}

// Удаление элемента
shared_ptr<TreeNode> BinarySearchTree::removeRecursively(shared_ptr<TreeNode> node, const string& key) {
    if (!node) return node;

    if (key < node->key) {
        node->left = removeRecursively(node->left, key);
    }
    else if (key > node->key) {
        node->right = removeRecursively(node->right, key);
    }
    else {
        if (!node->left) {
            return node->right;
        }
        else if (!node->right) {
            return node->left;
        }

        node->key = findMinimum(node->right)->key;
        node->right = removeRecursively(node->right, node->key);
    }
    return node;
}

void BinarySearchTree::remove(const string& key) {
    root = removeRecursively(root, key);
}

shared_ptr<TreeNode> BinarySearchTree::findMinimum(shared_ptr<TreeNode> node) const {
    shared_ptr<TreeNode> current = node;
    while (current && current->left) {
        current = current->left;
    }
    return current;
}

// Вывод дерева
void BinarySearchTree::printTree() const {
    printTreeRecursively(root, 0);
}

void BinarySearchTree::printTreeRecursively(shared_ptr<TreeNode> node, int space) const {
    if (!node) return;

    space += 5;
    printTreeRecursively(node->right, space);
    cout << endl;
    for (int i = 5; i < space; i++) {
        cout << " ";
    }
    cout << node->key << "\n";
    printTreeRecursively(node->left, space);
}