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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
(Odstepy itp.)
 
(Nie pokazano 22 wersji utworzonych przez 5 użytkowników)
Linia 1: Linia 1:
To są zadania na drzewa. Przyjmujemy następujące definicje:
+
To są zadania na drzewa.  
  '''type''' el_drzewa = record
+
 
                        w: integer;
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
                        lsyn, psyn: ^el_drzewa;
+
Oglądaj wskazówki i rozwiązania __SHOWALL__<br>
                        end;
+
Ukryj wskazówki i rozwiązania __HIDEALL__
          drzewo = ^el_drzewa;
+
</div>
 +
 
 +
Przyjmujemy następujące definicje:
 +
  '''type''' el_drzewa = '''record'''
 +
                    w: integer;
 +
                    lsyn, psyn: ^el_drzewa;
 +
                  '''end''';
 +
        drzewo = ^el_drzewa;
  
  
Linia 10: Linia 17:
 
Napisz funkcję która oblicza liczbę liści w drzewie.
 
Napisz funkcję która oblicza liczbę liści w drzewie.
  
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
  '''function''' LiczbaLiści(d: drzewo): integer;
 
  '''function''' LiczbaLiści(d: drzewo): integer;
 +
//Liczymy liczbe liści w drzewie
 
  '''begin'''
 
  '''begin'''
 
   '''if''' d = nil '''then''' LiczbaLiści:=0
 
   '''if''' d = nil '''then''' LiczbaLiści:=0
Linia 25: Linia 35:
  
 
''Omówienie:'' Koszt pamięciowy jest oczywiście związany z wielkością stosu wywołań rekurencyjnych
 
''Omówienie:'' Koszt pamięciowy jest oczywiście związany z wielkością stosu wywołań rekurencyjnych
 +
 +
[[pimp:modul3m_1_1.html|Wizualizacja]]
 +
 +
</div>
 
</div>
 
</div>
</div>}}
 
  
 
==Zadanie 2 (Odbicie lustrzane)==
 
==Zadanie 2 (Odbicie lustrzane)==
 
Napisz procedurę przekształcającą zadane drzewo w jego odbicie lustrzane.
 
Napisz procedurę przekształcającą zadane drzewo w jego odbicie lustrzane.
 
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
  '''procedure''' Lustro(d: drzewo);
 
  '''procedure''' Lustro(d: drzewo);
 +
//Przekształcamy d na swoje odbicie lustrzane
 
  '''var''' pom: drzewo;
 
  '''var''' pom: drzewo;
 
  '''begin'''
 
  '''begin'''
Linia 46: Linia 61:
  
 
''Koszt pamięciowy:'' liniowy ze względu na wysokość drzewa (rekurencja)
 
''Koszt pamięciowy:'' liniowy ze względu na wysokość drzewa (rekurencja)
 +
 +
[[pimp:modul3m_2_1.html|Wizualizacja]]
 +
 +
</div>
 
</div>
 
</div>
</div>}}
 
  
 
==Zadanie 3 (Izomorfizm drzew)==
 
==Zadanie 3 (Izomorfizm drzew)==
 
Napisz funkcję sprawdzającą czy dwa zadane drzewa są izomorficzne (mają taki sam kształt).
 
Napisz funkcję sprawdzającą czy dwa zadane drzewa są izomorficzne (mają taki sam kształt).
 
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
  '''function''' Izomorficzne(d1,d2: drzewo): boolean;
 
  '''function''' Izomorficzne(d1,d2: drzewo): boolean;
 +
//Sprawdzamy czy d1 i d2 mają taki sam kształt
 
  '''var''' i: boolean;
 
  '''var''' i: boolean;
 
  '''begin'''
 
  '''begin'''
Linia 68: Linia 88:
 
''Koszt czasowy:'' liniowy ze względu na sumę wielkości drzew
 
''Koszt czasowy:'' liniowy ze względu na sumę wielkości drzew
  
