ALG0

150 Rozdział 5. Struktury danytl

Jak jednak obejrzeć zawartość drzewa, które tak pieczołowicie stworzyliśmy’ Wbrew pozorom zadanie jest raczej trywialne i sprowadza się do wykorzystania własności „topograficznych” drzewa binarnego. Sposób interpretacji form wyrażenia (czy' jest ona infiksowa, prefiksowa czy też postfiksowa) zależy bowiem tylko i wyłącznie od sposobu przechodzenia przez gałęzie drzewa!

Popatrzmy na realizację funkcji służącej do wypisywania drzewa w postaci klasycznej, tzn. wrostkowej. Jej działanie można wyrazić w postaci prostego algorytmu rekurencyjnego:

wypisz(w)

{

jeśli wyrażenie w jest liczbą to wypisz ją: jeśli wyrażenie w jest operatorem og to wypisz w kolejności: (wypiszfw-t left) op wypisz(w-» right))

}

Realizacja programowa jest oczywiście dosłownym tłumaczeniem powyższego zapisu:

void pisz infix(struct wyrażenie ”w)

(

// funkcja wypisuje w postaci wrostkowej if(w->op==¹0¹) // wartość liczbowa... cout << w->val; else

(

cout <<

pisz_infix(w->lewy) ; cout c< w->op;

pi .S7_infix (w-sprawy) ;

cout

I

)

W analogiczny sposób możemy zrealizować algorytm wypisujący wyrażenie w formie beznawiasowej, czyli ONP:

void pisz_prefix;struct wyrażenie *w)

(

I/ funkcja wypisuje w postaci prefiksowej if !w->op=='0') II wartość liczbowa...

cout«w >val<<" else {

cout << w->op « "

pi S7._pref ix (w->lewy) ; pisz_prefix(w->prawy);

)

)