#include <iostream>
#include <stdio.h>
#include <time.h>

using namespace std;

class Wezel
{
public:
	int klucz;
	Wezel* lewy;
	Wezel* prawy;
	char tablica[256];

};
Wezel* root;
class Drzewo
{
public:
void wstaw(int klucz)
	{
		Wezel *wskWezel = new Wezel;
		wskWezel->lewy = NULL;
		wskWezel->prawy = NULL;
		wskWezel->klucz = klucz;
		Wezel *rodzic = NULL;
		Wezel *r = root;
		int i = 0;
		while (i < 256)
		{
			wskWezel->tablica[i] = (rand() % 26) + 97;
			i++;
		}
		while (r != NULL)
		{
			if (r->klucz == klucz)return;
			rodzic = r;
			if (r->klucz > klucz)
				r = r->lewy;
			else
				r = r->prawy;
		}
		if (root == NULL)
			root = wskWezel;
		else if (rodzic->klucz > klucz)
			rodzic->lewy = wskWezel;
		else
			rodzic->prawy = wskWezel;
		return;
	}
Wezel* wyszukaj(int klucz)
{
	Wezel *r = root;
	while ((r != NULL) && (klucz != r->klucz))
	{
		if (r->klucz < klucz)
			r = r->prawy;
		else
			r = r->lewy;
	}
	if (r)
		cout <<"Istnieje element" << endl;
	else
		cout << "Nie istnieje element" << endl;
	return r;
}
void wstaw_wiele(int X)
{
		int losowa;
		for (int i = 0; i < X; i++)
			{
			losowa = ((rand() % 1000) * 1000) + (rand() % 990) + 10;
				wstaw(losowa);
			}
}
void usun(int klucz)
{
	Wezel *rodzic = NULL;
	Wezel *r = root;
	while ((r != NULL) && (klucz != r->klucz))
	{
		rodzic = r;
		if (r->klucz < klucz)
			r = r->prawy;
		else
			r = r->lewy;
	}
	if (r == NULL)
	{
		cout << "usuwany obiekt nie istnieje."<<endl;
		return;
	};

	if ((r->prawy == NULL) && (r->lewy == NULL))
	{
		if (r == root)
		{
			root = NULL;
			return;
		}
		if (rodzic->prawy == r)
			rodzic->prawy = NULL;
		else
			rodzic->lewy = NULL;
		return;
	}
	if (r->prawy == NULL)//usuwany wezel  ma tylko lewe podrzewo
	{
			if (rodzic->prawy == r)
				rodzic->prawy = r->lewy;
			else
				rodzic->lewy = r->lewy;
			return;
	}
	if (r->lewy == NULL)//wezel  ma tylko prawe podrzewo
	{
			if (rodzic->prawy == r)
				rodzic->prawy = r->prawy;
			else
				rodzic->lewy = r->prawy;
			return;
	}
	//usuwany wezel  ma oba poddrzewa
		Wezel *prerodzic = r;
		Wezel *dziecko = r->lewy;
		while (dziecko->prawy != NULL)
		{
			prerodzic = dziecko;
			dziecko = dziecko->prawy;
		}
		if (dziecko == r->lewy)//poprzednik jest lewym potomkiem usuwanego wezla
		{
			if (rodzic->prawy == r)
				rodzic->prawy = dziecko;
			else
				rodzic->lewy = dziecko;
			return;
		}
		//poprzednik nie jest lewym potomkiem r, lecz jego wnukiem lub praprawnukiem
		Wezel *granddziecko = dziecko->lewy;//ewentualny potomek poprzednika
		//adopcja potomstwa poprzednika przez jego rodzic
		if (prerodzic->prawy = dziecko)
			prerodzic->prawy = granddziecko;
		else
			prerodzic->lewy = granddziecko;

		dziecko->lewy = r->lewy;//adopcja potomstwa usuwanego wezle przez jego porzednika

		//adopcja poprzednika przez rodzica usuwanego wezla
		if (rodzic->prawy = r)
			rodzic->prawy = dziecko;
		else
			rodzic->lewy = dziecko;
		return;
};
void Preorder(Wezel *root)
	{
		if (root != NULL)
		{
			cout << root->klucz << endl;
			Preorder(root->lewy);
			Preorder(root->prawy);
		}
		return;
	}
	void Inorder(Wezel *root)
	{
		if (root == NULL)
		{
			Inorder(root->lewy);
			cout << root->klucz << endl;
			Inorder(root->prawy);
		}
		return;
	}
	void Postorder(Wezel *root)
	{
		if (root != NULL)
		{
			Postorder(root->lewy);
			Postorder(root->prawy);
			cout << root->klucz << endl;

		}
		return;

	}
};
int main()
{
	srand(time(NULL));
	int X, k1, k2, k3, k4;

	FILE* fp = fopen("inlab03.txt", "r");
	if (fp == NULL)
		return -1;
	fscanf(fp, "%d %d %d %d %d", &X, &k1, &k2, &k3, &k4);
	fclose(fp);

	clock_t begin, end;
	double time_spent;
	begin = clock();

	root = NULL;
	Drzewo BST;
	BST.usun(k1);
	BST.wstaw_wiele(X);
	BST.wstaw(k1);
	BST.wstaw(k2);
	BST.wstaw(k3);
	BST.wstaw(k4);
	BST.usun(k1);
	BST.wyszukaj(k1);
	BST.usun(k2);
	BST.usun(k3);
	BST.usun(k4);

	end = clock();
	time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

	cout << "Czas pracy programu: " << time_spent << endl;
	getchar();
	return 0;
}