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

using namespace std;
struct node
{
	int key;//корень
	int count;//счётчик
	node *left;//указатель на левое поддерево
	node *right;//указатель на правое поддерево
}; node *tree;//указатель

void print_Tree(node *p, int level)
{
	if (p)
	{
		print_Tree(p->left, level + 1);
		for (int i = 0; i< level; i++) cout << "   ";
		cout << p->key << endl;
		print_Tree(p->right, level + 1);
	}
}
void ObhodEnd(node **w)//обратный обход
{
	if (*w != NULL)//если дерево не нулевое
	{
		ObhodEnd(&((**w).left));
		ObhodEnd(&((**w).right));
		cout << (**w).key << " " << endl;
	}

}
void ObhodBack(node **w)//симметричный обход
{
	if (*w != NULL)
	{
		ObhodBack(&((**w).left));
		cout << (**w).key << " ";
		ObhodBack(&((**w).right));
		cout << endl;
	}

}
void Obhodleft(node **w)//прямой обход
{
	if (*w != NULL)
	{
		cout << (**w).key << " ";
		Obhodleft(&((**w).left));
		Obhodleft(&((**w).right));
		cout << endl;
	}

}
void obhodnach(int el, node**p)
{
	if (*p == NULL)
	{
		*p = new (node);
		(**p).key = el;
		(**p).count = 1;
		(**p).left = NULL;
		(**p).right = NULL;
	}
	else
	{
		if (el<(**p).key)
			obhodnach(el, &((**p).left));
		else
		if (el>(**p).key)
			obhodnach(el, &((**p).right));
		else
			(**p).count = (**p).count + 1;

	}

}
void obhodright(int el, node**p)
{
	if (*p != NULL)
	{
		if (el<(**p).key)
			obhodright(el, &((**p).right));
		else
		if (el>(**p).key)
			obhodright(el, &((**p).left));
		else
			(**p).count = (**p).count + 1;
	}
	else
	{
		*p = new (node);
		(**p).key = el;
		(**p).count = 1;
		(**p).left = NULL;
		(**p).right = NULL;
	}
}
void obhodleft(int el, node**p)
{
	if (*p != NULL)
	{
		if (el<(**p).key)
			obhodleft(el, &((**p).left));
		else
		if (el>(**p).key)
			obhodleft(el, &((**p).right));
		else
			(**p).count = (**p).count + 1;
	}
	else
	{
		*p = new (node);
		(**p).key = el;
		(**p).count = 1;
		(**p).left = NULL;
		(**p).right = NULL;
	}
}
void Delete_1(node **r, node **q)//удаление узла
{
	node *s;

	if ((**r).right == NULL)
	{
		(**q).key = (**r).key; (**q).count = (**r).count;
		*q = *r;
		s = *r; *r = (**r).left; delete s;
	}
	else  Delete_1(&((**r).right), q);
}
void Delete(node **p, int k)//удаление листа
{
	node *q;

	if (*p == NULL) cout << "Вершина с заданным ключом не найдена!\n";
	else
	if (k<(**p).key) Delete(&((**p).left), k);
	else
	if (k>(**p).key) Delete(&((**p).right), k);
	else
	{
		q = *p;
		if ((*q).right == NULL) { *p = (*q).left; delete q; }
		else
		if ((*q).left == NULL) { *p = (*q).right; delete q; }
		else  Delete_1(&((*q).left), &q);
	}
}

//void Delete1(node **r,node **q)
//{
//		node *s;
//		if((**q).right==NULL)
//		{
//			(**q).key=(**r).key;
//			(**q).key=(**r).key;
//			(**q).count=(**r).count;
//			*q=*r;
//			s=*r;
//			*r=(**r).left;
//			delete s;
//		}
//		else
//			Delete1(&((**r).right),q);
//}
//
//void Delete(node **tree,int k)
//{
//	node*q;
//	if (*tree==NULL)
//		cout<<"Вершина с заданным ключом не найдена";
//	else
//	{
//		if(k<(**tree).key)
//			Delete(&((**tree).left),k);
//		else
//		{
//			if(k>(**tree).key)
//				Delete(&((**tree).right),k);
//			else
//			q=*tree;
//	if((*q).right==NULL)
//	{
//		*tree=(*q).left;
//		delete q;
//	}
//	else
//		if((*q).left==NULL)
//		{
//			*tree=(*q).right;
//			delete q;
//		}
//		else
//			Delete1(&((*q).left),&q);
//	}
//	}
//}
void buidtree()
{
	int el;
	tree = NULL;
	cout << "Введите лист дерева" << endl;
	cin >> el;
	while (el != 0)
	{
		obhodnach(el, &tree);
		/*obhodright(el,&tree);
		obhodleft(el,&tree);*/
		cin >> el;
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	char otv, otv2;
	setlocale(LC_ALL, "Russian");
	do
	{
		cout << "1.Построение дерева" << endl << "2.Удаление вершины дерева" << endl << "3.Вывод дерева на экран" << endl << "4.Добавление листа" << endl << "5.Прямой обход" << endl << "6.Обратный обход" << endl << "7.Симметричный обход" << endl << "0.Выход" << endl;
		cin >> otv;
		switch (otv)
		{
		case '1':
			buidtree();
			break;
		case '2':
			int k;
			cout << "Введите ключ удаляемой вершины" << endl;
			cin >> k;
			Delete(&tree, k);
			cout << "Вершина удалена" << endl;
			break;
		case '3':
			cout << "вывод дерева" << endl;
			print_Tree(tree, 0);

			break;
		case '4':
			int el;
			cin >> el;
			obhodnach(el, &tree);
			break;
		case '5':
			cout << "вывод дерева" << endl;
			Obhodleft(&tree);
			break;
		case '6':
			cout << "вывод дерева" << endl;
			ObhodEnd(&tree);
			break;
		case '7':
			cout << "вывод дерева" << endl;
			ObhodBack(&tree);
			break;
		default:
			cout << "Ошибка" << endl;
			break;
		}
	} while (otv != '0');
	cin.get();
	_getch();
	return 0;

}