ABC

#include <iostream>
#include <conio.h>
using namespace std;

struct NodABC {
	NodABC *fiu_st;
	int info;
	int inaltime;
	NodABC *fiu_dr;
};

NodABC*creareNod_ABC(int info_nou){

	NodABC *nod_nou = new NodABC;
	nod_nou->info = info_nou;
	nod_nou->fiu_st = NULL;
	nod_nou->fiu_dr = NULL;
	nod_nou->inaltime = 0;

	return nod_nou;
}

NodABC* cautare(NodABC* nod, int info_caut)
{
	NodABC* tmp = nod;
	while (tmp != NULL) {
		if (info_caut<tmp->info) {
			tmp = tmp->fiu_st;
		}
		else if (info_caut>tmp->info) {
			tmp = tmp->fiu_dr;
		}
		else {
			return tmp;
		}
	}
	return NULL;
}

NodABC* actualizare(NodABC* nod, int info_caut, int info_nou) {
	NodABC* tmp = cautare(nod, info_caut);
	if (tmp != NULL) {
		if (tmp->info == info_caut) {
			tmp->info = info_nou;
		}
	}
	return nod;
}
int inaltime_ABC(NodABC *ROOT) {
	if (ROOT == NULL)
		return -1;

	int stanga = inaltime_ABC(ROOT->fiu_st);
	int dreapta = inaltime_ABC(ROOT->fiu_dr);

	if (stanga > dreapta)
		return stanga + 1;
	else
		return dreapta + 1;
}

NodABC *inserare_ABC(NodABC *ROOT, int info_nou) {
	NodABC *nod_nou = creareNod_ABC(info_nou);

	if (ROOT == NULL) {
		ROOT = nod_nou;
	}
	else {
		NodABC *tmp = ROOT;
		NodABC *tata = NULL;

		while (tmp != NULL) {
			tata = tmp;

			if (tmp->info < info_nou) {
				tmp = tmp->fiu_dr;
			}
			else if (tmp->info > info_nou) {
				tmp = tmp->fiu_st;
			}
			else {
				cout << "Eroare, cheie dubla!\n";
				return ROOT;
			}
		}
		if (nod_nou->info < tata->info) {
			tata->fiu_st = nod_nou;
		}
		else {
			tata->fiu_dr = nod_nou;
		}
	}
	nod_nou->inaltime = inaltime_ABC(ROOT);

	return ROOT;
}


void preordine(NodABC *nod) {
	if (nod == NULL) return;
	else {
		cout << nod->info << " intm = " << nod->inaltime << endl;
		preordine(nod->fiu_st);
		preordine(nod->fiu_dr);
	}
}

void inordine(NodABC *nod) {
	if (nod == NULL) return;
	else {
		inordine(nod->fiu_st);
		cout << nod->info << " intm = " << nod->inaltime << endl;
		inordine(nod->fiu_dr);
	}
}

void postordine(NodABC* nod) {
	if (nod == NULL) return;
	else {
		postordine(nod->fiu_st);
		postordine(nod->fiu_dr);
		cout << nod->info << " intm = " << nod->inaltime << endl;
	}
}

NodABC* eliberare_ABC(NodABC* nod) {
	if (nod != NULL) {
		eliberare_ABC(nod->fiu_st);
		eliberare_ABC(nod->fiu_dr);
		delete nod;
	}
	else {
		cout << "Arbore vid!\n";
	}
	return NULL;
}

