Metody programowania / Ćwiczenia 3: Różnice pomiędzy wersjami
(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| | + | {{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| | + | {{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
Zadanie 2 (Odbicie lustrzane)
Napisz procedurę przekształcającą zadane drzewo w jego odbicie lustrzane.
Rozwiązanie 1
Zadanie 3 (Izomorfizm drzew)
Napisz funkcję sprawdzającą czy dwa zadane drzewa są izomorficzne (mają taki sam kształt).
Rozwiązanie 1
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
Rozwiązanie 1
Zadanie 5 (Szerokość drzewa)
Napisz funkcję obliczającą szerokość drzewa, czyli maksymalną liczbę wierzchołków na jednym poziomie.
Wskazówka 1
Rozwiązanie 1
Zadanie 6 (Średnica drzewa)
Napisz funkcję obliczającą średnicę drzewa. Średnica to maksymalna odległość między dwoma wierzchołkami.
Wskazówka 1
Rozwiązanie 1
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