To są zadania na drzewa.
Oglądaj wskazówki i rozwiązania __SHOWALL__
Ukryj wskazówki i rozwiązania __HIDEALL__
Przyjmujemy następujące definicje:
type el_drzewa = record
w: integer;
lsyn, psyn: ^el_drzewa;
end;
drzewo = ^el_drzewa;
Zadanie 1 (Liczba liści w drzewie)
Napisz funkcję która oblicza liczbę liści w drzewie.
Rozwiązanie
function LiczbaLiści(d: drzewo): integer;
//Liczymy liczbe liści w drzewie
begin
if d = nil then LiczbaLiści:=0
else
if d^.lsyn=nil and d^.psyn=nil then LiczbaLiści:=1
else
LiczbaLiści:=LiczbaLiści(d^.lsyn) + LiczbaLiści(d^.psyn);
end;
Koszt czasowy: liniowy ze względu na wielkość drzewa
Koszt pamięciowy: liniowy ze względu na wysokość drzewa
Omówienie: Koszt pamięciowy jest oczywiście związany z wielkością stosu wywołań rekurencyjnych
Wizualizacja
Zadanie 2 (Odbicie lustrzane)
Napisz procedurę przekształcającą zadane drzewo w jego odbicie lustrzane.
Rozwiązanie
procedure Lustro(d: drzewo);
//Przekształcamy d na swoje odbicie lustrzane
var pom: drzewo;
begin
if d <> nil then begin
Lustro(d^.lsyn);
Lustro(d^.psyn);
pom:=d^.lsyn;
d^.lsyn:=d^.psyn;
d^.psyn:=pom;
end;
end;
Koszt czasowy: liniowy ze względu na wielkość drzewa
Koszt pamięciowy: liniowy ze względu na wysokość drzewa (rekurencja)
Wizualizacja
Zadanie 3 (Izomorfizm drzew)
Napisz funkcję sprawdzającą czy dwa zadane drzewa są izomorficzne (mają taki sam kształt).
Rozwiązanie
function Izomorficzne(d1,d2: drzewo): boolean;
//Sprawdzamy czy d1 i d2 mają taki sam kształt
var i: boolean;
begin
if d1 = nil and d2 = nil then i:=true
else
if d1 <> nil and d2 <> nil then begin
i:=Izomorficzne(d1^.lsyn, d2^.lsyn);
if i then i:=Izomorficzne(d1^.psyn, d2^.psyn);
end
else i:=false;
Izomorficzne:=i;
end;
Koszt czasowy: liniowy ze względu na sumę wielkości drzew
Koszt pamięciowy: liniowy ze względu na minimum z wysokości drzew
Wizualizacja
Zadanie 4 (Lista liści)
Napisz funkcję wiążącą liście drzewa w listę (od lewej do prawej). Wynikiem funkcji ma być wskaźnik do utworzonej listy. Zakładamy, że każdy węzeł ma dodatkowe pole będące wskaźnikiem do węzła, czyli używamy typów
type węzeł = record
w: integer;
lsyn, psyn, nast: ^węzeł;
end;
drzewoL = ^węzeł;
Wskazówka
Najwygodniej zrobić to obchodząc drzewo od prawej strony w lewo.
Rozwiązanie
function ListaLiści(d: drzewoL): drzewoL;
//Wynikiem funkcji jest wskaźnik do listy liści (od prawej do lewej) w drzewie d
var l: drzewoL; //dotychczas obliczona lista liści
procedure Lista(d: drzewoL);
//Jeśli węzeł d jest liściem to dopisujemy go z przodu listy l
//l jest zmienną globalną dla procedury Lista
begin
if d <> nil then
if d^.lsyn = nil and d^.psyn = nil then begin
d^.nast:=l;
l:=d;
end
else begin
Lista(d^.psyn);
Lista(d^.lsyn);
end;
end;
begin //ListaLiści
l:=nil;
Lista(d);
ListaLiści:=l;
end;
Koszt czasowy: liniowy ze względu na wielkość drzewa
Koszt pamięciowy: liniowy ze względu na wysokość drzewa (rekurencja)
Wizualizacja
Zadanie 5 (Szerokość drzewa)
Napisz funkcję obliczającą szerokość drzewa, czyli maksymalną liczbę wierzchołków na jednym poziomie.
Wskazówka
Najłatwiej to zrobić obchodząc drzewo wszerz; ale taniej jest gdy dla każdego poziomu będziemy pamiętać dotychczas odwiedzoną liczbę wierzchołków na tym poziomie. Do tego celu potrzebna jest lista.
Rozwiązanie
function Szerokość(d: drzewo): integer;
//Oblicza maksymalną liczbę wierzchołków na jednym poziomie drzewa d
var l, pom: lista;
maks: integer;
procedure Obejdź(d: drzewo; var l:lista);
//Wskaźnik l odpowiada poziomowi na którym jest d; jeśli l = nil to trzeba listę poziomów wydłużyć
begin
if d <> nil then
if l = nil then begin
new(l);
l^.w:=0;
l^.nast:=nil;
end;
l^.w:=l^.w+1; //zwiększamy licznik liści na tym poziomie
Obejdź(d^.lsyn, l^.nast); //obchodzimy lewe i prawe poddrzewa
Obejdź(d^.psyn, l^.nast);
end;
begin //Szerokość
l:=nil;
Obejdź(d, l);
maks:=0; //szukamy maksimum na l i jednocześnie ją niszczymy
while l <> nil do begin
maks:=max(maks, l^.w);
pom:=l;
l:=l^.nast;
dispose(pom);
end;
Szerokość:=maks;
end;
Koszt czasowy: liniowy ze względu na wielkość drzewa
Koszt pamięciowy: liniowy ze względu na wysokość drzewa
Zadanie 6 (Średnica drzewa)
Napisz funkcję obliczającą średnicę drzewa. Średnica to maksymalna odległość między dwoma wierzchołkami.
Wskazówka
Niech d to wierzchołek średnicy położony najbliżej korzenia. Wtedy średnica składa się z najdłuższej ścieżki w lewym i w prawym poddrzewie d.
Rozwiązanie
function Średnica(d: drzewo): integer;
//Obliczamy maksymalną odległość między dwoma wierzchołkami w d
var dl, maks: integer;
function Ścieżki(d:drzewo; var dl, maks:integer);
//Na dl i maks są obliczane odpowiednio długość najdłuższej ścieżki w d i maksymalna średnica w d
//Dla d = nil ustalamy dl na -1 żeby dobrze obliczać dl dla liści
var dl1,dl2,m1,m2, pom: integer;
begin
if d=nil then begin
dl:=-1;
maks:= 0;
end
else begin
Ścieżki(d^.lsyn, dl1, m1);
Ścieżki(d^.psyn, dl2, m2);
dl:=max(dl1,dl2)+1;
pom:=max(m1,m2);
maks:=max(pom, dl1+2+dl2);
end;
end;
begin //Średnica
Ścieżki(d, dl, maks);
Średnica:=maks;
end;
Koszt czasowy: liniowy ze względu na wielkość drzewa
Koszt pamięciowy: liniowy ze względu na wysokość drzewa (rekurencja)
Zadanie 7 (Sprawdzanie czy drzewo jest BST)
Napisz funkcję sprawdzającą czy drzewo jest drzewem BST.
Wskazówka 1
Sprawdzenie, że w każdym wierzchołku d^.lsyn^.w < d^.w < d^.psyn^.w nie wystarcza. Trzeba dla każdego poddrzewa wiedzieć jaka jest maksymalna i minimalna wartość w tym poddrzewie.
Rozwiązanie 1
function CzyBST1(d: drzewo): boolean;
//Sprawdzamy czy d jest drzewem BST
var mala, duza: integer;
function Czy(d: drzewo; var mala,duza :integer): boolean;
//Zakładamy, że d <> nil; Czy stwierdza czy d jest drzewem BST i jeśli tak to przy wyjściu z procedury mala i duza to najmniejsza i największa wartość w drzewie d
var m1,d1,m2,d2: integer;
c1,c2, lewy, prawy: boolean;
begin
if d^.lsyn <> nil then begin //sprawdzenie lewego poddrzewa
c1:=Czy(d^.lsyn, m1, d1);
if c1 then begin
lewy:=(d1 < d^.w);
mala:=m1;
end
else lewy:=false;
end
else begin
lewy:=true;
mala:=d^.w;
end;
if d^.psyn <> nil then begin //analogiczne sprawdzenie prawego poddrzewa
c2:=Czy(d^.psyn, m2, d2);
if c2 then begin
prawy:=(d^.w < m2);
duza:=d2;
end
else prawy:=false;
end
else begin
prawy:=true;
duza:=d^.w;
end
CzyBST1:=lewy and prawy;
end;
begin //CzyBST1
if d = nil then CzyBST:=true;
else CzyBST:=Czy(d, mala, duza);
end;
Koszt czasowy: liniowy ze względu na wielkość drzewa
Koszt pamięciowy: liniowy ze względu na wysokość drzewa
Wskazówka 2
Można też skorzystać z następującej własności drzew BST: w obiegu infiksowym wartości tworzą ciąg rosnący.
Rozwiązanie 2
function CzyBST2(d: drzewo): boolean;
//Sprawdzamy czy d jest drzewem BST
var ost: integer;
pierwsza, dobrze: boolean;
procedure Obejdź(d: drzewo):
//Obejdź obchodzi d infiksowo; dla kazdego węzła d, poównujemy d^.w z ostatnio odwiedzoną wartością
//obiegu infiksowego, którą mamy zapamiętaną w zmiennej globalnej ost.
//Wyjątkiem jest sytuacja gdy pierwsza=true, czyli gdy nie mamy jeszcze zapamiętanej żadnej wartości
//dobrze oznacza że dotychczas odwiedzone węzły tworzą ciąg rosnący
begin
if dobrze and (d <> nil) then
begin
Obejdź(d^.lsyn);
if pierwsza then
begin ost:=d^.w //pierwszy element może być dowolny
pierwsza:=false
end
else dobrze:=dobrze and (ost < d^.w);
if dobrze then begin //ucinamy rekursję tak wcześnie, jak się da!
ost:=d^.w;
Obejdź(d^.psyn);
end;
end;
end;
begin //CzyBST2
pierwsza:=true;
dobrze:=true;
Obejdź(d);
CzyBST2:=dobrze;
end;
Koszt czasowy: liniowy ze względu na wielkość drzewa
Koszt pamięciowy: liniowy ze względu na wysokość drzewa