''Koszt pamięciowy:'' liniowy ze względu na minimum z wysokości drzew (rekurencja)
+
''Koszt pamięciowy:'' liniowy ze względu na minimum z wysokości drzew
 +
 
 +
[[pimp:modul3m_3_1.html|Wizualizacja]]
 +
 
 +
</div>
 
</div>
 
</div>
</div>}}
 
 
  
 
==Zadanie 4 (Lista liści)==
 
==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
+
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
 
  '''type''' węzeł = record
                        w: integer;
+
                w: integer;
                        lsyn, psyn, nast: ^węzeł;
+
                lsyn, psyn, nast: ^węzeł;
                        end;
+
              end;
          drzewoL = ^węzeł;
+
    drzewoL = ^węzeł;
 
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
Najwygodniej zrobić to obchodząc drzewo od prawej strony w lewo.
 
Najwygodniej zrobić to obchodząc drzewo od prawej strony w lewo.
 
</div>
 
</div>
</div>}}
+
</div>
  
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
  '''function''' ListaLiści(d: drzewoL): drzewoL;
 
  '''function''' ListaLiści(d: drzewoL): drzewoL;
  '''var''' l: drzewoL;
+
//Wynikiem funkcji jest wskaźnik do listy liści (od prawej do lewej) w drzewie d
  '''procedure''' Lista(d: drzewoL);   
+
  '''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'''
 
  '''begin'''
 
   '''if''' d <> nil '''then'''  
 
   '''if''' d <> nil '''then'''  
Linia 110: Linia 138:
  
 
''Koszt pamięciowy:'' liniowy ze względu na wysokość drzewa (rekurencja)
 
''Koszt pamięciowy:'' liniowy ze względu na wysokość drzewa (rekurencja)
 +
 +
[[pimp:modul3m_4_1.html|Wizualizacja]]
 +
 +
</div>
 
</div>
 
</div>
</div>}}
 
 
  
 
==Zadanie 5 (Szerokość drzewa)==
 
==Zadanie 5 (Szerokość drzewa)==
 
Napisz funkcję obliczającą szerokość drzewa, czyli maksymalną liczbę wierzchołków na jednym poziomie.
 
Napisz funkcję obliczającą szerokość drzewa, czyli maksymalną liczbę wierzchołków na jednym poziomie.
 
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
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.
 
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.
 
</div>
 
</div>
</div>}}
+
</div>
 
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
  '''function''' Szerokość(d: drzewo): integer;
 
  '''function''' Szerokość(d: drzewo): integer;
  '''var''' l, pom: lista
+
//Oblicza maksymalną liczbę wierzchołków na jednym poziomie drzewa d
  '''procedure''' Obejdź(d: drzewo; l:lista);   
+
  '''var''' l, pom: lista;
  //Zakładamy, że d <> nil, a l <> nil odpowiada poziomowi na którym jest d   
