Metody programowania / Ćwiczenia 3

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

{{{3}}}

Rozwiązanie 1

{{{3}}}

Wskazówka 2

{{{3}}}

Rozwiązanie 2

{{{3}}}