ALG1

5.6. Drzewa i ich reprezentacje 151

Jak łatwo zauważyć, w zależności od sposobu przechadzania się po drzewie możemy w różny sposób przedstawić jego zawartość bez wykonywania jakiejkolwiek zmiany w strukturze samego drzewa!

Reprezentacja wyrażeń arytmetycznych byłaby z pewnością niekompletna, gdybyśmy jej nie uzupełnili funkcjami do obliczania ich wartości. Zanim jednak cokolwiek zechcemy obliczać, musimy dysponować funkcją, która sprawdzi, czy wyrażenie znajdujące się w drzewie jest prawidłowo skonstruowane, tzn. czy przykładowo nie zawiera nieznanego nam operatora arytmetycznego.

Zauważmy, że o poprawności drzewa decyduje już sam sposób jego konstruowania z użyciem stosu. Pomimo lego ułatwienia dysponowanie dodatkową funkcją spraw dzającą poprawność drzewa jest jednak mało kosztowne - dosłownie kilka linijek kodu - a użyteczność takiej dodatkowej funkcji jest oczywista

int poprawne ; struct wyrażenie *w)

(

// czy wyrażenie jest poprawne składniowo? if(w->op=='0')

return 1; // OK, wg naszej konwencji jest to liczba switch(w->op!

case	^1 +
case
case	' *
case
case	*/

// to sa znane operatory

return (poprawne(w->lewy)‘poprawne(w->prawy)); default :

return (0);    //błąd!!! -> operator nieznany

)

Nie będę nikogo zachęcał do zrealizowania powyższych funkcji w formie itera-cyjnej - jest to oczywiście wykonalne, ale rezultat nie należy do specjalnie czytelnych i eleganckich.

Przejdźmy wreszcie do prezentacji funkcji, która zajmie się obliczeniem wartości wyrażenia arytmetycznego. Jego schemat jest bardzo zbliżony do tego zastosowanego w funkcji poprawne:

double oblicz(struct wyrażenie *w)

(

if(poprawne(w)) // wyrażenie poprawne? if(w->op=='0 *)

return (w >val); // pojedyncza wartość else

switch (w->op)

I

case '+¹: