Arvore Binária de Busca com Elo sem smart find

bstree_elo.cpp

#include <iostream>

using namespace std;

struct bnode{
    int value;
    bnode * left;
    bnode * right;
    bnode(int value = 0){
        this->value = value;
    }
};

struct bstree{
    bnode * root{nullptr};

    bstree(){
    }

    ~bstree(){
        clear(root);
        root = nullptr;
    }

    void clear(bnode * node){
        if(node == nullptr)
            return;
        clear(node->left);
        clear(node->right);
        delete node;
    }

    void _show(bnode * node, string her, bnode * ref = nullptr, int value = 0){
        if(node != nullptr)
            if((node->left != nullptr) || (node->right != nullptr))
                _show(node->left, her + "l");

        for(int i = 0; i < ((int)her.size() - 1); i++){
            if(her[i] != her[i + 1])
                cout << "│   ";
            else
                cout << "    ";
        }
        if(her != ""){
            if(her.back() == 'l')
                cout << "<───";
            else
                cout << ">───";
        }
        if(node == nullptr){
            cout << "#" << endl;
            return;
        }
        cout << node->value;
        if(ref == node)
            cout << "(" << value << ")";
        cout << endl;

        if((node->left != nullptr) || (node->right != nullptr))
            _show(node->right, her + "r");
    }

    void show(bnode * ref = nullptr, int value = 0){
        cout << "VVVVVVVVVVVVVVVVVVVVVVVVVVVV" << endl;
        _show(root, "", ref, value);
        cout << "AAAAAAAAAAAAAAAAAAAAAAAAAAAA" << endl << endl;
    }

    bool _insert(bnode * node, int value, bnode ** elo){
        if(node == nullptr){
            *elo = new bnode(value);
            return true;
        }
        if(node->value == value)
            return false;
        if(value < node->value)
            return _insert(node->left, value, &node->left);
        return _insert(node->right, value, &node->right);
    }

    bool insert(int value){
        return _insert(root, value, &root);
    }

    bool _exist(bnode * node, int value){
        if(node == nullptr)
            return false;
        if(node->value == value)
            return true;
        if(value < node->value)
            return _exist(node->left, value);
        return _exist(node->right, value);
    }

    bool exist(int value){
        return _exist(root, value);
    }

    int _sequestro(bnode * node, bnode ** elo){
        if(node->right == nullptr){
            int value = node->value;
            _kill(node, elo);
            return value;
        }
        return _sequestro(node->right, &node->right);

    }

    void _kill(bnode * node, bnode ** elo){
        if(node->left == nullptr && node->right == nullptr){
            *elo = nullptr;
            delete node;
            return;
        }
        if(node->left != nullptr && node->right == nullptr){
            *elo = node->left;
            delete node;
            return;
        }
        if(node->left == nullptr && node->right != nullptr){
            *elo = node->right;
            delete node;
            return;
        }
        node->value = _sequestro(node->left, &node->left);
    }

    bool _remove(bnode * node, int value, bnode ** elo){
        if(node == nullptr)
            return false;
        if(node->value == value){
            _kill(node, elo);
            return true;
        }
        if(value < node->value)
            return _remove(node->left, value, &node->left);
        return _remove(node->right, value, &node->right);
    }

    bool remove(int value){
        return _remove(root, value, &root);
    }

};

int main()
{
    bstree tree;
    char op = ' ';
    while(op != 'q'){
        cout << "i insert; r remove; q quit" << endl;
        cin >> op;
        if(op == 'i'){
            int value;
            cin >> value;
            tree.insert(value);
            tree.show();
        }
        if(op == 'r'){
            int value;
            cin >> value;
            tree.remove(value);
            tree.show();
        }
    }
    return 0;
}