Binary Tree example(3 sem.)

#include <iostream>
#include <random>
#include <queue>

int getRandomNumber(int min, int max) {
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<int> dis(min, max);
    return dis(gen);
}

struct Trunk
{
    Trunk* prev;
    std::string str;

    Trunk(Trunk* prev, std::string str)
    {
        this->prev = prev;
        this->str = str;
    }
};

class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node* next;

    explicit Node(int value) {
        data = value;
        left = nullptr;
        right = nullptr;
        next = nullptr;
    }
};

class BinarySearchTree {
private:
    Node* root;

    Node* insertNode(Node* node, int value) {
        if (node == nullptr) {
            return new Node(value);
        }

        if (value < node->data) {
            node->left = insertNode(node->left, value);
        }
        else if (value > node->data) {
            node->right = insertNode(node->right, value);
        }

        return node;
    }

    static Node* findMinNode(Node* node) {
        while (node->left != nullptr) {
            node = node->left;
        }
        return node;
    }

    Node* deleteNode(Node* node, int value) {
        if (node == nullptr) {
            return nullptr;
        }

        if (value < node->data) {
            node->left = deleteNode(node->left, value);
        }
        else if (value > node->data) {
            node->right = deleteNode(node->right, value);
        }
        else {
            if (node->left == nullptr && node->right == nullptr) {
                delete node;
                node = nullptr;
            }
            else if (node->left == nullptr) {
                Node* temp = node;
                node = node->right;
                delete temp;
            }
            else if (node->right == nullptr) {
                Node* temp = node;
                node = node->left;
                delete temp;
            }
            else {
                Node* temp = findMinNode(node->right);
                node->data = temp->data;
                node->right = deleteNode(node->right, temp->data);
            }
        }

        return node;
    }

    void inorderTraversal(Node* node) {
        if (node != nullptr) {
            inorderTraversal(node->left);
            std::cout << node->data << " ";
            inorderTraversal(node->right);
        }
    }

    void preorderTraversal(Node* node) {
        if (node != nullptr) {
            std::cout << node->data << " ";
            preorderTraversal(node->left);
            preorderTraversal(node->right);
        }
    }

    void postorderTraversal(Node* node) {
        if (node != nullptr) {
            postorderTraversal(node->left);
            postorderTraversal(node->right);
            std::cout << node->data << " ";
        }
    }

    void preorderTraversalFull(Node* node) {
        if (node != nullptr) {
            std::cout << node->data << " ";
            if (node->left != nullptr) {
                preorderTraversalFull(node->left);
            }
            else {
                std::cout << "null ";
            }
            if (node->right != nullptr) {
                preorderTraversalFull(node->right);
            }
            else {
                std::cout << "null ";
            }
        }
    }

    void inorderTraversalFull(Node* node) {
        if (node != nullptr) {
            if (node->left != nullptr) {
                inorderTraversalFull(node->left);
            }
            else {
                std::cout << "null ";
            }
            std::cout << node->data << " ";
            if (node->right != nullptr) {
                inorderTraversalFull(node->right);
            }
            else {
                std::cout << "null ";
            }
        }
    }

    void postorderTraversalFull(Node* node) {
        if (node != nullptr) {
            if (node->left != nullptr) {
                postorderTraversalFull(node->left);
            }
            else {
                std::cout << "null ";
            }
            if (node->right != nullptr) {
                postorderTraversalFull(node->right);
            }
            else {
                std::cout << "null ";
            }
            std::cout << node->data << " ";
        }
    }

    void inorderTraversalThread(Node* node) {
        if (node != nullptr) {
            inorderTraversalThread(node->left);
            std::cout << node->data << " -> ";
            if (node->next != nullptr) {
                std::cout << node->next->data;
            }
            else {
                std::cout << "null";
            }
            std::cout << std::endl;
            inorderTraversalThread(node->right);
        }
    }

    void showTrunks(Trunk* p)
    {
        if (p == nullptr) {
            return;
        }

        showTrunks(p->prev);
        std::cout << p->str;
    }

    void printTree(Node* root, Trunk* prev = nullptr, bool isLeft = false)
    {
        if (root == nullptr) {
            return;
        }

        std::string prev_str = "    ";
        auto* trunk = new Trunk(prev, prev_str);

        printTree(root->right, trunk, true);

        if (!prev) {
            trunk->str = "---";
        }
        else if (isLeft)
        {
            trunk->str = ".---";
            prev_str = "   |";
        }
        else {
            trunk->str = "`---";
            prev->str = prev_str;
        }

        showTrunks(trunk);
        std::cout << " " << root->data << std::endl;

        if (prev) {
            prev->str = prev_str;
        }
        trunk->str = "   |";

        printTree(root->left, trunk, false);
    }

public:
    BinarySearchTree() {
        root = nullptr;
    }

    void insert(int value) {
        root = insertNode(root, value);
    }

    void remove(int value) {
        root = deleteNode(root, value);
    }

    void inorder() {
        inorderTraversal(root);
        std::cout << std::endl;
    }

    void preorder() {
        preorderTraversal(root);
        std::cout << std::endl;
    }

    void postorder() {
        postorderTraversal(root);
        std::cout << std::endl;
    }

    void preorderFull() {
        preorderTraversalFull(root);
        std::cout << std::endl;
    }

    void inorderFull() {
        inorderTraversalFull(root);
        std::cout << std::endl;
    }

    void postorderFull() {
        postorderTraversalFull(root);
        std::cout << std::endl;
    }

    void reverseInorderThread(Node* node, Node*& prev) {
        if (node == nullptr) {
            return;
        }

        reverseInorderThread(node->left, prev);

        node->next = prev;

        prev = node;

        reverseInorderThread(node->right, prev);
    }

    void reverseInorderThread() {
        Node* prev = nullptr;
        reverseInorderThread(root, prev);
    }

    void inorderThread() {
        inorderTraversalThread(root);
    }

    void print() {
        printTree(root);
    }
};

int main() {
    BinarySearchTree tree;

    for (int i = 0; i < 100; i++) {
        tree.insert(getRandomNumber(-100, 100));
    }

    tree.insert(10);
    tree.insert(3);
    tree.insert(-7);
    tree.insert(0);
    tree.insert(9);
    tree.insert(39);

    tree.print();

    tree.inorder();
    tree.postorder();
    tree.preorder();

    tree.inorderFull();
    tree.postorderFull();
    tree.preorderFull();

    tree.reverseInorderThread();
    tree.inorderThread();

    tree.print();

    system("pause");

    return 0;
}