+
    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'''
 
  '''begin'''
  l^.w:=l^.w+1;
+
   '''if''' d <> nil '''then'''
   '''if''' l^.nast = nil '''and''' (d^.lsyn <> nil '''or''' d^.psyn <> nil) '''then''' '''begin'''
+
    '''if''' l = nil '''then''' '''begin'''  
    new(l^.nast);
+
      new(l);
    l^.nast^.w:=0;
+
      l^.w:=0;
    l^.nast^.nast:=nil;
+
      l^.nast:=nil;
  '''end''';
+
    '''end''';
  '''if''' d^.lsyn <> nil '''then''' Obejdż(d^.lsyn, l^.nast);
+
    l^.w:=l^.w+1;                                    //zwiększamy licznik liści na tym poziomie
  '''if''' d^.psyn <> nil '''then''' Obejdż(d^.psyn, l^.nast);
+
    Obejdź(d^.lsyn, l^.nast);                         //obchodzimy lewe i prawe poddrzewa
 +
    Obejdź(d^.psyn, l^.nast);
 
  '''end''';
 
  '''end''';
  '''begin''' //ListaLiści
+
  '''begin''' //Szerokość
  '''if''' d = nil '''then''' Szerokość:=0
+
   l:=nil;
   '''else''' '''begin'''
+
  Obejdź(d, l);
    new(l);
+
  maks:=0;                                             //szukamy maksimum na l i jednocześnie ją niszczymy
    l^.nast:=nil;
+
  '''while''' l <> nil '''do''' '''begin'''
    l^.w:=0;
+
    maks:=max(maks, l^.w);
    Obejdź(d,l);
+
    pom:=l;
    maks:=0;
+
    l:=l^.nast;
    '''while''' l <> nil '''do''' '''begin'''
+
    dispose(pom);
      maks:=max(maks, l^.w);
 
      pom:=l;
 
      l:=l^.nast;
 
      dispose(pom);
 
    '''end''';
 
    Szerokość:=maks;
 
 
   '''end''';
 
   '''end''';
 +
  Szerokość:=maks;
 
  '''end''';
 
  '''end''';
  
Linia 159: Linia 189:
 
''Koszt pamięciowy:'' liniowy ze względu na wysokość drzewa  
 
''Koszt pamięciowy:'' liniowy ze względu na wysokość drzewa  
 
</div>
 
</div>
</div>}}
+
</div>
 
 
 
 
  
 
==Zadanie 6 (Średnica drzewa)==
 
==Zadanie 6 (Średnica drzewa)==
 
Napisz funkcję obliczającą średnicę drzewa. Średnica to maksymalna odległość między dwoma wierzchołkami.
 
Napisz funkcję obliczającą średnicę drzewa. Średnica to maksymalna odległość między dwoma wierzchołkami.
  
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Nazwijmy d 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.
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka</span>
 +
<div class="mw-collapsible-content" style="display:none">
 +
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.
 +
</div>
 
</div>
 
</div>
</div>}}
 
  
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
  '''function''' Średnica(d: drzewo): integer;
 
  '''function''' Średnica(d: drzewo): integer;
 +
//Obliczamy maksymalną odległość między dwoma wierzchołkami w d
 
  '''var''' dl, maks: integer;
 
  '''var''' dl, maks: integer;
 
  '''function''' Ścieżki(d:drzewo; var dl, maks:integer);
 
  '''function''' Ścieżki(d:drzewo; var dl, maks:integer);
  //Na dl i maks są obliczne odpowiednio długość najdłuższej ścieżki w d i maksymalna średnica w d
+
  //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;
 
  '''var''' dl1,dl2,m1,m2, pom: integer;
 
  '''begin'''
 
  '''begin'''
Linia 199: Linia 233:
 
''Koszt pamięciowy:'' liniowy ze względu na wysokość drzewa (rekurencja)
 
''Koszt pamięciowy:'' liniowy ze względu na wysokość drzewa (rekurencja)
 
</div>
 
</div>
</div>}}
+
</div>
 
 
  
 
==Zadanie 7 (Sprawdzanie czy drzewo jest BST)==
 
==Zadanie 7 (Sprawdzanie czy drzewo jest BST)==
 
Napisz funkcję sprawdzającą czy drzewo jest [[drzewem BST]].
 
Napisz funkcję sprawdzającą czy drzewo jest [[drzewem BST]].
  
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
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ść tam występująca.
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
 +
<div class="mw-collapsible-content" style="display:none">
 +
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.
 +
</div>
 
</div>
 
</div>
</div>}}
 
  
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 1</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
  '''function''' CzyBST1(d: drzewo): boolean;
 
  '''function''' CzyBST1(d: drzewo): boolean;
 +
//Sprawdzamy czy d jest drzewem BST
 
  '''var''' mala, duza: integer;
 
  '''var''' mala, duza: integer;
 
  '''function''' Czy(d: drzewo; var mala,duza :integer): boolean;   
 
  '''function''' Czy(d: drzewo; var mala,duza :integer): boolean;   
Linia 230: Linia 268:
 
     mala:=d^.w;
 
     mala:=d^.w;
 
   '''end''';
 
   '''end''';
   '''if''' d^.psyn <> nil '''then''' '''begin'''  ///analogiczne sprawdzenie prawego poddrzewa
+
   '''if''' d^.psyn <> nil '''then''' '''begin'''  //analogiczne sprawdzenie prawego poddrzewa
 
     c2:=Czy(d^.psyn, m2, d2);
 
     c2:=Czy(d^.psyn, m2, d2);
 
     '''if''' c2 '''then''' '''begin'''
 
     '''if''' c2 '''then''' '''begin'''
Linia 253: Linia 291:
 
''Koszt pamięciowy:'' liniowy ze względu na wysokość drzewa  
 
''Koszt pamięciowy:'' liniowy ze względu na wysokość drzewa  
 
</div>
 
</div>
</div>}}
+
</div>
  
  
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 2</span>
 +
<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">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 2</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
  '''function''' CzyBST2(d: drzewo): boolean;
 
  '''function''' CzyBST2(d: drzewo): boolean;
 +
//Sprawdzamy czy d jest drzewem BST
 
  '''var''' ost: integer;
 
  '''var''' ost: integer;
      pierwsza, dobrze: boolean;
+
    pierwsza, dobrze: boolean;
 
  '''procedure''' Obejdź(d: drzewo):   
 
  '''procedure''' Obejdź(d: drzewo):   
  //Obejdź obchodzi d infiksowo; w liściach porównuje ost-ostatnio napotkaną wartość z wartością w liściu; wyjątkiem jest sytuacja gdy pierwsza=true, czyli gdy nie mamy jeszcze zapamiętanej żadnej wartości
+
  //Obejdź obchodzi d infiksowo; dla kazdego węzła d, poównujemy d^.w z ostatnio odwiedzoną wartością
  // dobrze oznacza że dotychczas odwiedzone liście tworzą ciąg rosnący
+
//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'''
 
  '''begin'''
   '''if''' dobrze '''and''' d <> nil '''then'''
