Studia Licencjackie / Inżynierskie

Algorytmy i struktury danych

Lista zadań nr 5

Dane są następujące deklaracje:

typedef struct eldrzewa *wskdrz;
typedef struct eldrzewa{

int klucz;
wskdrz lewy; wskdrz prawy} sdrz;

Napisz funkcje, które dla parametru

t

typu

wskdrz

opisującego

drzewo BST

:

1.

zwraca jako wartość liczbę elementów w drzewie o korzeniu

t

,

2.

zwraca jako wartość wysokość drzewa o korzeniu

t

;

3.

wypisuje (w porządku rosnącym) wszystkie elementy większe od elementu znajdującego
się w korzeniu drzewa.

4.

Do drzewa BST (na początku pustego) wstawiane są elementy 1, 2, 3, 4, 5, 6, 7. Podaj
kolejność wstawiania elementów przy której drzewo będzie miało największą
(najmniejszą) możliwą wysokość. Odpowiedź uzasadnij i uogólnij na drzewa o
elementach 1,2, …, n dla dowolnego naturalnego n.

5.

Do drzewa BST (na początku pustego):

a.

wstawiane są po kolei elementy 3, 1, 2, 5, 4, 7, 6;

b.

potem usuwane są elementy 3 i 7;

c.

na koniec wstawiana jest liczba 12.

Podaj drzewa uzyskane po każdej operacji.

6.

Które z poniższych drzew są drzewami BST:

5

8

6

4

7

9

5

7

3

2

4

9

5

8

3

2

4

7

5

3

7.

[*] Napisz funkcję, która dla danego drzewa sprawdza czy jest ono drzewem BST.

8.

Jaki jest efekt działania poniższych funkcji:

wypisz1(wskrz t)
{ if (t!=NULL){

printf("%d\n", t->klucz);

wypisz(t->lewy);

wypisz(t->prawy);

}
}

wypisz1(wskrz t)
{ if (t!=NULL){

wypisz(t->prawy);

printf("%d\n", t->klucz);

wypisz(t->lewy);

}
}

Opisz efekty na przykładowych drzewach z zadania 3 i uogólnij je.

2

6