ALG5

5.6. Drzewa i ich reprezentacje 145

sposobu korzystania z takiej reprezentacji. Otóż, dowolne wyrażenie arytmetyczne może być zapisane w kilku odmiennych postaciach związanych z położeniem operatorów: przed swoimi argumentami, po nich oraz klasycznie pomiędzy nimi (jeśli oczywiście mamy do czynienia tylko z wyrażeniami dwuargu-mentowymi, co pozwolimy sobie tutaj dla uproszczenia przykładów założyć).

Struktura danych z tego rysunku jest zwykłym drzewem binarnym, posiadającym dwa pola przeznaczone do przechowywania danych (operator i val) oraz tradycyjne wskaźniki do lewego i prawego odgałęzienia naszego odwróconego „do góry nogami” drzewa. Umówimy się ponadto, że w przypadku, gdy pole operator zostanie zainicjowane jakąś bezsensowną wartością (tutaj '0’; nie jest to żaden znany operator), to wówczas pole val ma jakąś wartość, którą możemy uznać za sensowną. Taka dualna reprezentacja może posłużyć do łatwego rozróżnienia przy użyciu tylko jednego typu rekordów, dwóch typów węzłów: wartości (listek drzewa) i operatora arytmetycznego, wiążącego w ogólnym przypadku trzy typy węzłów:

lewy potomek	prawy potomek
wyrażenie	wyrażenie
wyrażenie	wartość
wartość	wyrażenie

Tabela 5 - 2.

Typy węzłów w drzewie opisującym wy rażenie arytmetyczne.

Jeśli napiszemy odpowiednie funkcje obsługujące powyższą strukturę danych wedle przyjętych przez nas reguł postępowania, to możemy przy pomocy takiej prostej reprezentacji wyrazić dowolnie skomplikowane wyrażenia arytmetyczne, wykonywać na nich operacje, różniczkować je etc. Wszystko zależy wyłącznie od tego, co zamierzamy uzyskać - możliwych zastosowań jest dość sporo, a ponadto, jak się okaże już wkrótce, jeśli do roboty zaprzęgniemy rekurencję, to algorytmy obsługi drzew binarnych (i nie tylko), stają się bardzo proste i zrozumiałe na pierwszy rzut oka.

Czy' reprezentacja przy pomocy rekurencyjnych struktur danych jest optymalna? Na to pytanie można odpowiedzieć sensownie jedynie mając przed oczami ostateczne zastosowanie implementowanego drzewa: jeśli nie dbamy zbytnio o zajęlość pamięci, a zależy' nam na łatwości implementacji, to reprezentacja tablicowa może okazać się nawet lepsza od tej klasycznej, zaprezentowanej powyżej.

Jak zapamiętać drzewo w tablicy? Nie jest to bynajmniej dla nas problem nowy, w §5.5 została podana dość prosta metoda na zapamiętanie w tablicy innej „drzewiastej” struktury danych — sterty. Podobnie w §5.2.2 poznaliśmy tzw. metodę tablic równoległych do reprezentacji list z wieloma kryteriami sortowania.