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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 1: Linia 1:
 
To są zadania na drzewa. Przyjmujemy następujące definicje:
 
To są zadania na drzewa. Przyjmujemy następujące definicje:
  '''type''' el_drzewa = record
+
  '''type''' el_drzewa = '''record'''
 
                     w: integer;
 
                     w: integer;
 
                     lsyn, psyn: ^el_drzewa;
 
                     lsyn, psyn: ^el_drzewa;
                   end;
+
                   '''end''';
 
         drzewo = ^el_drzewa;
 
         drzewo = ^el_drzewa;
 +
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
Oglądaj wskazówki i rozwiązania __SHOWALL__<br>
 +
Ukryj wskazówki i rozwiązania __HIDEALL__
 +
</div>
 +
  
 
==Zadanie 1 (Liczba liści w drzewie)==
 
==Zadanie 1 (Liczba liści w drzewie)==

Wersja z 22:39, 28 wrz 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;

Oglądaj wskazówki i rozwiązania __SHOWALL__
Ukryj wskazówki i rozwiązania __HIDEALL__


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