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);

)

)

Wyszukiwarka

Podobne podstrony:
ALG0 100 Rozdział 5. Struktury danyi z tych przypadków w istniejącej liście trzeba znaleźć miejsce
ALG0 110 Rozdział 5. Struktury danych Rysunek 5-9 zawiera już kilka nowości w porównaniu z tym, co
ALG0 120 Rozdział 5. Struktury danych i if (pos!=q) rsturn(O);    II element nie
Alg0 120 Rozdział 5. Struktury danych i if (pos!=q) rsturn(O);    II element nie
ALG4 124 Rozdział 5. Struktury danych Co jednak z dołączaniem elementów do listy? Poniżej są omówio
ALG0 130 Rozdział 5. Struktury danych Symboliczny stos znajdujący się pod każdą z sześciu grup inst
ALG4 134 Rozdział 5. Struktury danyct Jak to zwykle bywa, możliwych implementacji kolejek jest co n
ALG0 140 Rozdział 5. Struktury danych porządek. Czy czasem owa procedura nie jest na tyle kosztowna
ALG6 146 Rozdział 5. Struktury danycti Jak widać, inteligentne użycie tablic może nam podsunąć możl
ALG2 152 Rozdział 5. Struktury danytl 5.; raturn oblicz(w->lcwy)+oblicz(w->prawy); case - :
ALG0 170 Rozdział 6. Oerekursywaci 6.3. Uwaga: Wywołanie rekurencyjne procedury P zawarte w jakiejk
ALG0 30 Rozdział 2. Rekurencja 2.2 potwornie skomplikowany: klocków jest cala masa i niespecjalnie
ET0 150 Rozdział 9. Jakość usług turystycznych badaniem opinii konsumentów) - SMART. Metoda ta pozw
ALG0 20 Rozdział 1. Zanim wystartujemy (Na marginesie warto dodać, że przedsiębiorstwo Hollcritha
ALG0 50_ _Rozdział2. Rekurencja Odpowiadający temu rozumowaniu program przedstawia się
Alg0 60 Rozdział 3. Analiza sprawności algorytmów •    Znak graficzny 3 należy czyta
ALG0 70 Rozdział 3. Analiza sprawności algorytmów Przykład: SRL=xn-3x„.i+2 x„ -2=0 daje
ALG 0 90 Rozdział 4. Algorytmy sortowania 90 Rozdział 4. Algorytmy sortowania Rys. 4 - 8. Sortowanie

więcej podobnych podstron