+
   '''if''' dobrze '''and''' (d <> nil) '''then'''
    '''if''' d^.lsyn = nil '''and''' d^.psyn = nil '''then'''
+
    '''begin'''
      '''if''' pierwsza '''then''' '''begin'''
+
        Obejdź(d^.lsyn);
        pierwsza:=false;
+
        '''if''' pierwsza then  
        ost:=d^.w;
+
        '''begin''' ost:=d^.w //pierwszy element może być dowolny
      '''end'''
+
            pierwsza:=false
      '''else'''  
+
        '''end'''
        dobrze:=(ost < d^.w);
+
        '''else''' dobrze:=dobrze and (ost < d^.w);
    '''else''' '''begin'''
+
        '''if''' dobrze then '''begin''' //ucinamy rekursję tak wcześnie, jak się da!
      Obejdź(d^.lsyn);
+
          ost:=d^.w;
      Obejdź(d^.psyn);  
+
          Obejdź(d^.psyn);  
    '''end;     
+
        '''end''';     
 +
    '''end''';
 
  '''end''';
 
  '''end''';
 
  '''begin''' //CzyBST2
 
  '''begin''' //CzyBST2
Linia 293: Linia 339:
 
''Koszt pamięciowy:'' liniowy ze względu na wysokość drzewa  
 
''Koszt pamięciowy:'' liniowy ze względu na wysokość drzewa  
 
</div>
 
</div>
</div>}}
+
</div>

Aktualna wersja na dzień 21:58, 28 maj 2020

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

Zadanie 2 (Odbicie lustrzane)

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

Rozwiązanie

Zadanie 3 (Izomorfizm drzew)

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

Rozwiązanie

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

Rozwiązanie

Zadanie 5 (Szerokość drzewa)

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

Wskazówka

Rozwiązanie

Zadanie 6 (Średnica drzewa)

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

Wskazówka

Rozwiązanie

Zadanie 7 (Sprawdzanie czy drzewo jest BST)

Napisz funkcję sprawdzającą czy drzewo jest drzewem BST.

Wskazówka 1

Rozwiązanie 1


Wskazówka 2

Rozwiązanie 2