#include "bintree.h"

// Выбор пользователя в меню
enum user_choice
{
	INSERT,
	DELETE,
	FIND,
	FINDNEAR,
	PRINT,
	LOAD,
	SAVE,
	EXIT
};

user_choice menu();
void insert();
void del();
void find();
void findnear();
void print();
void load();
void save();
int GetNum();

BinTree * btree;

int main()
{
//	locale::global(locale(""));
	system("chcp 1251 >> nul");

	while (true)
	{
		switch (menu())
		{
			case INSERT:
				insert();
				break;
			case DELETE:
				del();
				break;
			case FIND:
				find();
				break;
			case FINDNEAR:
				findnear();
				break;
			case PRINT:
				print();
				break;
			case LOAD:
				load();
				break;
			case SAVE:
				save();
				break;
			case EXIT:
				delete btree;
				return 0;
		}
	}

	return 0;
}

// Меню
user_choice menu()
{
	while (true)
	{
		cout << "Меню:" << endl
			<< "1 - Включить новый элемент" << endl
			<< "2 - Удалить элемент" << endl
			<< "3 - Найти элемент" << endl
			<< "4 - Найти близкий элемент" << endl
			<< "5 - Вывести дерево" << endl
			<< "6 - Загрузить из файла" << endl
			<< "7 - Сохранить в файл" << endl
			<< "0 - Выход" << endl
			<< "Ваш выбор: ";
		int choice = _getch();
		if (choice == 0 || choice == 0xE0)
		{
			_getch();
		}
		else
		{
			cout << static_cast<char> (choice) << endl;
			switch (choice)
			{
				case '1':
					return INSERT;
				case '2':
					return DELETE;
				case '3':
					return FIND;
				case '4':
					return FINDNEAR;
				case '5':
					return PRINT;
				case '6':
					return LOAD;
				case '7':
					return SAVE;
				case '0':
					return EXIT;
			}
		}
		cout << endl
			<< "Будьте внимательней!" << endl << endl;
	}
}

//добавление узла 
void insert(void)
{
	int		iKey;
	char	sInfo[256];

	if (btree == NULL)
		btree = new BinTree();

	//запросим ключ
	cout << "Введите ключ: ";	
	iKey = GetNum();

	if (btree->FindNode(iKey))
	{
		cout << "Такой ключ уже есть" << endl;
		return;
	}
	
	//запросим Info
	cout << "Введите строку: ";
	cin.ignore();
	do
	{
		cin.getline(sInfo, 256);
	}while(0==sInfo[0]);				//строка должна быть непустой!
	
	btree->InsertNode(iKey, sInfo);		//заносим в дерево
	
	cout << "Элемент добавлен" << endl;
}

//удаление узла
void del(void)
{
	int		iKey;

	if (btree)							//проверим на существование дерева
	{
		//запросим ключ
		cout << "Введите ключ: ";	
		iKey = GetNum();

		if (btree->DelNode(iKey))		//удаляем
			cout << "Узел удален" << endl;
		else
			cout << "Ключ не найден" << endl;
	}
	else
		cout << "Нет дерева" << endl;
}

void find()
{
	int		iKey;

	if (btree)							//проверим на существование дерева
	{
		//запросим ключ
		cout << "Введите ключ: ";	
		iKey = GetNum();

		if (!btree->PrintNode(iKey))	//находим и выводим
			cout << "Ключ не найден" << endl;
	}
	else
		cout << "Нет дерева" << endl;
}

void findnear()
{
	int		iKey;

	if (btree)							//проверим на существование дерева
	{
		//запросим ключ
		cout << "Введите ключ: ";	
		iKey = GetNum();

		btree->SearchNearNode(iKey);	//ищем ближайшего не равного
	}
	else
		cout << "Нет дерева" << endl;
	
}

void print()
{
	if (btree)							//проверим на существование дерева
		btree->OutTree();
	else
		cout << "Нет дерева" << endl;
}

//ввод числа
int GetNum(void)
{
	int		a = -1;
	cin >> a;
	while ( !( cin.good() || cin.eof() ) || ( a < 0 ) )
	{
		cout << "Введите число! " << endl;
		cin.clear();
		cin.ignore();
		cin >> a;
	}
	return a;
}

void load(void)
{
	delete btree;
	btree = new BinTree();
	btree->LoadFromFile("tree.txt");
	cout << "Файл загружен" << endl;
}

