10

Metodyka i Techniki Programowania II
Binarne struktury drzewiaste (Binary Search Trees) 
Piotr Pacyna, Jarosław Bułat

8.05.2010

Wstęp

Drzewo jest strukturą danych, w której każdy węzeł ma wskaźniki mogące wskazywać na inne 

węzły (w przypadku węzła binarnego używa się określenia węzeł ‘lewy’ i ‘prawy’). Jeżeli któryś ze 
wskaźników   nie   wskazuje   na   inny   węzeł,   wówczas   przechowuje   wartość    null.   Istotną   cechą 

drzewa jest brak pętli w strukturze drzewa. 

Następujące określenia dotyczą drzew.

•

Korzeń  

 

 –   węzeł   położony   najwyżej   (pierwszy   w   strukturze)   –   dla   drzewa   na   rysunku 

powyżej jest to ten, dla którego wartość klucza wynosi 52.

•

Węzeł macierzysty

 

  – dowolny węzeł, który wskazuje na jeden lub dwa węzły znajdujące się 

niżej w strukturze.

•

Węzeł potomny

 

  – węzeł, który jest wskazywany przez węzeł macierzysty. Węzeł potomny 

może być również węzłem macierzystym dla innych węzłów. 

•

Liść

    – węzeł, który nie ma węzłów potomnych.

•

Poziom

 

   – długość ścieżki od korzenia drzewa do danego węzła, mierzona liczbą ‘skoków’ 

przez węzły pośrednie. Np. węzeł 29 jest na poziomie 1, zaś 62 jest na poziomie 2.

•

Krawędź

 

  – strukturalne powiązanie dwóch węzłów reprezentowane w implementacjach na 

ogół za pośrednictwem „wskaźnika do węzła” (pointer).

Struktury   drzewiaste   łączą   zalety   znane   z   innych   struktur:   z   uporządkowanej   tablicy   oraz   z 

uporządkowanej listy jednokierunkowej. Dzięki wielokrotnym powiązaniom (pomiędzy elementem 
‘macierzystym’   a   ‘potomnymi’)   można   te   elementy   wzajemnie   uporządkować   między   sobą 

(uporządkowanie   względne)   by   potem   np.   efektywnie   przeszukiwać   strukturę   drzewa   w 
poszukiwaniu elementu.

Struktura drzewiasta jest binarna, jeżeli węzeł może posiadać co najwyżej dwa węzły potomne. 
Binarne drzewo przeszukiwań jest strukturą w której:

•

Węzły przechowują elementy (obiekty danych) indeksowane wartością klucza, który służy 

do identyfikowania tych elementów,

•

dla każdego węzła “x” w drzewie wszystkie elementy przechowywane w lewym pod-drzewie 
węzła   “x”   charakteryzują   się  mniejszymi   lub   równymi  wartościami   klucza   niż   elementy 

przechowywane w węźle ”x”, oraz

•

wszystkie elementy przechowywane w prawym pod-drzewie węzła “x” mają wartości kluczy 
większe od elementu przechowywanego w węźle ”x”.

Takie drzewo jest uporządkowanym drzewem binarnym.

Uporządkowane   drzewa   binarne   (drzewa   binarne   przeszukiwań)   mają   ważną   właściwość: 

uporządkowane przeszukiwanie drzewa pozwala na odczytanie elementów w rosnącym porządku 
odpowiadającej im wartości klucza.

.

Dla drzewa przedstawionego powyżej porządek ten wynosi: 13, 18, 23, 32, 36, 44, 54, 59, 64, 

73, 81, 85, 92. 

Warunkiem uzyskania takiego wyniku jest budowanie i powiększanie (pomniejszanie) drzewa w 
sposób   kontrolowany.   Wówczas   drzewa   binarne   umożliwiają   także   efektywne   wyszukiwanie 

elementów według wartości klucza. 

Czas   wykonania   procedury   poszukiwania   elementu   (lub   wstawiania   elementu   w   odpowiednie 

miejsce)  zależy od wysokości  h  drzewa,  O(h). Wysokość drzewa   binarnego  jest w przedziale 
log

2

n ≤ h ≤ n, gdzie n jest liczbą węzłów, tak więc wartość O(h) z pewnością leży w przedziale; 

O(log n) - O(n). W najgorszym przypadku czas przeszukania wynosi O(n), jednak średnia wartość 
czasu wykonania procedury (liczona dla różnych ‘przypadków’ kształtu drzewa) wynosi O(log n).

Kształt drzewa zależy od wartości kluczy, które pojawiają się wraz z elementami wstawianymi do 
drzewa.

Ćwiczenie 1. Zakładanie drzewa 

1. Przestudiuj kod w pliku nagłówkowym bintree.h, zwracając uwagę na deklaracje funkcji:

TBinTree MakeBinTreeNode( TBinTreeData data, int key );

void InsertLeftChild( TBinTree *parent, TBinTree node );

void InsertRightChild( TBinTree *parent, TBinTree node );

2. Przestudiuj uważnie implementacje wyżej wymienionych funkcji przeglądając kod zawarty 

w pliku bintree.c .

3. Przestudiuj kod programu  main_bintree.c  i załóż strukturę drzewiastą składającą się z 

węzłów identyfikowanych jako A, B, C, D, E, F, G, H z wartościami klucza odpowiednio a, b, 
c, d, e, f, g, h.  (do kompilacji użyj załączonego programu Makefile)

Ćwiczenie 2. Łączenie drzew
Wygeneruj drugie drzewo i połącz je ze sobą programowo (uzupełniając kod w main_bintree.c) 
w dowolny sposób.

•

Czy powstałe w ten sposób drzewo jest drzewem binarnym ?

•

Czy jest drzewem uporządkowanym ?  

Ćwiczenie 3.  Liczba liści drzewa
Napisz funkcję, int leafCount( TBinTree tree ), która policzy elementy niemające potomków, 

czyli liście drzewa.

Ćwiczenie 4. Wysokośc drzewa
Napisz funkcję int height( TBinTree tree ),  która policzy wysokość drzewa. 

Ćwiczenie 5. Pokolenie

Napisz funkcję  int generation( TBinTree tree, int level  ), która policzy ilość węzłów na 
określonym poziomie drzewa.

Ćwiczenie 6. Koszt gałęzi

Napisz funkcję int maxPathSum(TBinTree tree) , która policzy największy koszt gałęzi spośród 
wszystkich gałęzi występujących w drzewie. Jako koszt   przyjmujemy sumę wartości kluczy od 

korzenia drzewa do wszystkich liści, wliczając wartości elementów przechowywanych w korzeniu i 
w liściu.

Ćwiczenie 7. Rekursywne przeszukiwanie drzewa binarnego (nadobowiązkowe)

Wykorzystując kod źródłowy dołączony do laboratorium skonstruuj strukturę drzewiastą binarną 
uporządkowaną   składającą   się   z   węzłów   identyfikowanych   jako  A,   B,   C,   D,   E,   F,   G,   H   z 

wartościami klucza odpowiednio 1, 5, 10, 15, 20, 25, 30, 35. Następnie wykonaj przeszukiwanie 
według   wartości   kluczy   rekursywne   oraz   nierekursywne   (uzupełnij   brakujący   kod).   Porównaj 

szybkość działania, łatwość implementacji oraz zwięzłość kodu źródłowego obu implementacji.