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:

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.

Wyszukiwarka

Podobne podstrony:
ALG1 5.6. Drzewa i ich reprezentacje 151 Jak łatwo zauważyć, w zależności od sposobu przechadzania
ALG7 5.6. Drzewa i ich reprezentacje 147 Numery znajdujące się przy węzłach mają charakter wyłączni
ALG9 5.6. Drzewa i ich reprezentacje 149 stwierdzeniem, że z punktu widzenia komputera ON P jest is
13861 lastscan19 Położenie polityczno - prawne obszrow morskich, zasady ich delimitacji oraz sposoby
ALG5 Rozdział 6Derekursywacja Podjęcie tematu przekształcania algorytmów rekurencyjnych na ich post
ALG$8 248 RozdziałłO. Elementy algorytmiki gratów10.2.Sposoby reprezentacji grafów Poznane uprzednio
292 Badanie sił przyrody i ocena pożytecznej ich wartości. kilka sposobów do otrzymywania saletry, a
IMG258 (2) •    Sposób korzystania •    Wynagrodzenie dla twórcy Prawa
OMiUP t1 Gorski52 Sposób korzystania z wykresu: Przykład A Gęstość oleju, mierzona w temperaturze 15
kat C 43 PODRĘCZNIK KATEGORIA C •    sygnalizatory określające sposób korzystania z p
Dziawgo; Wyznacznik i rząd macierzy 3 62 Wyznacznik i rząd macierzyRozwiązanie: I sposób: Korzystamy
str. 131 a.    Wykorzystanie czasu str. 131 b.    Sposób korzysta
jest niezbędne do budowy odpowiedniej ich reprezentacji w postaci modelu rzeczywistości. Należy zwró

więcej podobnych podstron