Btree.cpp - master - RinFall/lab5

Btree.cpp
110 строк3 KB
RinFall
add lab
27 апр 2026, 03:47
27 апр 2026, 03:47886f374
#include "Btree.h"
#include <iostream>

using namespace std;

Node* createNode(Data data) {
    Node* newNode = new Node;
    newNode->d = data;
    newNode->left = nullptr;
    newNode->right = nullptr;
    return newNode;
}

void AddNode(Node*& root, Data data) {
    if (root == nullptr) {
        root = createNode(data);
        return;
    }
    if (data.id < root->d.id) {
        AddNode(root->left, data);
    }
    else {
        AddNode(root->right, data);
    }
}

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

Node* deleteNode(Node* root, int key) {
    if (root == nullptr) return root;

    if (key < root->d.id)
        root->left = deleteNode(root->left, key);
    else if (key > root->d.id)
        root->right = deleteNode(root->right, key);
    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;
        }

        Node* temp = findMin(root->right);
        root->d = temp->d;
        root->right = deleteNode(root->right, temp->d.id);
    }
    return root;
}

Node* findNode(Node* root, int key) {
    if (root == nullptr) return nullptr;

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

void collectDuplicates(Node* root, set<string>& seen, vector<int>& ids) {
    if (!root) return;

    collectDuplicates(root->left, seen, ids);

    if (seen.count(root->d.name))
        ids.push_back(root->d.id);
    else
        seen.insert(root->d.name);

    collectDuplicates(root->right, seen, ids);
}

void removeDuplicateSurnames(Node*& root) {
    set<string> seen;
    vector<int> ids;

    collectDuplicates(root, seen, ids);

    for (int id : ids)
        root = deleteNode(root, id);
}

void printNormal(Node* root, int level) {
    if (!root) return;

    printNormal(root->right, level + 1);
    for (int i = 0; i < level; i++) cout << "   ";
    cout << root->d.id << " (" << root->d.name << ")\n";
    printNormal(root->left, level + 1);
}

void printReverse(Node* root, int level) {
    if (!root) return;

    printReverse(root->left, level + 1);
    printReverse(root->right, level + 1);

    for (int i = 0; i < level; i++) cout << "   ";
    cout << root->d.id << " (" << root->d.name << ")\n";
}