#include <iostream>

using namespace std;

struct node {
	string number;
	string surname;
	node* left, * right;
};

struct node* add(string num, string name, node*& MyTree) //Фукция добавления звена в дерево
{
	if (MyTree == NULL) {
		MyTree = new node;
		MyTree->surname = name;
		MyTree->number = num;
		MyTree->left = MyTree->right = NULL;
	}
	else if (name < MyTree->surname)
		MyTree->left = add(num, name, MyTree->left);
	else
		MyTree->right = add(num, name, MyTree->right);
	return MyTree;
}

struct node* find(node*& Tree, string name) {

	if (Tree != NULL)
	{
		if (name == Tree->surname) {
			return Tree;
		}
		if (name < Tree->surname) {
			find(Tree->left, name);
		}
		if (name > Tree->surname) {
			find(Tree->right, name);
		}
	}
	else {
		return NULL;
	}
}

node* SearchMin(node* root) {
	if (root->left) {
		return SearchMin(root->left);
	}
	return root;
}

struct node* del(node*& Tree) {
	if (Tree != NULL)
	{
		del(Tree->left);                //Рекурсивная функция прохода по левому поддереву
		del(Tree->right);                //Рекурсивная функци для прохода по правому поддереву
		delete Tree;
		Tree = NULL;
	}
	cout << "Tree was deleted";
	return Tree;
}

node* Delete(string aName, node* root) {
	if (root == NULL) {
		cout << "This name isn`t in list" << endl;
		return root;
	}
	if (root->surname == aName) {
		if (root->left && root->right) {
			node* min = SearchMin(root->right);
			root->surname = min->surname;
			root->number = min->number;
			root->right = Delete(min->surname, root->right);
			return root;
		}
		if (root->left) {
			root->surname = root->left->surname;
			root->number = root->left->number;
			root->left = Delete(root->left->surname, root->left);
			return root;
		}
		if (root->right) {
			root->surname = root->right->surname;
			root->number = root->right->number;
			root->right = Delete(root->right->surname, root->right);
			return root;
		}
		root = NULL;
		return root;
	}
	if (root->surname > aName) {
		root->right = Delete(aName, root->right);
	}
	else {
		root->left = Delete(aName, root->left);
	}
	return root;
}

void show(node*& Tree)
{
	if (Tree != NULL)
	{
		show(Tree->left);
		cout << "Surname : " << Tree->surname << ", number : +380" << Tree->number << endl;
		show(Tree->right);
	}
}

int main()
{
	node* Tree = NULL;
	node* Temp_tree = NULL;
	int temp;
	string temp_number;
	string surname;

	bool program = true;
	while (program) {

		cout << "----------------------------------------------------" << endl;
		cout << "0 - enter new contact\n1 - show all contacts\n2 - find contact\n3 - delete contact\n4 - end program" << endl;
		cin >> temp;
		switch (temp) {

		case 0:
			cout << "Enter number +380";
			cin >> temp_number;
			cout << "Enter surname ";
			cin >> surname;

			Tree = add(temp_number, surname, Tree);
			break;
		case 1:
			if (Tree == NULL) {
				cout << "\nThe phonebook is empty\n";
			}
			if (Tree != NULL) {
				show(Tree);
			}
			break;
		case 2:
			cout << " Enter finding surname :";
			cin >> surname;
			Temp_tree = find(Tree, surname);

			if (Temp_tree) {
				cout << "Surname:" << Temp_tree->surname << endl << "Number: +380" << Temp_tree->number << endl;
			}
			else {
				cout << "Contact doesn`t find!" << endl;
			}
			break;
		case 3:
			cout << " Enter the surname of contact what you want to delete: ";
			cin >> surname;
			Tree = Delete(surname, Tree);
			cout << "Contact was deeleted!" << endl;
			break;
		case 4:
			Tree = del(Tree);
			program = false;
			break;
		default:
			break;
		}

	}

	del(Tree);
}