void save(void)
{
	if (btree)
	{
		btree->SaveToFile("tree.txt");
		cout << "Файл сохранен" << endl;
	}
	else
		cout << "Нет дерева" << endl;
}

#include <locale>
#include <limits>
#include <fstream>
#include <iostream>
#include <conio.h>

using namespace std;

struct Node
{
	int		key;
	Node	*left;
	Node	*right;
	Node	*parent;
	char	*info;
};

class BinTree
{
public:
	// Конструктор
	BinTree(void){root = NULL;}
	~BinTree(void);
	bool FindNode(int iKey);
	bool InsertNode(int key, char * info);
	bool PrintNode(int key);
	bool DelNode(int key);
	void outReverse(void);
	void SearchNearNode(int iKey);
	void OutTree(void);
	void LoadFromFile(char *sName);
	void SaveToFile(char * sName);

private:
	Node * root;
	Node * FindNode(Node * node, int iKey);
	Node * CreateNode(int iKey, char * sInfo);
	void FreeNode(Node *node);
	Node * NodeMinimum(Node *node);
	Node * NodeMaximum(Node *node);
	Node * NodeNext(Node * node);
	Node * NodePrev(Node * node);
	void OutNode(Node * node);
	ofstream * SaveNode(ofstream *out, Node *node);
};

void BinTree::FreeNode(Node *node)
{
	if (node)
	{
		delete [] node->info;			//память поля инфо
		BinTree::FreeNode(node->left);	//левого потомка
		BinTree::FreeNode(node->right);	//правого потомка
		delete node;					//память самого узла
	}
}

BinTree::~BinTree()
{
	BinTree::FreeNode(root);
}

//создание узла дерева
Node * BinTree::CreateNode(int iKey, char * sInfo)
{
	//создаем
	Node * node = new Node;

	//обнулим указатели на потомков
	node->left = NULL;
	node->right = NULL;
	//на родителя
	node->parent = NULL;

	//заполняем поля
	node->key = iKey;						//ключ
	node->info = new char[strlen(sInfo)+1];	//Info
	strcpy(node->info, sInfo);
	return node;
}

//вставка узла с указанным ключом и данными
bool BinTree::InsertNode(int iKey, char * sInfo)
{
	Node	*node = root;						//текущий узел, начинаем с корня
	Node	*nodeParent;						//указатель на родителя
	Node	*nodeNew = CreateNode(iKey, sInfo);	//создаем новый узел
	// Пока ещё есть узлы, которые надо просмотреть, 
	// то есть пока мы не добрались до “листочков” дерева
	while (node)
	{
		// Выбираем узел, в зависимости от того,
		// меньше или больше вставляемый ключ относительно текущего узла
		nodeParent = node;
		if (iKey < node->key)
			node = node->left;
		else if (iKey > node->key)
			node = node->right;
		//если равно, то говорим, что такой ключ есть
		else
			return false;
	}
								//добавляем узел в дерево
	if (root == NULL)			//если в дереве ещё нет узлов
		root = nodeNew;			//то запомним, как корень
	else
	{
		// Если ключ узла, который мы хотим вставить, 
		// меньше ключа узла, потомком которого должна стать 
		// вставляемый узел
		if (iKey < nodeParent->key)
			nodeParent->left = nodeNew;	//то добавить в дерево как левого потомка
		else
			nodeParent->right = nodeNew;//иначе добавить в дерево как правого потомка
		//запомним родителя
		nodeNew->parent = nodeParent;
	}
	return true;				//узел добавлен
}

//поиск узла с указанным ключом в дереве, начиная с указанного
bool BinTree::FindNode(int iKey)
{
	return (NULL != BinTree::FindNode(root, iKey));
}

//поиск узла с указанным ключом в дереве, начиная с указанного
Node* BinTree::FindNode(Node * node, int iKey)
{
	// Если узел равен NULL, то нечего в нем искать. Так же и возвращаем. 
	// Это нужно для поиска по несуществующим потомкам
	if (node == NULL)
		return node; 
	
	// Если нашли, то возвращаем указатель на найденный узел.
	if (node->key == iKey)
		return node;
	
	// Если ключ найденного узла больше того, который мы ищем
	if (node->key > iKey)
		// То искать в левом поддереве
		return BinTree::FindNode(node->left, iKey);
	else 
		// Иначе в правом поддереве
		return BinTree::FindNode(node->right, iKey);
}

