Árvore binária de busca implementada utilizando duplo ponteiro.

bstree_usando_duplo_ponteiro.cpp

#include <iostream>

using namespace std;

struct bnode {
    int value;
    bnode * left{nullptr};
    bnode * right{nullptr};
    bnode(int v){
        value = v;
    }
};

void getch(){
    string s;
    getline(cin, s);
}

struct bstree{
    bnode * root{nullptr};

    bnode ** find(int value){
        return find(&root, value);
    }

    bnode ** find(bnode ** node, int value){
        if(*node == nullptr)
            return node;
        if((*node)->value == value)
            return node;
        if((*node)->value > value)
            return find(&(*node)->left, value);
        return find(&(*node)->right, value);
    }

    bool exist(int value){
        return (*find(value) != nullptr);
    }

    bool insert(int value){
        auto node = find(value);
        if(*node == nullptr){
            *node = new bnode(value);
            return true;
        }
        return false;
    }

    void remove(bnode ** node){
        if(*node == nullptr)
            return;
        auto ptr = *node;
        if(ptr->left == nullptr && ptr->right == nullptr){
            delete *node;
            *node = nullptr;
        }
        else if(ptr->left != nullptr && ptr->right == nullptr){
            auto aux = (*node)->left;
            delete *node;
            *node = aux;
        }
        else if(ptr->left == nullptr && ptr->right != nullptr){
            auto aux = (*node)->right;
            delete *node;
            *node = aux;
        }
        else{
            auto suc = ptr->left;
            while(suc->right != nullptr)
                suc = suc->right;
            auto value = suc->value;
            remove(find(value));
            (*node)->value = value;
        }
    }

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

        int tam = her.size();
        for(int i = 0; i < tam - 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(ancora == node)
            cout << "(" << value << ")";
        cout << endl;

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

    void show(bnode * ancora = nullptr, int value = 0){
        cout << "VVVVVVVVVVVVVVVVVVVVVVVVVVV" << endl;
        rshow(root, "", ancora, value);
        cout << "AAAAAAAAAAAAAAAAAAAAAAAAAAA" << endl;
    }
};

int main(){
    bstree tree;
    string op = "";
    while(op != "q"){
        cout << "insert: i value ... -1; remove: r; quit: q" << endl;
        cin >> op;
        if(op == "i"){

            int value;
            while(true){
                cin >> value;
                if(value == -1)
                    break;
                tree.insert(value);
            }
            tree.show();
        }
        if(op == "r"){
            int value;
            cin >> value;
            tree.remove(tree.find(value));
            tree.show();
        }
    }
    return 0;
}