bstree_usando_referencias.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;
    }

    //referencia do braço do pai
    bnode *& find(bnode *& node ,int value){
        if(node == nullptr)
            return node;
        if(node->value == value)
            return node;
        if(value < node->value)
            return find(node->left, value);
        return find(node->right, value);
    }

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

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

    void show(bnode * node, string her){
        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 << endl;

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

int main()
{
    bstree tree;
    string op = "";
    while(op != "q"){
        cout << "f find; i insert; r remove; q quit" << endl;
        cin >> op;
        if(op == "i"){

            int value;
            while(true){
                cin >> value;
                if(value == -1)
                    break;
                tree.insert(value);
            }
            tree.show(tree.root, "");
        }
        if(op == "r"){
            int value;
            cin >> value;
            tree.remove(tree.find(tree.root, value));
            tree.show(tree.root, "");
        }
        if(op == "f"){
            int value;
            cin >> value;
            if(tree.find(tree.root, value) != nullptr)
                cout << "Node existe" << endl;
            else
                cout << "Node nao existe" << endl;

        }
    }
    return 0;
}