Drzewo binarne – najstarsze słowo – rozwiązanie nr 1 (trudniejsze)

ZADANIE NA 29.11.2015, WIĘC JESZCZE MACIE PONAD 2 TYGODNIE NA PRZEROBIENIE GO NA TYSIĄC SPOSOBÓW 🙂

Rozwiązanie nigdy nie wrzucane na spox, więc nie wiem ile punktów dostanie.

Jest to rozwiązanie TRUDNIEJSZE (w rekurencji jest złożona pętla która pozwala zaoszczędzić parę bajtów i sporo obliczeń). Za chwilę dodam wpis z rozwiązaniem łatwiejszym do zrozumienia, ale wolniejszym o jakieś 30%.

ZADANIE
Rozważmy niepuste drzewo binarne T etykietowane literami alfabetu angielskiego (tylko małe litery) i zapisane wierzchołkowo tak, że pozycję dowolnego wierzchołka x w drzewie T określa ciąg skierowań krawędzi (L – lewa krawędź, R – prawa krawędź) jakie pokonamy przechodząc w tym drzewie ścieżkę od korzenia do wierzchołka x.
Wyznacz najstarsze leksykograficznie słowo, jakie można zbudować z etykiet wierzchołków rozważanego drzewa występujących na dowolnej ścieżce wierzchołek zewnętrzny (liść) drzewa T – korzeń drzewa T.
WEJŚCIE
Ciąg wierszy zakończony symbolem znaku końca pliku (EOF) reprezentujący poprawnie (zgodnie z powyższym opisem) pewne drzewo binarne T. Każdy pojedynczy wiersz zakończony znakiem nowej linii (kod ASCII 10) opisujący pozycję wierzchołka w drzewie T i zawierający:
– małą literę alfabetu angielskiego (kod ASCII od 97 do 122) – etykieta wierzchołka,
– znak odstępu (kod ASCII 32),
– ciąg znaków L (kod ASCII 76) oraz R (kod ASCII 82) – ciąg skierowań krawędzi na ścieżce od korzenia drzewa do rozważanego wierzchołka.
WYJŚCIE
Wiersz zawierajacy ciąg znaków będący rozwiązaniem postawionego problemu.
OGRANICZENIA
Liczba wierzchołków drzewa T nie większa niż 10^7. Wysokość drzewa T ograniczona przez 2^6.

LIMITY
Złożoność czasowa O(n), złożoność pamięciowa O(n), gdzie n jest liczbą wierzchołków drzewa T.
PRZYKŁAD 1

wejście:
a LL
d
a R
s L

wyjście:
asd

ROZWIĄZANIE:

Pamiętajcie, żeby przed wrzuceniem na spoxa zmienić getchar na getchar_unlocked (w 2 miejscach):

#include <stdio.h>

class Element;

Element* aktualnyElement;

char najstarszyWyraz[65];

class Element
{
	public:
		char wartosc;
		Element* prawy;
		Element* lewy;
		Element* rodzic;
		Element()
		{
			wartosc = 0;
			prawy = NULL;
			lewy = NULL;
			rodzic = NULL;
		}

