#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;
}