[PJWSTK] ASD – Kolokwium 3 – Rozwiązanie

Trzecie zadanie z ASD:

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ź, P - prawa krawędź) jakie pokonamy przechodząc w drzewie T ścieżkę od korzenia do wierzchołka x (przykłady poniżej).

Wyznacz najstarsze leksykograficznie słowo, jakie można zbudować z etykiet wierzchołków 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 w sposób poprawny pewne drzewo binarne T. Każdy pojedynczy wiersz zakończony znakiem nowego wiersza/linii (ASCII kod 10) opisujący pozycję wierzchołka w drzewie T i zawierający:

małą literę alfabetu nagielskiego (ASCII kod od 97 do 122) - etykieta wirzchołka,
znak odstępu/spacji (ASCII kod 32),
ciąg znaków L (ASCII kod 76) oraz R (ASCII kod 82) - ciąg skierowań krawędzi.
Liczba wierzchołków drzwa T ograniczona zawarta w przedziale [1,10^6]. Wysokość drzewa T ograniczona przez 2^6.

Wyjście

Wiersz zawierajacy ciąg znaków będący rozwiązaniem postawionego problemu.

Złożoności i limity

Złożoność czasowa O(nh), złożoność pamięciowa O(n) bez uwzględnienia kosztów mechanizmu rekursji, gdzie n jest liczbą wierzchołków drzewa T a h jest jego wysokością. Fizyczny limit pamięci, bez uwzględnienia kosztu mechanizmu rekursji, zależny od rozmiaru danych wejściowych i ograniczony przez 10n B+1 KB.

Przykład 1

Wejście:
a LL
d
a R
s L

Wyjście:
asd
Przykład 2

Wejście:
s LR
o LRR
m RR
p LRLRL
k
w LRL
a LL
t L
h R
j LRLR

Wyjście:
pjwstk

Jedno z wielu możliwych rozwiązań:

#include<iostream>
using namespace std;

class Element
{
    public:
	char value;
	Element* left;
	Element* right;
	Element()
	{
		value = NULL;
		left = NULL;
		right = NULL;
	}
};

void showTree(Element* element)
{
	if(element->left)
		showTree(element->left);
	if(element->right)
		showTree(element->right);
	cout << element->value;
}

char isOneNode(Element* element)
{
	if(element->left && element->right)
		return 0;
	else if(element->left)
		return isOneNode(element->left);
	else if(element->right)
		return isOneNode(element->right);
	else
		return 1;
}

char getTheBest(Element* element)
{
	char r1 = 0;
	char r2 = 0;
	if(!element->left && !element->right)
	{
		return element->value - 70;
	}
	else
	{
		if(element->left)
		{
			r1 = getTheBest(element->left);
		}
		if(element->right)
		{
			r2 = getTheBest(element->right);
		}
	}
	if(r1 != 0 && r1 < 90)
	{
		delete element->left;
		element->left = NULL;
		r1 = r1 + 70;
	}
	if(r2 != 0 && r2 < 90)
	{
		delete element->right;
		element->right = NULL;
		r2 = r2 + 70;
	}
	if(r1 > r2)
	{
		delete element->right;
		element->right = NULL;
		return r1;
	}
	else if(r1 < r2)
	{
		delete element->left;
		element->left = NULL;
		return r2;
	}
	return r2;
}

int main()
{
	char lastChar;
	char tmpChar;
	Element* root = new Element();
	Element* currentNode = root;
	cin >> lastChar;
	while(cin >> tmpChar)
	{
		if(tmpChar == 'L')
		{
			if(currentNode->left == NULL)
			{
				currentNode->left = new Element();
			}
			currentNode = currentNode->left;
		}
		else if(tmpChar == 'R')
		{
			if(currentNode->right == NULL)
			{
				currentNode->right = new Element();
			}
			currentNode = currentNode->right;
		}
		else
		{
			currentNode->value = lastChar;
			lastChar = tmpChar;
			currentNode = root;
		}
	}
	currentNode->value = lastChar;
	while(!isOneNode(root))
	{
		cout << getTheBest(root);
	}
	showTree(root);
	return 0;
}