#include <iostream>
#include <cstdlib>
#include <ctime>
#include <conio.h>
using namespace std;
 
struct elem {
	int labela;
	int firstchild, nextsibling;
};
 
struct tstablo {
	elem elements[1000];
	int first;
};
tstablo *stablo = new tstablo;
int broj_cvorova = 0;
 
int parentT (int n, tstablo *stablo) {
	if (stablo->first == n)
		return -1;
	for (int i = 0; i < 1000; i++) {
		if (stablo->elements[i].firstchild == n)
			return i;
		if(stablo->elements[i].nextsibling == n)
			return parentT(i,stablo);
	}
	return -2;
}
 
int firstchildT(int n, tstablo *stablo) {
	if (stablo->elements[n].firstchild == -1)
		return -1;
	return stablo->elements[n].firstchild;
}
 
int nextsiblingT(int n, tstablo *stablo) {
	if (stablo->elements[n].nextsibling == -1)
		return -1;
	return stablo->elements[n].nextsibling;
}
 
int labelT (int n, tstablo *stablo) {
	if (parentT(n, stablo) != -2)
		return stablo->elements[n].labela;
}
 
int rootT (tstablo *stablo) {
	return stablo->first;
}
 
int createT (int x, int n, tstablo *stablo) {
	if (parentT(n, stablo) == -2) {
		cout << "Ne postoji cvor u stablu na toj poziciji" << endl;
		return -1;
	}
	if (stablo->elements[n].firstchild == -1) {
		stablo->elements[n].firstchild = x;
		stablo->elements[x].firstchild = -1;
		stablo->elements[x].nextsibling = -1;
		stablo->elements[x].labela = rand() % 100 + 1;
		return 1;
	}
 
	int tekuci;
	int brat;
	brat = stablo->elements[n].firstchild;
	while (brat != -1) {
		tekuci = brat;
		brat = stablo->elements[tekuci].nextsibling;
	}
	stablo->elements[tekuci].nextsibling = x;
	stablo->elements[x].firstchild = -1;
	stablo->elements[x].nextsibling = -1;
	stablo->elements[x].labela = rand() % 100 + 1;
	return 1;
}
 
void changelabelT (int x, int n, tstablo *stablo) {
	if (parentT(n, stablo) != -2)
		stablo->elements[n].labela = x;		
}
 
int deleteT (int n, tstablo *stablo) {
	int roditelj, brat, dijete;
	roditelj = parentT(n, stablo);
	brat = stablo->elements[roditelj].firstchild;
	if (parentT(n, stablo) == -2) {
		return -1;
	}
	while (stablo->elements[n].firstchild != -1) {
		dijete = stablo->elements[n].firstchild;
		deleteT (dijete, stablo);
	}
	if (n == brat)
		stablo->elements[parentT(n,stablo)].firstchild =stablo->elements[n].nextsibling;
	else if (stablo->elements[n].nextsibling != -1)
		stablo->elements[brat].nextsibling = stablo->elements[n].nextsibling;
	stablo->elements[n].labela = 0;
	broj_cvorova--;
	return 1;
}
 
 
void initT (int x, tstablo *stablo) {
	int oznaka;
	for (int i = 0; i < 1000; i++) {
		stablo->elements[i].firstchild = -1;
		stablo->elements[i].nextsibling = -1;
		stablo->elements[i].labela = 0;
	}
	stablo->first = x;
	cout << "Unesite labelu(oznaku) korijena: ";
	cin >> oznaka;
	stablo->elements[x].labela = oznaka;
}
 
void ispis(tstablo *stablo) {
	for(int i = 0; i < 1000; i++) {
		if (stablo->elements[i].labela != 0)
			cout << i << " ::::: " << stablo->elements[i].labela << " ::::: "
			 	 << stablo->elements[i].firstchild << " ::::: "
			 	 << stablo->elements[i].nextsibling << endl;
	}
	cout << endl << endl;
}
 
int main() {
	srand(time(0));
	int pozicija;
	initT(0, stablo);
	broj_cvorova++;
	ispis(stablo);
	cout << "KREIRANJE STABLA OD 10 ELEMANTA" << endl;
	getch();
	for (int i = 1; i <= 9;) {
		broj_cvorova++;
		system("cls");
		cout << i << ". pozicija u polju: " << endl;
		cout << "Unesite poziciju cvora gdje ce se kreirati dijete cvora: ";
		cin >> pozicija;
		if(createT(i,pozicija,stablo) == -1) {
			--i;
			broj_cvorova--;
		}
		ispis(stablo);
		i++;
		getch();
	}
	system("cls");
	ispis(stablo);
 
	int izbor;
	int cvor;
	int vrijednost;
	do {
		cout << "ENTER ZA NASTAVAK" << endl;
		getch();
		system("cls");
		cout << "IZBORNIK" << endl;
		cout << "1. Roditelj cvora" << endl;
		cout << "2. Prvo dijete cvora" << endl;
		cout << "3. Sljedeci brat cvora" << endl;
		cout << "4. Labela (oznaka) cvora" << endl;
		cout << "5. Korijen stabla" << endl;
		cout << "6. Kreiranje cvora" << endl;
		cout << "7. Promjena labele cvora" << endl;
		cout << "8. Brisanje cvora sa svim potomcima" << endl;
		cout << "9. Izlaz iz programa" << endl;
		cout << "Unesite mogucnost: ";
		cin >> izbor;
		cout << endl << endl;
		switch(izbor) {
			case 1:
				ispis(stablo);
				cout << "Unesite poziciju cvora: ";
				cin >> cvor;
				cout << "Roditelj cvora: " << parentT(cvor,stablo) << endl;;
				break;
			case 2:
				ispis(stablo);
				cout << "Unesite poziciju cvora: ";
				cin >> cvor;
				cout << "Prvo dijete cvora: " << firstchildT(cvor,stablo) << endl;
				break;
			case 3:
				ispis(stablo);
				cout << "Unesite poziciju cvora: ";
				cin >> cvor;
				cout << "Sljedeci brat cvora: " << nextsiblingT(cvor,stablo) << endl;
				break;
			case 4:
				ispis(stablo);
				cout << "Unesite poziciju cvora: ";
				cin >> cvor;
				cout << "Labela cvora: " << labelT(cvor,stablo) << endl;
				break;
			case 5:
				ispis(stablo);
				cout << "Korijen stabla: " << rootT(stablo) << endl;
				break;
			case 6:
				cout << "Unesite poziciju cvora gdje ce se kreirati dijete cvora: ";
				cin >> cvor;
				if(createT(broj_cvorova++,cvor,stablo) == -1)
					broj_cvorova--;
				ispis(stablo);
				break;
			case 7:
				ispis(stablo);
				cout << "Unesite poziciju cvora gdje zelite promijeniti labelu: ";
				cin >> cvor;
				cout << "Unesite oznaku(labelu) zamjene: ";
				cin >> vrijednost;
				changelabelT(vrijednost,cvor,stablo);
				system("cls");
				ispis(stablo);
				break;
			case 8:
				ispis(stablo);
				cout << "Unesite poziciju cvora kojeg zelite obrisati ";
				cin >> cvor;
				if(deleteT(cvor,stablo) == -1)
					cout << "Ne postoji cvor sa tom pozicijom za brisanje" << endl;
				cout << "Broj cvorova(sa korijenom): " << broj_cvorova << endl;
				getch();
				system("cls");
				ispis(stablo);
				break;
 
		}
	} while(izbor != 9);
 
 
	return 0;
}