ALG4

144 Rozdział 5. Struktury danych

studia dotyczące drzew można znaleźć w zasadzie w większości książek poświęconych ogólnie strukturom danych. Ponieważ jednak te ostatnie nie są celem samym w sobie (o czym bardzo często autorzy książek o algorytmice zapominają ..), to wierzę, że bardziej praktyczne podejście do tematu zostanie przez większość Czytelników zaakceptowane.

Nasze rozważania zaczniemy od najpopularniejszych i najczęściej używanych drzew binarnych, których użyteczność do rozwiązywania przeróżnych zagadnień algorytmicznych jest niezaprzeczalna.

Co to są zatem drzew a binarne? Są to struktury bardzo podobne do list jednokierunkowych, ale wzbogacone o jeszcze jeden wymiar (lub kierunek jak kto woli...).

Podstawowa komórka służąca do konstrukcji drzewa binarnego ma postać: struct wezel

int intTo; // lub dowolny inny typ danych struct wezel *lewy,*prawy;

Jak łatwo jest zauważyć, w miejsce jednego wskaźnika następny (jak w liście jednokierunkowej) mamy do czynienia z dw'oma wskaźnikami o nazwach lewy i prawy, będącymi wskaźnikami do lewej i prawej gałęzi drzewa binarnego. Aby dobrze zrozumieć sposób działania i użyteczność drzew binarnych, popatrzmy na rysunek 5 - 22.

2

operator='0' =>

znaczenie ma polecał

Konwencjo:

char operator;

float val;

wezeł *lewy, *prawy;

struct węzeł

operator*'etc. => pole val jest bez znaczeni?

Rys. 5 - 22.

Drzewa binarne i wyrażenia arytmetyczne.

{(2+3)+(7*9)}*12.5

Pokazuje on jeden z możliwych przykładów' zastosowania drzew binarnych, a mianowicie reprezentowanie wyrażeń arytmetycznych. Do tego przykładu jeszcze powrócimy w dalszych paragrafach, na razie wystarczy ogólny opis