bst.cpp

#include <iostream>
#include <memory>

using namespace std;

template<class T>
class binary_tree {
    struct node {
        unique_ptr<node> left;
        unique_ptr<node> right;
        T value;
        node(const T& value_) : value(value_) { }

        static unique_ptr<node> from(const T& value) {
            return unique_ptr<node>(new node(value));
        }
    };
    typedef unique_ptr<node> node_ptr;
    node_ptr root_;

    void insert(node_ptr& root, const T& value) {
        if (!root) {
            root = std::move(node::from(value));
        } else {
            if (value > root->value)
                insert(root->right, value);
            else
                insert(root->left, value);
        }
    }

    bool search(const node_ptr& root, const T& value) {
        if (!root) {
            return false;
        } else {
            if (value > root->value)
                return search(root->right, value);
            else
                return search(root->left, value);
        }
    }

    void order(const node_ptr& root) {
        if (root) {
            order(root->left);
            cout << root->value << ' ';
            order(root->right);
        }
    }

    void preorder(const node_ptr& root) {
        if (root) {
            cout << root->value << ' ';
            order(root->left);
            order(root->right);
        }
    }

    void posorder(const node_ptr& root) {
        if (root) {
            order(root->left);
            order(root->right);
            cout << root->value << ' ';
        }
    }

    node_ptr minimum(node_ptr& root) {
        if (!root || !root->left)
            return std::move(root);

        return std::move(minimum(root->left));
    };

    node_ptr remove(node_ptr& root, const T& value) {
        if (!root)
            return std::move(root);

        if (value > root->value)
            root->right = std::move(remove(root->right, value));
        else if (value < root->value)
            root->left = std::move(remove(root->left, value));
        else {
            node_ptr here = std::move(root);
            if (here->left == here->right)
                return node_ptr();

            if (!here->right)
                return std::move(here->left);

            if (!here->left)
                return std::move(here->right);

            node_ptr min = std::move(minimum(here->right));
            min->left = std::move(here->left);
            if (here->right)
                min->right = std::move(remove(here, value));
            return std::move(min);
        }
        return std::move(root);
    }

public:
    binary_tree() {
    }

    void insert(const T& value) {
        insert(root_, value);
    }

    void order() {
        order(root_);
        cout << endl;
    }
    void preorder() {
        preorder(root_);
        cout << endl;
    }
    void posorder() {
        posorder(root_);
        cout << endl;
    }

    void remove(const T& value) {
        root_ = std::move(remove(root_, value));
    }

    bool search(const T& value) {
        return search(root_, value);
    }
};

void test_remove(int v)
{
    binary_tree<int> tree;
    tree.insert(10);
    tree.insert(5);
    tree.insert(20);
    tree.insert(15);
    tree.insert(28);
    tree.insert(25);
    tree.insert(30);

    tree.order();
    tree.remove(v);
    tree.order();
}

int main()
{
    test_remove(20);
    return 0;
}