9988996104

Drzewa binarnych poszukiwań

Zadanie 15

Napisać procedurę w języku Pascal obliczającą:

1.    liczba wierzchołków drzewa BST;

2.    liczba liści drzewa BST;

3.    wysokość drzewa BST;

4.    liczbę wierzchołków o wysokości k;

5.    liczbę wierzchołków o głębokości k.

Zadanie 16

Napisać procedurę w języku Pascal sprawdzającą czy dwa drzewa BST mają te same klucze (to znaczy każdy klucz występuje tą samą liczbę razy w obu drzewach).

Zadanie 17

Napisać procedurę w języku Pascal sprawdzającą czy jedno drzewo BST jest poddrzewem drugiego.

Zadanie 18

Napisać procedurę w języku Pascal obliczającą wskaźnik do najdłuższej gałęzi w drzewie BST. Zadanie 19

Napisać procedurę w języku Pascal obliczającą wskaźnik do największego pełnego poddrzewa binarnego w drzewie BST.

Zadanie 20

Napisać procedurę w języku Pascal sprawdzającą czy etykietowane drzewo binarne jest drzewem BST.

Zadanie 21

Napisać procedurę w języku Pascal sprawdzającą czy drzewo BST jest zbalansowane. Drzewo jest zbalansowane o ile różnica wielkości poddrzew każdego wierzchołka jest co najwyżej 1.

Zadanie 22

Napisać procedurę w języku Pascal obliczającą wskaźnik do wierzchołka o najmniejszej różnicy z daną liczba rzeczywistą (zakładamy, że klucze w drzewie BST są rzeczywiste).

Zadanie 23

Napisać procedurę w języku Pascal, która czyści drzewo BST.

Zadanie 24

Drzewo binarne jest zdefiniowane następująco:

drzewo = “wezel; wezel = record klucz: integer; lewy, prawy: drzewo

end;

Napisać funkcję function ile(d:drzewo)-.integer, która zwraca liczbę węzłów w drzewie d o kluczach mniejszych od klucza korzenia drzewa.

18