Бинарное дерево

#include <iostream>
#include <iomanip>
 
template<typename T>
class Dequeue {
public:
    Dequeue() : base() {}
    Dequeue(const Dequeue<T> &) = delete;
    Dequeue<T> &operator=(const Dequeue<T> &) = delete;
    Dequeue(Dequeue<T> &&) noexcept = delete;
    Dequeue<T> &operator=(Dequeue<T> &&) noexcept = delete;
 
    ~Dequeue() {
        clear();
    }
    void clear() {
        while (!empty()) {
            delete base.next;
        }
    }
    bool empty() const {
        return base.next == &base;
    }
    const T &front() const {
        return base.next->getValue();
    }
    const T &back() const {
        return base.prev->getValue();
    }
    void popFront() {
        delete base.next;
    }
    void popBack() {
        delete base.prev;
    }
    void pushFront(const T &value) {
        new VNode(base.next, value);
    }
    void pushBack(const T &value) {
        new VNode(&base, value);
    }
private:
    struct VNode;
    struct Node {
        Node *prev;
        Node *next;
        Node() : prev(this), next(this) {}
        Node(Node *before) : prev(before->prev), next(before) {
            prev->next = next->prev = this;
        }
        virtual ~Node() {
            prev->next = next;
            next->prev = prev;
        }
        const T &getValue() const {
            return dynamic_cast<const VNode*>(this)->value;
        }
    };
    struct VNode : public Node {
        T value;
        VNode(Node *before, const T &value) : Node(before), value(value) {}
    };
 
    Node base;
};
 
template<typename T>
class BSTree {
public:
    struct Node {
        T value;
        Node *left;
        Node *right;
        Node(const T &value) : value(value), left(nullptr), right(nullptr) {}
    };
 
    BSTree() : root(nullptr) {}
    BSTree(const BSTree<T> &) = delete;
    BSTree<T> &operator=(const BSTree<T> &) = delete;
    BSTree(BSTree<T> &&) noexcept = delete;
    BSTree<T> &operator=(BSTree<T> &&) noexcept = delete;
    ~BSTree() {
        clear();
    }
 
    void insert(const T &value) {
        if (!root) {
            root = new Node(value);
            return;
        }
        Node **current = &root;
        while (*current) {
            current = (value < (*current)->value) ? &(*current)->left : &(*current)->right;
        }
        *current = new Node(value);
    }
 
    template<typename Consumer>
    void traverseInOrder(Consumer consume) {
        Dequeue<Node*> stack;
        Node *current = root;
        while (current || !stack.empty()) {
            while (current) {
                stack.pushBack(current);
                current = current->left;
            }
            current = stack.back();
            stack.popBack();
            consume(current->value);
            current = current->right;
        }
    }
 
    bool contains(const T &value) const {
        for (Node *current = root; current;) {
            if (current->value == value) {
                return true;
            }
            current = (value < current->value) ? current->left : current->right;
        }
        return false;
    }
 
    void clear() {
        if (root) {
            Dequeue<Node*> queue;
            queue.pushBack(root);
            while (!queue.empty()) {
                Node *node = queue.front();
                queue.popFront();
                if (node->left) {
                    queue.pushBack(node->left);
                }
                if (node->right) {
                    queue.pushBack(node->right);
                }
                delete node;
            }
        }
    }
 
private:
    Node *root;
};
 
int main() {
    //         5
    //     3       8
    //   2   4   6   9
    // 1
    int data[] { 5, 3, 8, 2, 4, 6, 9, 1 };
 
    BSTree<int> tree;
 
    for (int v : data) {
        tree.insert(v);
    }
 
    tree.traverseInOrder([](int v) { std::cout << v << ' '; });
 
    std::cout << '\n';
    for (int i = 0; i < 11; ++i) {
        std::cout << std::setw(2) << i << ": " << std::boolalpha << tree.contains(i) << '\n';
    }
 
    return 0;
}