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