Metody programowania / Ćwiczenia 3: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
(Odstepy itp.)
(Odstepy itp.)
Linia 27: Linia 27:
 
</div>
 
</div>
 
</div>}}
 
</div>}}
 +
  
 
==Zadanie 2 (Odbicie lustrzane)==
 
==Zadanie 2 (Odbicie lustrzane)==
Linia 48: Linia 49:
 
</div>
 
</div>
 
</div>}}
 
</div>}}
 +
  
 
==Zadanie 3 (Izomorfizm drzew)==
 
==Zadanie 3 (Izomorfizm drzew)==
Linia 256: Linia 258:
  
  
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
{{wskazowka| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
Można też  skorzystać z następującej własności drzew BST: w obiegu infiksowym wartości tworzą ciąg rosnący.
 
Można też  skorzystać z następującej własności drzew BST: w obiegu infiksowym wartości tworzą ciąg rosnący.
 
</div>
 
</div>
 
</div>}}
 
</div>}}
  
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
{{rozwiazanie| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
  '''function''' CzyBST2(d: drzewo): boolean;
 
  '''function''' CzyBST2(d: drzewo): boolean;
 
  '''var''' ost: integer;
 
  '''var''' ost: integer;

Wersja z 19:55, 11 sie 2006

To są zadania na drzewa. 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 1

{{{3}}}


Zadanie 2 (Odbicie lustrzane)

Napisz procedurę przekształcającą zadane drzewo w jego odbicie lustrzane.

Rozwiązanie 1

{{{3}}}


Zadanie 3 (Izomorfizm drzew)

Napisz funkcję sprawdzającą czy dwa zadane drzewa są izomorficzne (mają taki sam kształt).

Rozwiązanie 1

{{{3}}}


Zadanie 4 (Lista liści)

Napisz funkcję wiążącą liście drzewa w listę (od lewej do prawej). Wynikiem funkcji jest 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 1

{{{3}}}

Rozwiązanie 1

{{{3}}}


Zadanie 5 (Szerokość drzewa)

Napisz funkcję obliczającą szerokość drzewa, czyli maksymalną liczbę wierzchołków na jednym poziomie.

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}


Zadanie 6 (Średnica drzewa)

Napisz funkcję obliczającą średnicę drzewa. Średnica to maksymalna odległość między dwoma wierzchołkami.

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}


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}}}