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.