Laboratorium programowania zad 9

Zadanie z laboratorium programowania na Informatyce UW.

Zadanie 9 (termin wysylania rozwiazan: 14 III 2008, godz. 23:59)

(Poziomy drzewa)

Napisz program, ktory wczyta z wejscia ciag napisow, z ktorych
kazdy bedzie zajmowal jeden wiersz, utworzy z nich drzewo BST,
a nastepnie wypisze to drzewo poziomami.

Kolejne napisy wczytywane z wejscia program bedzie wstawial
do drzewa BST, przechodzac do lewego poddrzewa, jesli wstawiany
napis jest "<=" (w porzadku leksykograficznym) od napisu
w aktualnym wezle, wpp. przechodzac do prawego poddrzewa.

Po utworzeniu drzewa, program powinien je wypisac na wyjscie
poziomami - w pierwszym wierszu nalezy wypisac napis z korzenia,
w drugim napisy jego synow itd. Lacznie program wypisze tyle
wierszy, ile jest niepustych poziomow w drzewie.

Na i-tym poziomie jest 2^i pozycji, na ktorych moze sie znalezc
wezel. Program powinien wypisac zawartosc kazdej pozycji.
Jesli jest na niej wezel, wypisujemy napis, ktory sie w nim
znajduje, oraz jedna spacje. Jesli na danej pozycji poziomu
nie ma wezla, program wypisuje pare nawiasow okraglych i jedna
spacje.

Np. dla danych:

kota
ala
miec
by
chciala

program powinien wypisac:

kota 
ala miec 
() by () () 
() () () chciala () () () () 

A oto rozwiązanie:

program zad8;
type

	drzewo_t=^drzewo_r_t;
	drzewo_r_t=record
		prawy:drzewo_t;
		lewy:drzewo_t;
		napis:string;
	end;
	
	//Tutaj beda przechowywane napisy
	napis_t=^napis_r_t;
	napis_r_t=record
		nastepny:napis_t;
		wezel:drzewo_t;
	end;
	
	//A tu cale wiersze
	wiersz_t=^wiersz_r_t;
    wiersz_r_t=record 
		lisci:integer; //niepustych lisci
		nastepny:wiersz_t;
		napis:napis_t; //Pierwszy plik
	end;


	procedure spacer(wezel:drzewo_t;poziom:wiersz_t);
	var teraz:napis_t;
	begin
		if (wezelnil) then
		begin
			if (poziom^.napis=nil) then
			begin
				new(poziom^.napis);
				teraz:=poziom^.napis;
				teraz^.nastepny:=nil;
			end
			else
			begin
				teraz:=poziom^.napis;
				while teraz^.nastepnynil do
					teraz:=teraz^.nastepny;
				new(teraz^.nastepny);
				teraz:=teraz^.nastepny;
				teraz^.nastepny:=nil;
			end;
			
			teraz^.wezel:=wezel;
			
			if wezel^.napis'()' then
				poziom^.lisci+=1;
			
			if poziom^.nastepny=nil then
			begin
				new(poziom^.nastepny);
				poziom^.nastepny^.nastepny:=nil;
				poziom^.nastepny^.napis:=nil;
				poziom^.nastepny^.lisci:=0;
			end;
			
			//No i rekurencja:
			
			spacer(wezel^.lewy,poziom^.nastepny);
			spacer(wezel^.prawy,poziom^.nastepny);
			
		end;
	end;
	
var wiersz:string;
teraz,drzewo:drzewo_t;
lista,teraz_lista:wiersz_t;
napis:napis_t;

begin

	if not EOF then
	begin

		readln(wiersz);
		
		new(drzewo);
		new(drzewo^.lewy);
		new(drzewo^.prawy);
		drzewo^.lewy^.lewy:=nil;
		drzewo^.lewy^.prawy:=nil;
		drzewo^.lewy^.napis:='()';
		drzewo^.prawy^.lewy:=nil;
		drzewo^.prawy^.prawy:=nil;
		drzewo^.prawy^.napis:='()';
		drzewo^.napis:=wiersz;
		
		while not EOF do
		begin
			readln(wiersz);
			teraz:=drzewo;
			
			while teraz^.napis'()' do
			begin
				if wiersz > teraz^.napis then
					teraz:=teraz^.prawy
				else
					teraz:=teraz^.lewy;
			end;
			
			teraz^.napis:=wiersz;
			new(teraz^.lewy);
			new(teraz^.prawy);
			teraz^.lewy^.lewy:=nil;
			teraz^.lewy^.prawy:=nil;
			teraz^.lewy^.napis:='()';
			teraz^.prawy^.lewy:=nil;
			teraz^.prawy^.prawy:=nil;
			teraz^.prawy^.napis:='()';
			
		end;
		//Teraz powinismy miec wszystko w drzewie.

		new(lista);
		lista^.nastepny:=nil;
		lista^.napis:=nil;
		lista^.lisci:=0;
				
		spacer(drzewo,lista);
		//Teraz wszystko przygotowane do wypisania.
//to wymaga przejrzenia:

	
		teraz_lista:=lista;
		while teraz_lista^.nastepnynil do
		begin
		
			if	(teraz_lista^.lisci>0) then
			begin
				napis:=teraz_lista^.napis;
				while napis^.nastepnynil do
				begin
					write(napis^.wezel^.napis);
					
					if (napis^.wezel^.napis'') then
						write(' ');
					
					//sprzatamy:
					//tmp_napis:=napis;
					napis:=napis^.nastepny;
					//dispose(tmp_napis);
				end
			end;
			//usuwamy straznika:
			
			writeln();
			
			//Sprzatamy:
			//tmp_teraz_lista:=teraz_lista;
			teraz_lista:=teraz_lista^.nastepny;
			//dispose(tmp_teraz_lista);
		end;
		dispose(teraz_lista);
		//usuwamy straznika
	end
end.