		void rekurencja()
		{
			// jesli ma lewy
			if(this->lewy)
			{
				this->lewy->rekurencja();
			}
			// jesli ma prawy
			if(this->prawy)
			{
				this->prawy->rekurencja();
			}
			// jesli nie ma lewego, ani prawego = JEST LISCIEM
			else if(!this->lewy)
			{
				aktualnyElement = this;
				register int i = 0;
				while(aktualnyElement->rodzic)
				{
					// aktualny 'najstarszyWyraz' jest krotszy od aktualnego wyrazu
					if(najstarszyWyraz[i] == NULL)
					{
						while(aktualnyElement->rodzic)
						{
							najstarszyWyraz[i] = aktualnyElement->wartosc;
							aktualnyElement = aktualnyElement->rodzic;
							++i;
						}
						najstarszyWyraz[i] = aktualnyElement->wartosc;
						// dodanie NULL na koncu wyrazu
						najstarszyWyraz[i+1] = 0;
						break;
					}
					// aktualna litera 'najstarszyWyraz' jest rowna literze aktualnego wyrazu
					// moze to byc nowy rekordzista, trzeba sprawdzac dalej
					else if(najstarszyWyraz[i] == aktualnyElement->wartosc)
					{
						aktualnyElement = aktualnyElement->rodzic;
						++i;
					}
					// aktualna litera 'najstrszyWyraz' jest nizsza, niz litera aktualnego wyrazy
					// aktualny wyraz jest rekordzista, trzeba go przepisac do konca
					else if(najstarszyWyraz[i] < aktualnyElement->wartosc)
					{
						while(aktualnyElement->rodzic)
						{
							najstarszyWyraz[i] = aktualnyElement->wartosc;
							aktualnyElement = aktualnyElement->rodzic;
							++i;
						}
						najstarszyWyraz[i] = aktualnyElement->wartosc;
						// dodanie NULL na koncu wyrazu
						najstarszyWyraz[i+1] = 0;
						break;
					}
					// aktualna litera 'najstarszyWyraz' jest wyzsza, niz aktualnego wyrazu
					// na pewno nie bedzie to nowy rekordzista
					else
					{
						break;
					}
				}
				// dodanie ostatniego elementu ktory zostal po wykonaniu petli
				// o ile nowy wyraz jest rekordzista
				if(najstarszyWyraz[i] <= aktualnyElement->wartosc)
				{
					najstarszyWyraz[i] = aktualnyElement->wartosc;
					// dodanie NULL na koncu wyrazu
					// nowy wyraz moze byc KROTSZY, niz poprzedni rekordzista
					najstarszyWyraz[i+1] = 0;
				}
			}
			// pod spodem kod do wypisywania na konsole aktualnie przegladanej litery i aktualnego rekordzisty
			//fprintf(stdout, "litera '%c' wyraz: '%s'\n", this->wartosc, najstarszyWyraz);
		}
};

int main()
{
	// czyscimy tablice z naj
	for(int i = 0; i < 65; ++i)
	{
		najstarszyWyraz[i] = 0;
	}
	register char znakNaWejsciu;
	register char wartosc = getchar();

	Element* korzen = new Element();
	aktualnyElement = korzen;

	while(!feof(stdin))
	{
		znakNaWejsciu = getchar();
		// litera 'a-z'
		if(znakNaWejsciu > 96 && znakNaWejsciu < 123)
		{
			// zapisz ostatnio zapamietana litere na elemencie na ktorym zatrzymal sie wskaznik
			aktualnyElement->wartosc = wartosc;
			// cofnij wskaznik na poczatek drzewa
			aktualnyElement = korzen;
			// zapamietaj nowa litere
			wartosc = znakNaWejsciu;
		}
		// R
		else if(znakNaWejsciu == 82)
		{
			// jesli element po prawej nie istnieje to go utworz
			if(!aktualnyElement->prawy)
			{
				aktualnyElement->prawy = new Element();
				aktualnyElement->prawy->rodzic = aktualnyElement;
			}
			// przejdz w prawo
			aktualnyElement = aktualnyElement->prawy;
		}
		// L
		else if(znakNaWejsciu == 76)
		{
			// jesli element po lewej nie istnieje to go utworz
			if(!aktualnyElement->lewy)
			{
				aktualnyElement->lewy = new Element();
				aktualnyElement->lewy->rodzic = aktualnyElement;
			}
			// przejdz w lewo
			aktualnyElement = aktualnyElement->lewy;
		}
	}

	// koniec wczytywania, wskaznik doszedl do jakiegos elementu
	// trzeba w tym elemencie zapisac ostatnio zapamietana wartosc
	aktualnyElement->wartosc = wartosc;

	// rekurencja przemieli drzewo i zapisze nam najstarszy wyraz do zmiennej
	korzen->rekurencja();
	fprintf(stdout, "%s", najstarszyWyraz);
	return 0;
}