//Удаление узла по ключу
//Необходимо сохранить свойство упорядоченности. 
//При удалении возможны три случая: 
//1) у удаляемого узла нет потомков, 
//2) у удаляемого узла есть один потомок и 
//3) у удаляемого узла два потомка. 
//Если потомков нет, то узел можно просто удалить. 
//Если потомок один, то удаляемый узел можно “вырезать”, 
//указав его родителю в качестве потомка единственного 
//имеющегося потомка удаляемого узла. 
//Если же потомков два, требуются дополнительные действия. 
//Нужно найти следующий за удаляемым (по порядку ключей) узлом, 
//Скопировать его содержимое (ключ и данные) в удаляемый узел 
//и удалить найденный узел (у него не будет левого потомка). 
bool BinTree::DelNode(int iKey)
{
	//ищем узел с указанным ключом
	Node	*node = root;
	Node	*del,*nodeParent,*nodeNext;

	while (node)
	{
		// Выбираем узел, в зависимости от того,
		// меньше или больше вставляемый ключ относительно текущего узла
		nodeParent = node;			//запоминаем родителя
		if (iKey < node->key)
			node = node->left;		//идем налево
		else if (iKey > node->key)
			node = node->right;		//направо
		//равно - удаляем узел
		else
		{
			// Если потомков не более одного
			if ((node->left == NULL) || (node->right == NULL))
				del = node;				// физически удаляем текущий узел
			else
				del = BinTree::NodeMinimum(node->right);	// Иначе самого левого потомка правого потомка
															// другими словами, переносим следующего по значению ключа
															// на место удаляемого
  
			if (del->left)				// Пытаемся найти хоть одного потомка
				nodeNext = del->left;
			else
				nodeNext = del->right;	// Или NULL
  
			// Если удаляем корень дерева, надо указать новый корень дерева
			if (del == root)
				root = nodeNext;
			else
			{
				// Указываем родителю удаляемого узла в качестве потомка 
				// потомок удаляемого узла
				if (nodeParent->left == del)	//если удаляемый - левый потомок
					nodeParent->left = nodeNext;//то меняем ссылку на следующего
				else
					nodeParent->right = nodeNext;//для правого
				nodeNext->parent = nodeParent;	//ссылка на родителя
			}

			if (del != node)			//удаляемый узел с двумя потомками
			{
				delete [] node->info;	//освободим память под Info
				node->key = del->key;	//скопировать ключ
				node->info = del->info;	//Info со следующего узла
			}
			else						//с одним или ни одного потомка
				delete [] del->info;	//освободим память под Info
			delete del;					//освободим память узла

			return true;				//узел найден и удален
		}
	}
	return false;		//узел не найден - говорим об этом
}

//Поиск самого левого узла для данного
Node *  BinTree::NodeMinimum(Node *node)
{
	while (node->left != NULL)	// Пока есть левый потомок
		node = node->left;		// Перейти к нему
	return node;
}

//Поиск самого правого узла
Node *  BinTree::NodeMaximum(Node *node)
{
	while (node->right != NULL)	// Пока есть правый потомок
		node = node->right;		// Перейти к нему
	return node;
}

//поиск очередного узла по возрастанию ключей (для поиска ближайшего)
Node * BinTree::NodeNext(Node * node)
{
	Node   *nodeParent;
	// Если правое поддерево не пусто, то возвратить 
	// узел с минимальным значением ключа из правого поддерева
	if (node->right != NULL)
		return BinTree::NodeMinimum(node->right);
  
	nodeParent = node->parent;
	// Перебирать родителей, пока не найден узел, 
	// являющаяся левым потомком своего родителя 
	// или пока не закончатся родители.
	while (nodeParent && (node == nodeParent->right))
	{
		node = nodeParent;
		nodeParent = nodeParent->parent;
	}
   
	// Возвратить родителя узла, являющегося левым потомком своего родителя
	return nodeParent;
}
//поиск очередного узла по убыванию ключей (для поиска ближайшего)
Node * BinTree::NodePrev(Node * node)
{
	Node   *nodeParent;
	// Если левое поддерево не пусто, то возвратить 
	// узел с максимальным значением ключа из левого поддерева
	if (node->left != NULL)
		return NodeMaximum(node->left);
  
	nodeParent = node->parent;
	// Перебирать родителей, пока не найден узел, 
	// являющаяся правым потомком своего родителя 
	// или пока не закончатся родители.
	while (nodeParent && (node == nodeParent->left))
	{
		node = nodeParent;
		nodeParent = nodeParent->parent;
	}
   
	// Возвратить родителя узла, являющегося правым потомком своего родителя
	return nodeParent;
}

