BSTree.cpp

#include <iostream>
#include <stack>

using namespace std;

template<typename T>
class Node {
public:
    Node *l;
    Node *r;
    T key;
    
    Node(T value, Node *l, Node *r) {
        this->key = value;
        this->l = l;
        this->r = r;
    }
};

template<typename T>
class Iterator {
private:
    Node<T> *root;
    stack<const Node<T> *> s;
    Node<T> *prev;
    
    void allLeft(Node<T> *node) {
        while (node) {
            this->s.push(node);
            node = node->l;
        }
    }
    
public:
    explicit Iterator(Node<T> *node) {
        root = node;
        allLeft(root);
    }
    
    Iterator operator--() {
        allLeft(prev);
        root = prev;
        return *this;
    }
    
    Iterator operator++() {
        Node<T> *tmp = s.top();
        prev = tmp;
        s.pop();
        if (root->r) {
            allLeft(tmp->r);
            root = s.top();
        } else {
            root = NULL;
        }
        return *this;
    }
    
    bool operator==(const Iterator &iterator1) {
        return root == iterator1.root;
    }
    
    bool operator!=(const Iterator &iterator1) {
        return !(*this == iterator1);
    }
    
    Node<T> *operator->() {
        if (s.empty())
            return root;
        return s.top();
    }
    
    Node<T> *current() {
        return s.top();
    }
    
};

template<typename T>
class ConstIterator {
private:
    const Node<T> *root;
    stack<const Node<T> *> s;
    const Node<T> *prev;
    
    void allLeft(const Node<T> *node) {
        while (node) {
            this->s.push(node);
            node = node->l;
        }
    }
    
public:
    explicit ConstIterator(Node<T> *node) {
        root = node;
        allLeft(root);
    }
    
    ConstIterator operator++() {
        
        if (root->r) {
            Node<T> *tmp = s.top();
            prev = tmp;
            s.pop();
            allLeft(tmp->r);
            root = s.top();
        } else {
            root = NULL;
        }
        return *this;
    }
    
    ConstIterator operator--() {
        allLeft(prev);
        root = prev;
        return *this;
    }
    
    bool operator==(const ConstIterator &iterator1) {
        return root == iterator1.root;
    }
    
    bool operator!=(const ConstIterator &iterator1) {
        return !(*this == iterator1);
    }
    
    const Node<T> *operator->() {
        if (s.empty())
            return root;
        return s.top();
    }
    
    Node<T> *current() {
        return s.top();
    }
    
};

template<typename T>
class BST {
private:
    Node<T> *root;
    size_t size1;
    
    
public:
    
    friend class Iterator<T>;
    
    friend class ConstIterator<T>;
    
    BST() {
        root = nullptr;
        size1 = 0;
    }
    
    BST(const T BST) {
        size1 = 1;
        this->root = new Node<T>(BST, NULL, NULL);
    }
    
    BST &operator=(BST<T> &a) {
        size1 = 1;
        Iterator<T> i = a.begin();
        root = new Node<T>(i->key, NULL, NULL);
        ++i;
        while (i != a.end()) {
            insert(i->key);
            ++i;
        }
    }
    
    ~BST() {
        this->delNode(this->root);
    }
    
    bool empty() const {
        return this->size1 == 0;
    }
    
    size_t size() const {
        return this->size1;
    }
    
    Iterator<T> begin() {
        return Iterator<T>(root);
    }
    
    ConstIterator<T> cbegin() {
        return ConstIterator<T>(root);
    }
    
    Iterator<T> end() {
        return Iterator<T>(NULL);
    }
    
    ConstIterator<T> cend() {
        return ConstIterator<T>(NULL);
    }
    
public:
    Iterator<T> find(const T &value) {
        Node<T> *root = find(value, this->root);
        return Iterator<T>(root);
    }
    
private:
    Node<T> *find(const T value, Node<T> *currNode) const {
        if (currNode == NULL) return NULL;
        if (currNode->key == value) return currNode;
        if (value < currNode->key) {
            this->find(value, currNode->l);
        } else {
            this->find(value, currNode->r);
        }
    }
    
public:
    Iterator<T> insert(const T &value) {
        auto *tmp = new Node<T>(value, NULL, NULL);
        if (this->root == NULL) {
            this->root = tmp;
        } else {
            Node<T> *root = insert(tmp, this->root);
        }
        this->size1++;
        return Iterator<T>(tmp);
    }
    
    
private:
    
    Node<T> *insert(Node<T> *node, Node<T> *currNode) {
        if (currNode == NULL) return node;
        if (node->key <= currNode->key) {
            currNode->l = this->insert(node, currNode->l);
        } else {
            currNode->r = this->insert(node, currNode->r);
        }
    }
    
public:
    Iterator<T> remove(const T &value) {
        Node<T> *root = remove(value, this->root);
        return Iterator<T>(root);
    }
    
private:
    Node<T> *remove(T value, Node<T> *currNode) {
        currNode = find(value, currNode);
        if (currNode == NULL)
            return NULL;
        if (currNode->l != NULL && currNode->r != NULL) {
            currNode->key = Iterator<T>(currNode->r).current()->key;
            currNode->r = remove(root->r->key, root->r);
        } else if (currNode->l != NULL)
            currNode = currNode->l;
        else currNode = currNode->r;
        return currNode;
    }
    
    void delNode(Node<T> *node) {
        if (node != NULL) {
            delNode(node->l);
            delNode(node->r);
            this->size1--;
            delete node;
        }
    };
};

int main() {
    
    return 0;
}