BtreeNode.cpp - master - dimass1km/laba_5.

BtreeNode.cpp
127 строк3 KB
dimass1km
create: BtreeNode.cpp
15 мар 2026, 17:35
15 мар 2026, 17:35997e711
#include <iostream>
#include <string>
#include "BTreeNode.h"
Using namespace std;
//добавление узла
BtreeNode* addNode(BtreeNode* theRoot, user theData) {
    if (theRoot == NULL) {
        BtreeNode* curNode = new BtreeNode();
        curNode->d = theData;
        return curNode;
    }
    if (theRoot->d.id > theData.id) {
        theRoot->left = addNode(theRoot->left, theData);
    }
    else if (theRoot->d.id < theData.id) {
        theRoot->right = addNode(theRoot->right, theData);
    }
    return theRoot;
}

//поиск
BtreeNode* findNode(BtreeNode* root, int id) {
    if (root == NULL) {
        return NULL;
    }
    if (root->d.id == id) {
        return root;
    }
    if (id < root->d.id) {
        return findNode(root->left, id)
    }
    else {
        return findNode(root->right, id)
    }
}

//удаление
BtreeNode* deleteNode(int x, BtreeNode* tree) {
    BtreeNode** parent = &tree;
    BtreeNode* node2Del =
        findWithParent(x, tree, parent); // поиск узла для удаления и его родителя
    if (!node2Del)   return tree;

    BtreeNode* tempNode;
    // 0. У удаляемого узла нет потомков
    if (node2Del->right == nullptr && node2Del->left == nullptr) {
        if (*parent == node2Del)//если дерево из одного корня
        {
            delete node2Del;
            return NULL;
        }
        if ((*parent)->d.id < node2Del->d.id)
        {
            (*parent)->right = NULL;
        }
        else {
            (*parent)->left = NULL;
        }
        delete node2Del;
        return tree;
    }


    // 1. У удаляемого узла нет правого потомка
    if (node2Del->right == nullptr) {
        tempNode = node2Del->left;
        node2Del->d = tempNode->d;
        node2Del->left = tempNode->left;
        node2Del->right = tempNode->right;
        delete tempNode;
        return tree;
    }

    // 2. У удаляемого узла есть правый потомок, у которого нет левого потомка
    if (node2Del->right->left == nullptr) {
        tempNode = node2Del->right;
        node2Del->d = tempNode->d;
        node2Del->right = tempNode->right;
        delete tempNode;
        return tree;
    }


    BtreeNode* tempNodeParent = node2Del->right;
    tempNode = node2Del->right->left;
    while (tempNode->left != nullptr) {
        tempNodeParent = tempNode;
        tempNode = tempNode->left;
    }
    
    node2Del->d.id = tempNode->d.id;
    tempNodeParent->left = tempNode->right;
    delete tempNode;
    return tree;

}

//поиск с родителями
BtreeNode* findWithParent(int x, BtreeNode* tree, BtreeNode** outParent) {
    if (tree == NULL)
        return NULL;
    if (x < tree->d.id)
    {
        (*outParent) = tree;
        return findWithParent(x, tree->left, outParent);
    }
    if (x > tree->d.id)
    {
        (*outParent) = tree;
        return findWithParent(x, tree->right, outParent);
    }
    return tree;
}

void bft(BtreeNode* root) {
    if (root == nullptr) {
        cout << "В дереве отсутствуют значения";
        return;
    }

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

    cout << "Обход в ширину";
    while (!q.empty()) {
        BtreeNode* current = q.front();
        q.pop();