Drzewo binarne – najstarsze słowo – rozwiązanie nr 2 (łatwiejsze)

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 ŁATWIEJSZE (w rekurencji jest najprostsza możliwa pętla).

Rozwiązanie TRUDNIEJSZE (około 30% szybsze):

http://skalski.at/2015/11/14/pjwstk-asd-jesien-2015-zadanie-2-rozwiazanie-nr-1/

Rozwiązanie oszczędzające 1/3 pamięci, ale dające tylko 85% punktów w tym roku (z przed 2 lat):

http://skalski.at/2012/11/17/pjwstk-asd-kolokwium-3-rozwiazanie/

Inne możliwe rozwiązania:

• można utworzyć listę elementów (oprócz drzewa) i na niej znaleźć 'liście’ bez męczenia się z rekurencją (po prostu puścić 'while’ po wszystkich elementach w 'main’)
• można oszczędzić 1/3 pamięci nie zapisując 'rodzica’ w elementach, zamiast tego wystarczy dodatkowa tablica 'char wyraz[65]’ z wyrazem 'od korzenia do liścia’ (czyli odwrotną do tej jakiej potrzebujemy) oraz zmienna 'int aktualnaGlebokoscRekurencji’ zwiększana na początku każdego wywołania rekurencji (zanim przejdzie do lewego/prawego) i zmniejszana przed końcem

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>
#include <string.h>
class Element;

Element* aktualnyElement;

char najstarszyWyraz[65];
char aktualnyWyraz[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)
			{
				// jest lisciem, sprawdzamy czy wyraz utworzony z liter od liscia do korzenia
				// jest starszy od aktualnego rekordzisty, jak tak to zapisujemy jako nowego rekordziste
				
				// zapisujemy aktualny wyraz (z liter od liscia do korzenia) do zmiennej
				aktualnyElement = this;
				register int i = 0;
				while(aktualnyElement->rodzic)
				{
					aktualnyWyraz[i] = aktualnyElement->wartosc;
					aktualnyElement = aktualnyElement->rodzic;
					++i;
				}
				// po zakonczeniu petli zostaje jedna litera ktora musimy dodac
				aktualnyWyraz[i] = aktualnyElement->wartosc;
				// dodanie NULL na koncu wyrazu
				aktualnyWyraz[i+1] = 0;
				
				// jesli aktualny wyraz jest starszy leksykograficznie
				if(strcmp(najstarszyWyraz, aktualnyWyraz) < 0)
				{
					strncpy(najstarszyWyraz, aktualnyWyraz, 65);
				}
			}
			// 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;
}