//поиск элемента, наиболее близкого по значению к заданному ключу, 
//но не совпадающему с ним.
//из-за упорядоченности нам надо найти родителя узла, а также ближайшие
//к нему слева и справа. И сравнить их! 
void BinTree::SearchNearNode(int iKey)
{
	Node	*current = root;
	Node	*left, *right, *parent;
	int		keyLeft=-1, keyRight=-1;
   
	if (root == NULL)
	{
		cout << "Дерево отсутствует" << endl;
		return;
	}
	while(current != NULL) 
	{
		if(iKey == current->key)
			break;            //нашли
		else 
		{
			parent = current;
			current = (iKey < current->key) ?   //ветвимся
				current->left : current->right;
		}
	}
	if (current != NULL)         //нашли?
	{
		left = BinTree::NodePrev(current);	//ищем ближайшего слева
		right = BinTree::NodeNext(current);	//справа
	}
	else				//не нашли
	{					//рассматриваем родителя
		if (iKey < parent->key)		//или слева от него
		{
			left = BinTree::NodePrev(parent);	//ближайший до родителя
			right = parent;						//родитель
		}
		else						//или справа
		{
			left = parent;						//родитель
			right = BinTree::NodeNext(parent);	//ближайший справа
		}
	}
	//определимся, что же мы нашли
	if (left && (left != current))		//есть слева, не равный текущему?
		keyLeft = left->key;			//ключ слева
	if (right && (right != current))	//есть справа?
		keyRight = right->key;			//ключ справа
	if ((keyLeft == -1) && (keyRight == -1))	//ничего нет (только корень)?
	{
		cout << "Ближайший не равный найти невозможно" << endl;
		return;
	}
	else if (keyLeft == -1)				//слева нет (самый крайний слева)?
		current = right;				//ближайший - справа
	else if (keyRight == -1)			//справа нет?
		current = left;					//ближайший - слева
	else								//есть оба
	{									//смотрим, кто ближе
		if (abs(iKey - keyLeft) <= abs(iKey - keyRight))
			current = left;
		else
			current = right;
	}
	cout << "Ближайший ключ = " << current->key << ", info = " << current->info << endl;
}

//вывод одного узла
void BinTree::OutNode(Node * node)
{
	cout << "Key = " << node->key << ", Info = " << node->info << endl;
}

//находим и выводим
bool BinTree::PrintNode(int iKey)
{
	Node * node = BinTree::FindNode(root, iKey);

	if (node)
	{
		BinTree::OutNode(node);
		return true;
	}
	return false;
}

void BinTree::OutTree(void)
{
	for(Node * node=NodeMaximum(root); node; node=NodePrev(node))
		OutNode(node);
}


ofstream * BinTree::SaveNode(ofstream *out, Node *node)
{
	*out << node->key << endl << node->info << endl;
	if (node->left != NULL)
		SaveNode(out, node->left);
	if (node->right != NULL)
		SaveNode(out, node->right);
	return out;
}

void BinTree::SaveToFile(char * sName)
{
	ofstream out(sName) ;
   
	if (root != NULL)
	{
		if (out.is_open())			//создался?
		{
			SaveNode(&out, root);
			out.close();			//файл закрываем
		}
		else
			cout << "Ошибка создания файла" << endl;
	}
	else
		cout << "Дерево отсутствует" << endl;
}

void BinTree::LoadFromFile(char *sName)
{
	fstream		in;
	int			iKey;
	char		str[256];

	in.open(sName, ios::in);
 
	if(!in.is_open()) 
	{
		cout << "Файл не найден" << endl;
		return;
	}

	while(!in.eof()) //пока не конец файла
	{
		in.getline(str,256); //читаем очередную строку в str
		if (in.eof())
			break;
		iKey = atoi(str);
		in.getline(str,256); //читаем очередную строку в str
		InsertNode(iKey, str);
	}
	in.close();
}