NodABC* caz1(NodABC* ROOT, NodABC* nod, NodABC* tata)
{
	if (nod == ROOT)
	{
		delete ROOT;
		ROOT = NULL;
		return ROOT;
	}
	else
	{
		if (nod == tata->fiu_st)
		{
			tata->fiu_st = NULL;
		}
		else
		{
			tata->fiu_dr = NULL;
		}
		delete nod;
		return ROOT;
	}
}
NodABC* caz2(NodABC* ROOT, NodABC* nod, NodABC* tata)
{
	if (ROOT == nod)
	{
		if (ROOT->fiu_st)
		{
			ROOT = ROOT->fiu_st;
		}
		else
		{
			ROOT = ROOT->fiu_dr;
		}

		return ROOT;
	}
	else
	{
		if (nod == tata->fiu_dr)
		{
			if (nod->fiu_dr != NULL)
			{
				tata->fiu_dr = nod->fiu_dr;
			}
			else
			{
				tata->fiu_dr = nod->fiu_st;
			}
		}
		else
		{
			if (nod->fiu_st != NULL)
			{
				tata->fiu_st = nod->fiu_st;
			}
			else
			{
				tata->fiu_st = nod->fiu_dr;
			}
		}
		delete nod;
	}

	return ROOT;
}
NodABC* caz3(NodABC* ROOT, NodABC* nod, NodABC* tata)
{
	NodABC* max = nod->fiu_st;
	NodABC* tatamax = nod;
	while (max->fiu_dr != NULL)
	{
		tatamax = max;
		max = max->fiu_dr;
	}
	nod->info = max->info;
	if (max == tatamax->fiu_st)
	{
		tatamax->fiu_st = max->fiu_st;
	}
	else tatamax->fiu_dr = max->fiu_dr;
	delete max;
	return ROOT;
}
NodABC* stergere_ABC(NodABC* ROOT, int cheie_sters)
{
	if (ROOT == NULL)
	{
		cout << "ABC vid\n";
		return ROOT;
	}
	else
	{
		NodABC* tmp = ROOT;
		NodABC* tata = NULL;
		while (tmp != NULL)
		{
			if (tmp->info == cheie_sters)
			{
				break;
			}
			else
			{
				tata = tmp;
				if (tmp->info<cheie_sters)
				{
					tmp = tmp->fiu_dr;
				}
				else
				{
					tmp = tmp->fiu_st;
				}
			}
		}
		if (tmp == NULL)
		{
			cout << "Nu s-a gasit cheia in arbore\n";
			return NULL;
		}
		else
		{
			if (tmp->fiu_st == NULL && tmp->fiu_dr == NULL)
			{
				ROOT = caz1(ROOT, tmp, tata);
			}
			else
				if ((tmp->fiu_st != NULL && tmp->fiu_dr == NULL) || (tmp->fiu_st == NULL && tmp->fiu_dr != NULL))
				{
					ROOT = caz2(ROOT, tmp, tata);
				}
				else
					if (tmp->fiu_st != NULL && tmp->fiu_dr != NULL)
					{
						ROOT = caz3(ROOT, tmp, tata);
					}
			return ROOT;
		}
	}
	return ROOT;
}
NodABC *stergere_frunze(NodABC* ROOT)
{
	NodABC *tmp = ROOT;
	NodABC *tata;

	if (tmp == NULL)return NULL;
	else {
		if (tmp->fiu_dr == NULL && tmp->fiu_st == NULL) {
			delete tmp;
			ROOT->fiu_dr = NULL;
			ROOT->fiu_st = NULL;
			return ROOT;
		}

		stergere_frunze(tmp->fiu_st);
		stergere_frunze(tmp->fiu_dr);
	}
}


int main() {
	int meniu;
	NodABC* ROOT = NULL;

	do
	{
		cout << "0. Iesire din program\n";
		cout << "1.Initializare\n";
		cout << "2.Inserare ABC\n";
		cout << "3.Traversare preordine\n";
		cout << "4.Traversare inordine\n";
		cout << "5.Traversare postordine\n";
		cout << "6.Actualizare\n";
		cout << "7.Cautare\n";
		cout << "8.Stergere\n";
		cout << "9.Eliberare\n";
		cout << "10.Op. Extinse\n";

		cout << "Alegeti varianta dorita (0-10):";
		cin >> meniu;

		cout << "\n\n";
		switch (meniu)
		{
		case 0:break;
		case 1:
		{
			cout << "1.Initializare\n";
			ROOT = NULL;
			break;
		}
		case 2:
		{
			cout << "2.Inserare ABC\n";
			int info_nou;
			cout << "Info_nou\n";
			cin >> info_nou;
			ROOT = inserare_ABC(ROOT, info_nou);
			break;
		}
		case 3:
		{
			cout << "3.Traversare preordine\n";
			preordine(ROOT);
			break;
		}
		case 4:
		{
			cout << "Traversare inordine\n";
			inordine(ROOT);
			break;
		}
		case 5:
		{
			cout << "5.Traversare postordine\n";
			postordine(ROOT);
			break;
		}
		case 6:
		{
			cout << "6.Actualizare\n";
			int info_caut, info_nou;
			cout << "Info caut\n";
			cin >> info_caut;
			cout << "Introduceti valoarea noua\n";
			cin >> info_nou;
			actualizare(ROOT, info_caut, info_nou);
			break;
		}
		case 7:
		{
			cout << "7.Cautare\n";
			int info_caut;
			cout << "Info caut\n";
			cin >> info_caut;
			NodABC* var = cautare(ROOT, info_caut);
			if (var != NULL)
			{
				cout << "Elementul " << var->info << " exista in arbore\n";
			}
			else
			{
				cout << "Elementul nu exista in arbore\n";
			}
			break;
		}
		case 8:
		{
			cout << "8.Stergere\n";
			int info_sters;
			cout << "Info_sters\n";
			cin >> info_sters;
			ROOT = stergere_ABC(ROOT, info_sters);
			break;
		}
		case 9:
		{
			cout << "9.Eliberare\n";
			ROOT = eliberare_ABC(ROOT);
			break;
		}
		case 10:
		{
			int x;
			do {
				cout << "\nApasati Enter pentru a sterge ecranul\n";
				_getch();
				system("cls");

				cout << "0. Iesire.\n"
					<< "1. Stergere frunze\n"
					<< "Stergere nivel\n";
				cin >> x;

				switch (x)
				{
				case 0: break;
				case 1:

					cout << "Stergere frunze\n";
					ROOT = stergere_frunze(ROOT);
					break;
				default:
					break;
				}

			} while (x != 0);
		}
		default:
		{
			cout << "Varianta gresita\n";
		}
		}
		cout << "\nApasati Enter pentru a sterge ecranul\n";
		_getch();
		system("cls");
	} while (meniu != 0);










	system("PAUSE");
	return 0;
}