ALG7

5.6. Drzewa i ich reprezentacje 147

Numery znajdujące się przy węzłach mają charakter wyłącznie ilustracyjny - ich wybór jest raczej dowolny i nie podlega żadnym szczególnym regułom... chyba żc sobie sami je wymyślimy na użytek konkretnej aplikacji. W ramach kolejnej konwencji umówmy się, że jeśli ojciec[x] jest równy*, to mamy do czynienia z pierwszym elementem drzewa.

Teraz, gdy już wiemy, jak reprezentować drzewa wykorzystując dostępne w C i i (oraz w każdym nowoczesnym języku programowania) mechanizmy, spróbujmy popatrzeć na możliwe sposoby przechadzania się po gałęziach drzew'...

5.6.1.Drzewa binarne i wyrażenia arytmetyczne

Nasze rozważania o drzewach będziemy prowadzić poprzez prezentację dość rozbudowanego przykładu, na podstawie którego zobrazowane zostaną fenomeny, z którymi programista może się zetknąć, oraz mechanizmy, z których będzie on musiał sprawnie korzystać w celu efektywnego wykorzystania nowo poznanej struktury danych.

Problematyka będzie dotyczyła kwestii zaanonsowanej już na rysunku 5 - 22. Zobaczyliśmy tam, że drzewo doskonale się nadaje do reprezentacji informatycznej wyrażeń arytmetycznych, bardzo naturalnie zapamiętując nie tylko informacje zawarte w wyrażeniu (tzn. operandy i operatory), ale i ich logiczną strukturę, która daje się poglądow-o przedstawić właśnie w postaci drzewa.

Przypomnijmy jeszcze raz typ komórki, który może służyć - zgodnie z ideą przedstawioną na rysunku 5 - 22 - do zapamiętywania zarówno operatorów (ograniczymy się tu do:    * i do dzielenia wyrażonego przy pomocy : lub /),

jak i operandów (liczb rzeczywistych).

wyrazen.cpp

struct wyrażenie (

double val; char    op;

wyrażenie *lewy,*prawy;

);

Inicjacja takiej komórki determinuje późniejszą interpretację jej zawartości. Jeśli w polu ‘op’ zapamiętamy wartość ‘0’, to będziemy uważali, że komórka nie jest operatorem i wartość zapamiętana w polu val ma sens. W odwrotnym zaś przypadku będziemy zajmowali się wyłącznie polem op’ bez zwracania uwagi na to, co znajduje się w val. Popatrzmy na rysunek 5 - 24, który ukazuje kilka pierwszych etapów tworzenia drzewa binarnego wyrażenia arytmetycznego.

Do tworzenia drzewa użyjemy dobrze nam znanego z poprzednich dyskusji stosu (patrz §5.3). Tym razem będzie on służył do zapamiętywania wskaźników do rekordów typu struci wyrażenie, co implikuje jego deklarację przez STOS<wyrażenie *> s (Jak widać warto było raz się pomęczyć i stworzyć stos w postaci klasy szablonowej).