Lab5/Tree.cpp - master - Oppq/Labs

Lab5/Tree.cpp
200 строк5 KB
Oppq
update: Main.cpp, ObMen.cpp, Tree.cpp, Tree.h
25 фев 2026, 19:33
25 фев 2026, 19:33444ad2f
// Основные функции

#include "Tree.h"
#include <iostream>
#include <queue>
#include <string>
#include <fstream>
using namespace std;

// с практики: добавление нового узла

Btree* addNode(Btree* theRoot, Data theData)
{
    if (theRoot == NULL)
    {

        Btree* curNode = new Btree();
        curNode->d = theData;
        curNode->left = NULL;
        curNode->right = NULL;
        return curNode;
    }

    if (theRoot->d.id > theData.id)
    {
        theRoot->left = addNode(theRoot->left, theData);
    }
    if (theRoot->d.id < theData.id)

    {
        theRoot->right = addNode(theRoot->right, theData);
    }

    return theRoot;
}

// Поиск узла

string findNode(Btree* theRoot, int theID)
{
    if (theRoot == nullptr) { return "not found"; }

    if (theRoot != nullptr && theID < theRoot->d.id) { return findNode(theRoot->left, theID); } // Изначально было: "if (theRoot->d.id > theID) { return findNode(theRoot->left, theID); }", исправил (включая и следующие), тк: сравнение перепутано, нужно проверять theID < theRoot->d.id

    if (theRoot != nullptr && theID > theRoot->d.id) { return findNode(theRoot->right, theID); }

    if (theRoot != nullptr && theRoot->d.id == theID) { return theRoot->d.name; }
    
    return "not found";
}

// Индивидуальное задание

Tree* addDetail(Tree* root, Detail detail) 
{
    if (root == nullptr) {
        return new Tree(detail);
    }

    if (detail.code < root->det.code) {
        root->left = addDetail(root->left, detail);
    }
    else if (detail.code > root->det.code) {
        root->right = addDetail(root->right, detail);
    }

    return root;
}

Tree* findDetail(Tree* root, int code) 
{
    if (root == nullptr) {
        return nullptr;
    }

    if (code < root->det.code) {
        return findDetail(root->left, code);
    }
    else if (code > root->det.code) {
        return findDetail(root->right, code);
    }
    else {
        return root;
    }
}

// удаление узла + рассмотрим все случаи

Tree* deleteDetail(Tree* root, int code)
{
    if (root == nullptr) return nullptr;

    if (code < root->det.code)
    {
        root->left = deleteDetail(root->left, code);
        return root;

    }

    else if (code > root->det.code)
    {
        root->right = deleteDetail(root->right, code);
        return root;
    }

    // нет правого потомка

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

    // правый потомок есть, у него нет левого

    Tree* rightNode = root->right;

    if (rightNode->left == nullptr)
    {
        rightNode->left = root->left;
        delete root;
        return rightNode;
    }

    // правый потомок имеет левого потомка

    Tree* parent = rightNode;
    Tree* child = rightNode->left;

    while (child->left != nullptr)
    {
        parent = child;
        child = child->left;
    }

    parent->left = child->right;
    child->left = root->left;
    child->right = root->right;

    delete root;
    return child;
}


void deleteTree(Tree* root)
{
    if (!root) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

Tree* loadFromFile(Tree* root) 
{
    ifstream file("details.txt");
    if (!file.is_open()) 
    {
        cout << "Ошибка: файл не найден!" << endl;
        return root;
    }
    
    Detail d;
    int c = 0;
    
    while (file >> d.code >> d.name >> d.price >> d.weight)  // true / false для всех данных сразу (множество)
    {
        root = addDetail(root, d);
        c++;
    }
    
    file.close();
    cout << "Загружено " << c << " деталей из файла" << endl; // Проверка на правильность вывода
    return root;
}

Detail inputDetail()
{
    Detail d;
    cout << "Шифр: "; cin >> d.code;
    cout << "Название: "; cin >> d.name;
    cout << "Цена: "; cin >> d.price;
    cout << "Вес: "; cin >> d.weight;
    return d;
}

Tree* deleteByPrice(Tree* root, double minPrice) 
{
    if (!root) return nullptr;
    root->left = deleteByPrice(root->left, minPrice);
    root->right = deleteByPrice(root->right, minPrice);
    
    if (root->det.price < minPrice) 
    {
        cout << "Удаляем: " << root->det.name << endl;
        return deleteDetail(root, root->det.code);
    }
    
    return root;
}