BinTree

#include <iostream>
#include <conio.h>

using namespace std;

struct Node {
    int data;
    Node* leftChild;
    Node* rightChild;
    Node(float fdata) {
        data = fdata;
        leftChild = nullptr;
        rightChild = nullptr;
    }
    void displayNode() {
        cout << data << ' ';
    }
};

struct Tree {
    Node* root;

    Tree() {
        root = nullptr;
    }

    bool find(int data) {
        if (root != NULL) {
            Node* current = root;

            while (current->data != data) {
                if (data < current->data) current = current->leftChild;
                else current = current->rightChild;
                if (current == nullptr) return false;
            }

            return true;
        }
        else return false;
    }

    void insert(int data) {
        Node* newNode = new Node(data);
        if (root != NULL) {
            Node* current = root;
            Node* parent;

            while (true) {
                parent = current;
                if (data < current->data) {
                    current = current->leftChild;
                    if (current == NULL) {
                        parent->leftChild = newNode;
                        return;
                    }
                }
                else {
                    current = current->rightChild;
                    if (current == NULL) {
                        parent->rightChild = newNode;
                        return;
                    }
                }
            }
        }
        else {
            root = newNode;
        }
    }

    bool del(int data) {
        Node* current = root;
        Node* parent = root;
        bool isLeftChild = true;

        if (root != NULL) {
            while (current->data != data) {
                parent = current;
                if (data < current->data) {
                    isLeftChild = true;
                    current = current->leftChild;
                }
                else {
                    isLeftChild = false;
                    current = current->rightChild;
                }
                if (current == NULL) return false;
            }
        }
        else return false;

        // Нет потомков
        if (current->leftChild == nullptr && current->rightChild == nullptr) {
            if (current == root) root = nullptr;
            else if (isLeftChild) parent->leftChild = nullptr;
            else parent->rightChild = nullptr;
        }
        // Один потомок. Если нет левого потомка заменяем правым поддеревом
        else if (current->leftChild == nullptr) {
            if (current == root) root = current->rightChild;
            else if (isLeftChild) parent->leftChild = current->rightChild;
            else parent->rightChild = current->rightChild;
        }
        // Один потомок. Если нет правого потомка заменяем левым поддеревом
        else if (current->rightChild == nullptr) {
            if (current == root) root = current->leftChild;
            else if (isLeftChild) parent->leftChild = current->leftChild;
            else parent->rightChild = current->leftChild;
        }
        // Два потомка
        else {
            Node* success = getSuccessor(current);
            if (current == root) root = success;
            else if (isLeftChild) parent->leftChild = success;
            else parent->rightChild = success;
            success->leftChild = current->leftChild;
        }
        return true;
    }

    // Обходы
    // Симметричный
    void inOrder(Node* localRoot) {
        if (!localRoot)
            return;
        inOrder(localRoot->leftChild);
        cout << localRoot->data << ' ';
        inOrder(localRoot->rightChild);
    }
    // Прямой
    void preOrder(Node* localRoot) {
        if (!localRoot)
            return;
        cout << localRoot->data << ' ';
        preOrder(localRoot->leftChild);
        preOrder(localRoot->rightChild);
    }
    // Обратный
    void postOrder(Node* localRoot) {
        if (!localRoot)
            return;
        postOrder(localRoot->leftChild);
        postOrder(localRoot->rightChild);
        cout << localRoot->data << ' ';
    }
    void Order(string l) {
        if (l == "in") inOrder(root);
        else if (l == "pre") preOrder(root);
        else if (l == "post") postOrder(root);
        else return;
    }

    // Поиск приемника для двух потомков
    Node* getSuccessor(Node* delNode) {
        Node* successorParent = delNode;
        Node* successor = delNode;
        Node* current = delNode->rightChild;
        while (current != NULL) {
            successorParent = successor;
            successor = current;
            current = current->leftChild;
        }

        if (successor != delNode->rightChild) {
            successorParent->leftChild = successor->rightChild;
            successor->rightChild = delNode->rightChild;
        }
        return successor;
    }

    int F2p() {
        int c = 0;
        c = prepreOrder(root, c);
        return c;
    }

    int prepreOrder(Node* localRoot, int c) {
        if (!localRoot)
            return c;
        if (getSuccessor(localRoot)) c++;
        prepreOrder(localRoot->leftChild, c);
        prepreOrder(localRoot->rightChild, c);
    }

};

void main() {
    setlocale(LC_ALL, "Russian");

    Tree* tree = new Tree;

    for (int i = 0; i <= 10; i++) {
        tree->insert(rand() % 100 - 50);
    }

    cout << "Прямой обход :" << endl;
    tree->Order("pre");
    cout << "\nОбратный обход :" << endl;
    tree->Order("post");
    cout << "\nОбход в порядке возрастания :" << endl;
    tree->Order("in");

    int r = rand() % 100 - 50;
    bool fl = false;
    while (!fl) {
        if (tree->find(r)) {
            tree->del(r);
            fl = true;
            cout << "\n\nПоиск и удаление элемента = " << r << " завершено" << endl;
        }
        else r = rand() % 100 - 50;
    }

    cout << "\nКоличество узлов с двумя потомками = "<< tree->F2p() << endl;

    _getch();
}