Удаление и поиск с барьером в бинарном дереве поиска

Question

#include <iostream>

using namespace std;


struct Tree{
    int value;
    Tree* left;
    Tree* right;
};

Tree* Add(Tree*& a, int elem) {
        if (!a) {
            a = new Tree;
            a->value = elem;
            a->left = nullptr;
            a->right = nullptr;
            return 0;
        }
        else if (elem < a->value) {
            Add(a->left, elem);
        }
        else  {
            Add(a->right, elem);
        }
        return a;
}
void Del(int x,Tree*& a) {
    Tree* parent = nullptr;
    while (a && x != a->value) {
        parent = a;
        if (x < a->value) a = a->left;
        else a = a->right;
    }
    if (!a) return;
    if (!a->left && !a->right) a->value = NULL;
    else if (a->left && !a->right) {//вместо a к parent цепляем левое поддерево
        if (parent && parent->left == a)
            parent->left = a->left;
        if (parent && parent->right == a)
            parent->right = a->left;
        delete a;
        return;
    }
    else if (!a->left && a->right) {     //вместо a к parent цепляем правое поддерево
        if (parent && parent->left == a)
            parent->left = a->right;
        if (parent && parent->right == a)
            parent->right = a->right;
        delete a;
        return;
    }
    else {
        Tree* min = a->left;//ищем наименьший элемент из левой ветки
        while (min->right) min = min->right;
        int min_value = min->value;
        Del(min_value,a);
        a->value = min_value;
    }
}
void printTree(Tree*& a) {
    if (a) {
        cout << a->value<<" ";
        printTree(a->left);
        printTree(a->right);

    }
    else return;
}

bool findTree(int x,Tree* a) {
    int cmp = 0;
        while (a&&x!=a->value) {           
                if (x < a->value) a=a->left;
                else a=a->right;  
                cmp++;
        }
        cout << "Количество сравнений: " << cmp << endl;
        return a!=NULL;
}

void Barrier(Tree*& a,Tree*& b) {
    if (a) {
        if (a->left == nullptr) a->left = b;
        if (a->right == nullptr) a->right = b;
        Barrier(a->left,b);
        Barrier(a->right,b);
    }
}
bool findBTree(int x, Tree*& a) {
    Tree* b=new Tree;
    b->value = x;
    int cmp = 0;
    Tree* parent = nullptr;
    Barrier(a,b);
    while (x != b->value) {
        if (x < a->value) a = a->left;
        else a = a->right;
        cmp++;
    }
    if (&a == &b) return false;
    cout << "Количество сравнений: " << cmp << endl;
    return a != NULL;
}
int main()
{
    setlocale(LC_ALL, "Russian");
    int x;
    int n;
    cout << "Введите количество элементов: " << endl;
    cin >> n;
    Tree* tree=NULL;
    cout << "Введите элементы дерева: "<<endl;
    for (int i = 0; i < n; i++) {
        cin >> x;
        Add(tree, x);
    }
    cout << "Элементы дерева: "<<endl;
    printTree(tree);
    cout << endl;
    cout << findTree(5,tree)<<endl;
    cout << findBTree(5,tree)<<endl;
    Del(3, tree);
    printTree(tree);

}

У меня неправильно работает удаление(Del) и поиск с барьером(findBTree). Вроде уловил суть поиска с барьером,но не понял как это сделать.

Answer 1

Вы уже задавали вопрос по поводу функции AddTree(), если посмотрите ответы - будет понятнее.
Но если коротко:
вы во все функции передаете ссылку на указатель на вершину дерева. И когда ищете элемент с нужным значением, вы переприсваиваете вершине потомков. Ваше дерево с каждым шагом просто укорачивается, причем теряются целые ветки! Вы их потом ни найти не можете ни удалить!
В функции Del():

если у найденного узла нет потомков, то просто значение обнуляете! Т.е. узел остается, только value==0. А удалять узел кто будет?
В этом коде если нужный для удаления элемент является вершиной дерева, то он не будет удален. Нужно делать отдельную проверку на удаление вершины дерева.
а последний блок, когда у элемента 2 потомка, вообще странный - логика не прослеживается. Кажется вы хотите удалить всю левую ветку, а не 1 узел? и элемент опять-таки не удаляется, т.к. рекурсивно вызывается Del() для потомка, а с самим узлом никаких операций не происходит
в последнем блоке в комментарии написано - ищем элемент в левой ветке, а двигаетесь по правой while (min->right) min = min->right; В любом случае движение по одной ветке.

void Del(int x,Tree*& a) {
    Tree* parent = nullptr;
    while (a && x != a->value) 
    {
        parent = a;
        if (x < a->value) // a - не итератор, а изменяемый указатель на вершину дерева!
            a = a->left;  // не движение по дереву, а укорачивание дерева
        else 
            a = a->right; // не движение по дереву, а укорачивание дерева
    }
    if (!a) return;
    
    if (!a->left && !a->right) // если нет потомков
        a->value = 0;  // А удалять узел кто будет? А у родителя обнулять дочернюю ветку?
    else if (a->left && !a->right) //вместо a к parent цепляем левое поддерево
    {
        if (parent && parent->left == a) // если удаляется вершина, то условие не выполнится, т.к. `parent == nullptr`
            parent->left = a->left;
     
        if (parent && parent->right == a) // если удаляется вершина, то условие не выполнится, т.к. `parent == nullptr`
            parent->right = a->left;
     
        delete a;
        return;
    }
    else if (!a->left && a->right)   //вместо a к parent цепляем правое поддерево
        {
        if (parent && parent->left == a)
            parent->left = a->right;
        if (parent && parent->right == a)
            parent->right = a->right;
        delete a;
        return;
        }
    else 
    {
        Tree* min = a->left; //ищем наименьший элемент из левой ветки
        while (min->right) 
        { 
            min = min->right;
        }
        int min_value = min->value;
        Del(min_value,a);
        a->value = min_value;
    }
}

БЛОГ НА HUSL

Удаление и поиск с барьером в бинарном дереве поиска

Ответы (1 шт):