bst.cpp - main - silenww/laba

bst.cpp
220 строк5 KB
silenww
initial commit
10 мар 2026, 16:43
10 мар 2026, 16:433cae890
#include "btree.h"
#include <iostream>
#include <queue>
#include <fstream>
#include <limits>

using namespace std;

void printData(Data d) {
    cout << d.id << " "
        << d.surname << " "
        << d.profession << " "
        << d.workTime << " "
        << d.salary << "\n";
}

BtreeNode* addNode(BtreeNode* root, const Data& d) {
    if (root == nullptr) {
        BtreeNode* n = new BtreeNode();
        n->myData = d;
        n->left = nullptr;
        n->right = nullptr;
        return n;
    }

    if (d.id < root->myData.id)
        root->left = addNode(root->left, d);
    else if (d.id > root->myData.id)
        root->right = addNode(root->right, d);
    else
        cout << "����� ��������� ����� ��� ����������.\n";

    return root;
}

BtreeNode* findNode(BtreeNode* root, int id) {
    if (root == nullptr) return nullptr;
    if (id == root->myData.id) return root;

    if (id < root->myData.id)
        return findNode(root->left, id);
    else
        return findNode(root->right, id);
}

BtreeNode* findMin(BtreeNode* root) {
    while (root != nullptr && root->left != nullptr)
        root = root->left;
    return root;
}

BtreeNode* deleteNode(BtreeNode* root, int id) {
    if (root == nullptr) return nullptr;

    if (id < root->myData.id) {
        root->left = deleteNode(root->left, id);
    }
    else if (id > root->myData.id) {
        root->right = deleteNode(root->right, id);
    }
    else {
        if (root->left == nullptr && root->right == nullptr) {
            delete root;
            return nullptr;
        }

        if (root->left == nullptr) {
            BtreeNode* temp = root->right;
            delete root;
            return temp;
        }

        if (root->right == nullptr) {
            BtreeNode* temp = root->left;
            delete root;
            return temp;
        }

        BtreeNode* temp = findMin(root->right);
        root->myData = temp->myData;
        root->right = deleteNode(root->right, temp->myData.id);
    }

    return root;
}

void BFS(BtreeNode* root) {
    if (root == nullptr) {
        cout << "������ ������.\n";
        return;
    }

    queue<BtreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        BtreeNode* cur = q.front();
        q.pop();

        printData(cur->myData);

        if (cur->left != nullptr)
            q.push(cur->left);

        if (cur->right != nullptr)
            q.push(cur->right);
    }
}

void sumSalaryFor12(BtreeNode* root, double& sum, int& cnt) {
    if (root == nullptr) return;

    sumSalaryFor12(root->left, sum, cnt);

    if (root->myData.workTime == 12) {
        sum += root->myData.salary;
        cnt++;
    }

    sumSalaryFor12(root->right, sum, cnt);
}

void averageSalaryFor12(BtreeNode* root) {
    double sum = 0;
    int cnt = 0;

    sumSalaryFor12(root, sum, cnt);

    if (cnt == 0)
        cout << "��������� �� ������ 12 ��� �� �������.\n";
    else
        cout << "������� �����: " << sum / cnt << "\n";
}

void clearTree(BtreeNode* root) {
    if (root == nullptr) return;

    clearTree(root->left);
    clearTree(root->right);
    delete root;
}

void clearInput() {
    cin.clear();
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
}

Data inputData() {
    Data d;

    cout << "������� ID: ";
    cin >> d.id;
    clearInput();

    cout << "������� �������: ";
    getline(cin, d.surname);

    cout << "������� �������������: ";
    getline(cin, d.profession);

    cout << "������� ����: ";
    cin >> d.workTime;

    cout << "������� �����: ";
    cin >> d.salary;

    return d;
}

void loadFromFile(const string& filename, BtreeNode*& root) {
    ifstream fin(filename);

    if (!fin) {
        cout << "���� �� ������.\n";
        return;
    }

    Data d;
    while (fin >> d.id >> d.surname >> d.profession >> d.workTime >> d.salary) {
        root = addNode(root, d);
    }

    fin.close();
}

void runTests() {
    cout << "\n=== ����� ===\n";

    BtreeNode* t = nullptr;

    t = addNode(t, { 10, "Ivanov", "Engineer", 12, 50000 });
    t = addNode(t, { 5, "Petrov", "Worker", 10, 40000 });
    t = addNode(t, { 20, "Sidorov", "Manager", 12, 70000 });

    cout << "������:\n";
    BFS(t);

    if (findNode(t, 5) != nullptr)
        cout << "�����: OK\n";
    else
        cout << "�����: ERROR\n";

    averageSalaryFor12(t);

    t = deleteNode(t, 5);

    if (findNode(t, 5) == nullptr)
        cout << "��������: OK\n";
    else
        cout << "��������: ERROR\n";

    cout << "\n�������� ����� data.txt:\n";
    BtreeNode* f = nullptr;
    loadFromFile("data.txt", f);
    BFS(f);
    averageSalaryFor12(f);
    clearTree(t);
    clearTree(f);
    cout << "����� ������\n";
}