#include "stdafx.h"
#include <iostream>


using namespace std;

struct Tree {
    int field;           // поле данных
    struct Tree *left;  // левый потомок
    struct Tree *right; // правый потомок
};


// Префиксный обход
void traversalPrefix(Tree *tree) {
    if (tree != NULL) { //Пока не встретится пустой узел
        cout << tree->field << ' '; //Отображаем корень дерева
        traversalPrefix(tree->left); //Рекурсивная функция для левого поддерева
        traversalPrefix(tree->right); //Рекурсивная функция для правого поддерева
    }
}
// Инфиксный обход
void traversalInfix(Tree *tree) {
    if (tree != NULL) { //Пока не встретится пустой узел
        traversalInfix(tree->left); //Рекурсивная функция для левого поддерева
        cout << tree->field << ' '; //Отображаем корень дерева
        traversalInfix(tree->right); //Рекурсивная функция для правого поддерева
    }
}

// Постфиксный обход
void traversalPostfix(Tree *tree) {
    if (tree != NULL) { //Пока не встретится пустой узел
        traversalPostfix(tree->left); //Рекурсивная функция для левого поддерева
        traversalPostfix(tree->right); //Рекурсивная функция для правого поддерева
        cout << tree->field<<' '; //Отображаем корень дерева
    }
}

struct Tree* addValue(int x, Tree *tree) {
    if (tree == NULL) { // Если дерева нет, то формируем корень
        tree = new Tree; // память под узел
        tree->field = x;   // поле данных
        tree->left = NULL;
        tree->right = NULL; // ветви инициализируем пустотой
    }
    else  if (x < tree->field)   // условие добавление левого потомка
        tree->left = addValue(x, tree->left);
    else    // условие добавление правого потомка
        tree->right = addValue(x, tree->right);
    return(tree);
}


Tree* deleteNode(Tree* node, int val) {
    if (node == NULL)
        return node;

    if (val == node->field) {

        Tree* tmp;
        if (node->right == NULL)
            tmp = node->left;
        else {

            Tree* ptr = node->right;
            if (ptr->left == NULL) {
                ptr->left = node->left;
                tmp = ptr;
            }
            else {
                Tree* pmin = ptr->left;
                while (pmin->left != NULL) {
                    ptr = pmin;
                    pmin = ptr->left;
                }
                ptr->left = pmin->right;
                pmin->left = node->left;
                pmin->right = node->right;
                tmp = pmin;
            }
        }

        delete node;
        return tmp;
    }
    else if (val < node->field)
        node->left = deleteNode(node->left, val);
    else
        node->right = deleteNode(node->right, val);
    return node;
}

int main()
{
    setlocale(LC_ALL, "ru");
    Tree *tree = NULL;
    int n;
    int value;
    cout << "Как много элементов вы хотите добавить?" << endl;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cout << "Введите значения узла" << endl;
        cin >> value;
        tree = addValue(value, tree);
    }
    cout << "Префиксный обход дерева:" << endl;
    traversalPrefix(tree);
    cout << endl;
    cout << "Инфиксный обход дерева:" << endl;
    traversalInfix(tree);
    cout << endl;
    cout << "Постфиксный обход дерева:" << endl;
    traversalPostfix(tree);
    cout << endl;
    cout << "Введите значение узла, которое необходимо удалить" << endl;
    cin >> value;
    deleteNode(tree, value);
    traversalPrefix(tree);
    system("pause");
    return 0;
}