Matematyka Dyskretna

Andrzej Szepietowski

25 czerwca 2002 roku

Rozdział 1

Struktury danych

1.1

Listy, stosy i kolejki

Lista to uporz¸adkowany ci¸ag elementów. Przykładami list s¸a wektory lub tablice jednowy-
miarowe. W wektorach mamy dost¸ep do dowolnego elementu, poprzez podanie indeksu
tego elementu.

Przykład 1.1 W j¸ezyku Pascal przykładem typu tablicy jednowymiarowej jest

array[1..N] of integer.

Je˙zeli mamy zmienn¸a tego typu

a:array[1..N] of integer,

to tablica

a

zawiera

N

elementów

a[1], a[2], ... ,a[N].

W programie mo˙zemy odwoływa´c si¸e do całej tablicy, na przykład w instrukcji przypisania

a:=b,

lub do pojedynczych elementów:

a[i]:=a[i+1].

Mo˙zemy tak˙ze u˙zywa´c tablic dwu lub wi¸ecej wymiarowych. Przykładem tablicy dwuwy-
miarowej jest typ

array[1..N,1..M] of real.

Zmienna

c:array[1..N,1..M] of real

zawiera

elementów. Dla ka˙zdej pary liczb

spełniaj¸acej warunki

,

, element

c[i,j]

zawiera liczb¸e typu

real.

Czasami wygodniej posługiwa´c si¸e listami bez u˙zywania indeksów. Przykładami list,

których mo˙zna u˙zywa´c bez konieczno´sci odwoływania si¸e do indeksów poszczególnych
elementów, s¸a kolejki i stosy.

3

4

Rozdział 1. Struktury danych

Definicja 1.2 Kolejka jest list¸a z trzema operacjami:

dodawania nowego elementu na koniec kolejki,

zdejmowania pierwszego elementu z pocz¸atku kolejki,

sprawdzania, czy kolejka jest pusta.

Taki sposób dodawania i odejmowania elementów jest okre´slany angielskim skrótem

FIFO (first in first out, czyli pierwszy wszedł — pierwszy wyjdzie). Przykłady kolejek
spotykamy w sklepach, gdzie klienci czekaj¸acy na obsłu˙zenie tworz¸a kolejki.

Definicja 1.3 Stos jest list¸a z trzema operacjami:

dodawania elementu na wierzch stosu,

zdejmowania elementu z wierzchu stosu,

sprawdzania, czy stos jest pusty.

Na stosie dodajemy i odejmujemy elementy z tego samego ko ´nca, podobnie jak w

stosie talerzy spi¸etrzonym na stole. Talerze dokładane s¸a na wierzch stosu i zdejmowa-
ne z wierzchu stosu. Taka organizacja obsługi listy okre´slana jest angielskim skrótem
LIFO (last in first out, czyli ostatni wszedł – pierwszy wyjdzie). Niektórzy w ten spo-
sób organizuj¸a prac¸e na biurku. Przychodz¸ace listy układaj¸a na stosie i jak maj¸a czas, to
zdejmuj¸a jeden list i odpowiadaj¸a na niego.

Przyjrzyjmy si¸e zastosowaniu kolejki lub stosu do szukania. Przypu´s´cmy, ˙ze szukamy

przez telefon pewnej informacji (na przykład chcieliby´smy si¸e dowiedzie´c, kto z naszych
znajomych ma pewn¸a ksi¸a˙zk¸e).

Algorytm szukania ksi¸a˙zki w´sród znajomych

tworzymy STOS, który na pocz¸atku jest pusty,

wkładamy na STOS numer telefonu swojego znajomego,

powtarzamy dopóki na stosie s¸a jakie´s numery:

zdejmujemy z wierzchu STOSU jeden numer telefonu,

dzwonimy pod ten numer,

je˙zeli osoba, do której si¸e dodzwonili´smy, posiada szukan¸a ksi¸a˙zk¸e, to ko-

niec poszukiwa ´n,

je˙zeli nie posiada ksi¸a˙zki, to pytamy j¸a o numery telefonów jej znajomych,

którzy mog¸a mie´c ksi¸a˙zk¸e (lub zna´c kogo´s kto j¸a ma); ka˙zdy nowy numer zostaje
dopisany do STOSU.

W powy˙zszym algorytmie zamiast stosu mo˙ze by´c u˙zyta kolejka.

1.2. Drzewa binarne

5

1.2

Drzewa binarne

Drzewo jest hierarchiczn¸a struktur¸a danych. Jeden element drzewa, zwany korzeniem, jest
wyró˙zniony. Inne elementy drzewa s¸a jego potomstwem lub potomstwem jego potomstwa
itd. Terminologia u˙zywana do opisu drzew jest mieszanin¸a terminów z teorii grafów, bo-
taniki i stosunków rodzinnych. Elementy drzewa nazywa si¸e wierzchołkami lub w¸ezłami.
Li´scie to wierzchołki nie maj¸ace potomstwa. Drzewa cz¸esto przedstawia si¸e w formie
grafu, gdzie ka˙zdy wierzchołek jest poł¸aczony kraw¸edzi¸a ze swoim ojcem i ze swoimi
dzie´cmi (swoim potomstwem). Dla ka˙zdego elementu w drzewie istnieje dokładnie jedna
´scie˙zka prowadz¸aca od korzenia do tego wierzchołka.

Drzewa binarne to takie drzewa, w których ka˙zdy wierzchołek ma co najwy˙zej dwóch

synów. Do oznaczania wierzchołków w drzewie binarnym wygodnie jest u˙zywa ´c ci¸agów
zer i jedynek. Niech

oznacza zbiór wszystkich sko ´nczonych ci¸agów zer i jedy-

nek. Zbiór ten zawiera ci¸ag pusty (długo´sci 0), oznaczany przez

. Wierzchołki drzewa

oznaczamy w nast¸epuj¸acy sposób:

korze´n drzewa oznaczamy przez

— pusty ci¸ag,

je˙zeli jaki´s wierzchołek jest oznaczony przez

, to jego synowie oznaczeni s¸a przez

i

.

Rysunek 1.1: Przykład drzewa binarnego

Przy takim oznaczeniu wierzchołków drzewa binarnego nazwa wierzchołka

mówi

nam, jaka ´scie˙zka prowadzi od korzenia do

. Na przykład, aby doj´s´c od korzenia do

wierzchołka

nalezy: pój´s´c w prawo do

, potem znowu w prawo do

, a na ko ´ncu w

lewo do

.

6

Rozdział 1. Struktury danych

Je˙zeli mamy drzewo binarne

, to z ka˙zdym wierzchołkiem

mo˙zemy skojarzy ´c

poddrzewo

zło˙zone z wierzchołka

i wszystkich jego potomków. Na przykład w

drzewie przedstawionym na rysunku 1.1 wierzchołek

wyznacza poddrzewo

przedstawione na rysunku 1.2.

Rysunek 1.2: Poddrzewo

Mówimy te˙z, ˙ze drzewo

składa si¸e z korzenia (wierzchołka

), z lewego poddrzewa

i z prawego poddrzewa

.

Wysoko´sci¸a drzewa nazywamy długo´s´c (liczb˛e kraw˛edzi) najdłu˙zszej ´scie˙zki w drze-

wie prowadz¸acej od korzenia do li´scia. Na przykład drzewo z rysunku 1.1 jest wysoko´sci
3.

1.3

Drzewa wyra˙ze ´n arytmetycznych

Przykładem zastosowania drzew binarnych s¸a drzewa wyra˙ze ´n arytmetycznych. Najpierw
przykład. Na rysunku 1.3 przedstawiono drzewo wyra˙zenia

. W drzewie tym ka˙z-

dy wierzchołek ma etykiet¸e. Li´scie etykietowane s¸a stałymi albo zmiennymi. Wierzchołki
nie b¸ed¸ace li´s´cmi etykietowane s¸a operacjami arytmetyczymi. Ka˙zdemu wierzchołkowi
w drzewie mo˙zemy przypisa´c wyra˙zenie arytmetyczne według nast¸epuj¸acej zasady:

dla li´sci wyra˙zeniami s¸a etykiety tych li´sci (stałe lub zmienne),

je˙zeli wierzchołek

ma etykiet¸e

, a jego synom przypisano wyra˙zenia

i

, to wierzchołkowi

przypisujemy wyra˙zenie

!

.

Przykład 1.4 W drzewie z rysunku1.3 wierzchołkowi z etykiet ˛

a

odpowiada wyra˙zenie

, wierzchołkowi z etykiet ˛

a

wyra˙zenie

"

, a korzeniowi wyra˙zenie

#

$%"

!'&

Wyra˙zenie to zawiera wi¸ecej nawiasów, ni˙z to si¸e zwykle stosuje. Normalnie to samo wy-
ra˙zenie przedstawiamy bez nawiasów w postaci

()

.

1.3. Drzewa wyra˙ze ´n arytmetycznych

7

Rysunek 1.3: Drzewo wyra˙zenia

)

Opuszczenie nawiasów mo˙ze prowadzi´c do niejednoznaczno´sci lub mo˙ze zmieni´c

sens wyra˙zenia. Na przykład wyra˙zenie

%

po opuszczeniu nawiasów stanie si¸e identyczne z wyra˙zeniem

"$"

i zmieni sens.

Drzewo, które odpowiada wyra˙zeniu

%

, przedstawiono na rysunku 1.4.

Rysunek 1.4: Drzewo wyra˙zenia

()

Drzewo wyra˙zenia arytmetycznego oddaje logiczn¸a struktur¸e i sposób obliczania tego

wyra˙zenia.

8

Rozdział 1. Struktury danych

Istnieje sposób przedstawiania wyra˙ze ´n arytmetycznych nie wymagaj¸acy nawiasów.

Jest to tak zwana notacja polska lub Łukasiewicza. Jest ona te˙z nazywana notacj¸a postfixow¸a,
poniewa˙z znak operacji stoi na ko ´ncu wyra˙zenia, za argumentami, czyli wyra˙zenie w no-
tacji postfixowej ma posta´c:

pierwszy argument — drugi argument — operacja.

Notacja, do jakiej jeste´smy przyzwyczajeni, nazywa si¸e infixowa, poniewa˙z operacja znaj-
duje si¸e pomi¸edzy argumentami, czyli wyra˙zenie w notacji infixowej ma posta ´c:

pierwszy argument — operacja — drugi argument.

Przykład 1.5 Wyra˙zenie w postaci postfixowej

!

ma w postaci infixowej posta´c

a wyra˙zenie

!

jest postfixow¸a postaci¸a wyra˙zenia

()

&

W wyra˙zeniach w postaci postfixowej nie potrzeba nawiasów. Warto´s´c wyra˙zenia mo˙zna
w sposób jednoznaczny odtworzy´c z samego wyra˙zenia za pomoc¸a nast˛epuj ˛

acego algo-

rytmu.:

Algorytm obliczania warto´sci wyra˙zenia w postaci postfixowej.

Dla kolejnych elementów zapisu wyra˙zenia:

je˙zeli element jest stał¸a lub zmienn¸a, to wkładamy jego warto´s´c na stos,

je˙zeli element jest znakiem operacji, to:

zdejmujemy dwie warto´sci z wierzchu stosu,

wykonujemy operacj¸e na tych warto´sciach,

obliczon¸a warto´s´c wkładamy na wierzch stosu,

po przej´sciu całego wyra˙zenia jego warto´s´c znajduje si¸e na stosie.

Przykład 1.6 Zademonstrujmy ten algorytm na przykładzie wyra˙zenia:

"

Załó˙zmy, ˙ze zmienne maj¸a nast¸epuj¸ace warto´sci:

,

,

,

,

.

Poni˙zsza tabela przedstawia zawarto´s´c stosu po przeczytaniu kolejnych elementów wyra-
˙zenia.

1.4. Przeszukiwanie drzew binarnych

9

czytany element

stos

a

3,

b

3, 2,

c

3, 2, 1,

3, 3,

9,

d

9, 4,

e

9, 4, 2,

9, 2,

11.

1.4

Przeszukiwanie drzew binarnych

Zajmiemy si¸e teraz dwoma algorytmami przeszukiwania drzew (binarnych): przeszuki-
wanie w gł¸ab i wszerz. Ró˙zni¸a si¸e one rodzajem u˙zytych struktur danych. W algorytmie
przeszukiwania w gł¸ab u˙zyjemy stosu, a w algorytmie przeszukiwania wszerz u˙zyjemy
kolejki.

1.4.1

Przeszukiwanie drzewa w gł ˛

ab

Algorytm przeszukiwania drzewa w gł¸ab.

Dane wej´sciowe: drzewo

.

odwiedzamy korze ´n

i wkładamy go na STOS; zaznaczamy

jako wierzchołek

odwiedzony,

dopóki STOS nie jest pusty, powtarzamy:

je˙zeli

jest wierzchołkiem na wierzchu STOSU, to sprawdzamy, czy istnieje

syn

wierzchołka , który nie był jeszcze odwiedzony, najpierw sprawdzamy

,

a potem

.

je˙zeli takie

si¸e znajdzie, to odwiedzamy

, wkładamy go na wierzch STO-

SU i zaznaczamy jako wierzchołek odwiedzony,

je˙zeli takiego

nie ma, to zdejmujemy

ze STOSU i cofamy si¸e do wierz-

chołka b¸ed¸acego na stosie pod spodem.

Przykład 1.7 Poni˙zsza tabela pokazuje jaki wierzchołek jest odwiedzany i jaka jest za-
warto´s´c stosu po ka˙zdej kolejnej iteracji p¸etli algorytmu, gdy przeszukiwane jest drzewo
z rysunku 1.1.

10

Rozdział 1. Struktury danych

Wierzchołek

STOS

0

,0

00

,0,00

0

,0

01

,0,01

0

,0

1

,1

10

,1,10

1

,1

11

,1,11

110

,1,11,110

11

,1,11

111

,1,11,111

11

,1,11

1

,1

W metodzie przeszukiwania w gł¸ab po ka˙zdym kroku algorytmu wierzchołki znajduj¸ace
si¸e na stosie tworz¸a ´scie˙zk¸e od wierzchołka wej´sciowego do wierzchołka aktualnie od-
wiedzanego. Zauwa˙zmy, ˙ze nazwa ka˙zdego wierzchołka na stosie jest prefiksem (przed-
rostkiem) nazwy nast¸epnego wierzchołka. Dlatego wystarczy przechowywa ´c ostatnie bity
wierzchołków na stosie. Nie jest te˙z konieczne zaznaczanie, które wierzchołki były ju˙z
odwiedzone, wystarczy zauwa˙zy´c, ˙ze:

je˙zeli przyszli´smy do wierzchołka

od jego ojca, to ˙zaden z synów

nie był jeszcze

odwiedzany,

je˙zeli przyszli´smy do wierzchołka

od lewego syna

(po zdj¸eciu

ze stosu), to

odwiedzony był tylko lewy syn,

je˙zeli przyszli´smy do wierzchołka

od prawego syna

(po zdj¸eciu

ze stosu), to

odwiedzeni ju˙z byli obaj synowie.

Oto prostsza wersja algorytmu przeszukiwania w gł¸ab:

Algorytm przeszukiwania drzewa w gł¸ab (druga wersja).

Dane wej´sciowe: drzewo

.

odwiedzamy korze ´n

i wkładamy go na STOS,

dopóki STOS nie jest pusty, powtarzamy:

Je˙zeli

jest aktualnie odwiedzanym wierzchołkiem i

Je˙zeli ostatni¸a operacj¸a na stosi było wło˙zenie nowego elementu, to:

Je˙zeli

, to przejd´z do

i włó˙z 0 na stos,

Je˙zeli

ale

, to przejd´z do

i włó˙z 1 na stos,

1.4. Przeszukiwanie drzew binarnych

11

Je˙zeli

oraz

, to zdejmij ostatni element ze stosu i przejd´z do

ojca wierzchołka .

Je˙zeli ostatni¸a operacj¸a na stosie było zdj¸ecie 0 to:

Je˙zeli

, to przejd´z do

i włó˙z 1 na stos,

Je˙zeli

, to zdejmij ostatni element ze stosu i przejd´z do ojca wierz-

chołka .

Je˙zeli ostatni¸a operacj¸a na stosie było zdj¸ecie 1 to: zdejmij ostatni element ze stosu
i przejd´z do ojca wierzchołka .

Przykład 1.8 Poni˙zsza tabela pokazuje jaki wierzchołek jest odwiedzany i jaka jest za-
warto´s´c stosu po ka˙zdej kolejnej iteracji p¸etli drugiego algorytmu, gdy przeszukiwane jest
drzewo z rysunku 1.1.

Wierzchołek

STOS

0

,0

00

,0,0

0

,0

01

,0,1

0

,0

1

,1

10

,1,0

1

,1

11

,1,1

110

,1,1,0

11

,1,1

111

,1,1,1

11

,1,1

1

,1

Zauwa˙zmy, ˙ze etykiety na stosie zł¸aczone razem tworz¸a nazw¸e aktualnie odwiedzanego
wierzchołka.

1.4.2

Przeszukiwanie drzewa wszerz

Nast¸epny algorytm przeszukiwania drzew u˙zywa kolejki jako pomocniczej struktury da-
nych.

Algorytm przeszukiwania wszerz.

Dane wej´sciowe: drzewo

.

odwiedzamy korze ´n drzewa

i wkładamy go do KOLEJKI.

12

Rozdział 1. Struktury danych

dopóki KOLEJKA nie jest pusta, powtarzamy:

bierzemy jeden wierzchołek

z pocz¸atku KOLEJKI,

odwiedzamy wszystkiech synów wierzchołka

i wkładamy je na koniec

kolejki.

Poni˙zej przedstawiono odwiedzane wierzchołki oraz zawarto´s´c kolejki po ka˙zdej kolejnej
iteracji p¸etli algorytmu przeszukiwania wszerz drzewa przedstawionego na rysunku 1.1.

wierzchołki

KOLEJKA

0,1

0,1

00,01

1,00,01

10,11

00,01,10,11

-

01,10,11

-

10,11

-

11

110,111

110,111

-

111

-

-

W metodzie przeszukiwania wszerz wierzchołki s¸a przeszukiwane w kolejno´sci od wierz-
chołków b¸ed¸acych najbli˙zej wierzchołka pocz¸atkowego do wierzchołków b¸ed¸acych dalej.

1.4.3

Rekurencyjne algorytmy przeszukiwania drzew

Istnieje prosty i ciekawy sposób uzyskiwania postaci postfixowej wyra˙zenia arytmetycz-
nego z drzewa tego wyra˙zenia. Aby uzyska´c posta´c postfixow¸a wyra˙zenia, nale˙zy prze-
szuka´c drzewo tego wyra˙zenia w pewien okre´slony sposób, zwany przeszukiwaniem po-
storder.

Przeszukiwanie postorder. Aby przeszuka´c (pod)drzewo maj¸ace swój korze ´n w wierz-
chołku

:

przeszukujemy jego lewe poddrzewo (z korzeniem w

),

przeszukujemy jego prawe poddrzewo (z korzeniem w

),

odwiedzamy wierzchołek

(korze ´n drzewa).

Algorytm ten mo˙zemy krótko przedstawi´c w schemacie:

lewe poddrzewo — prawe poddrzewo — korze ´n.

Przykład 1.9 Je˙zeli przeszukamy drzewo z rysunku 1.4 i wypiszemy po kolei etykiety od-
wiedzanych wierzchołków, to otrzymamy ci¸ag:

który jest postaci¸a postfixow¸a wyra˙zenia

()

.

1.5. Drzewa poszukiwa ´n binarnych

13

Istniej¸a jeszcze dwie inne pokrewne metody przeszukiwania drzew binarnych: inorder

i preorder:

Przeszukiwanie inorder. Aby przeszuka´c (pod)drzewo maj¸ace swój korze ´n w wierzchoł-
ku

:

przeszukujemy jego lewe poddrzewo (z korzeniem w

),

odwiedzamy wierzchołek

(korze ´n drzewa),

przeszukujemy jego prawe poddrzewo (z korzeniem w

).

Przeszukiwanie preorder. Aby przeszuka´c (pod)drzewo maj¸ace swój korze ´n w wierz-
chołku

:

odwiedzamy wierzchołek

(korze ´n drzewa),

przeszukujemy jego lewe poddrzewo (z korzeniem w

),

przeszukujemy jego prawe poddrzewo (z korzeniem w

).

Przykład 1.10 Je˙zeli przeszukamy drzewo z rysunku 1.4 metod¸a inorder, to etykiety utworz¸a
ci¸ag:

czyli wyra˙zenie w postaci infixowej, ale bez nawiasów. Przeszukanie tego samego drzewa
metod¸a preorder da ci¸ag etykiet:

)

Jest to tak zwana posta´c prefixowa wyra˙zenia. Znak operacji wyst¸epuje w niej przed ar-
gumentami. Podobne jak w postaci postfixowej, posta´c prefixowa da si¸e jednoznacznie
rozkłada´c i nie wymaga nawiasów.

1.5

Drzewa poszukiwa ´n binarnych

Drzewa s¸a podstawow¸a struktur¸a przy budowie du˙zych baz danych. Jed¸a z najprostszych
takich struktur s¸a drzewa poszukiwa ´n binarnych. Aby utworzy´c drzewo poszukiwa ´n bi-
narnych, zaczynamy od pustego drzewa, a nast¸epnie wstawiamy po kolei elementy, któ-
re maj¸a by´c przechowywane w drzewie. Wstawiane elementy powinny by ´c z jakiego´s
uporz¸adkowanego zbioru. Poni˙zej przedstawiamy algorytmu wstawiania elementów do
drzewa.

oznacza warto´s´c przechowywan¸a w wierzchołku

. Pami¸etajmy, ˙ze

oznacza poddrzewo o korzeniu w wierzchołku

.

Algorytm wstawiania elementu do drzewa poszukiwa ´n binarnych.

Aby wstawi´c element

do drzewa

:

je˙zeli drzewo

jest puste, to

(wstaw

do korzenia

),

14

Rozdział 1. Struktury danych

w przeciwnym razie porównaj

z zawarto´sci¸a korzenia

:

je˙zeli

, to wstaw

do poddrzewa

,

je˙zeli

, to wstaw

do poddrzewa

.

Przykład 1.11 Przypu´s´cmy, ˙ze mamy ci¸ag liczb naturalnych:

#

!

&

Utworzymy dla tego ci¸agu drzewo poszukiwa´n binarnych.

Rysunek 1.5: Drzewo poszukiwa ´n po wstawieniu elementów: 128, 76, 106, 402

Po wstawieniu pierwszych czterech elementów ci¸agu otrzymamy drzewo, które jest

przedstawione na rysunku 1.5, a po wstawieniu całego ci¸agu otrzymamy drzewo, które
jest przedstawione na rysunku 1.6. Je˙zeli teraz przeszukamy to drzewo metod¸a inorder, to
otrzymamy ten sam ci¸ag, ale uporz¸adkowany:

!

!

&

Je˙zeli mamy ju˙z drzewo poszukiwa ´n binarnych

, to dla ka˙zdego wierzchołka

zachodzi

dla ka˙zdego

,

,

dla ka˙zdego

,

.

Czyli wszystkie wierzchołki w lewym poddrzewie

zawieraj ˛

a warto´sci mniejsze

od warto´sci w

, a wszystkie wierzchołki w prawym poddrzewie

zawieraj ˛

a warto´sci

mniejsze od warto´sci w

.

Aby stwierdzi´c, czy jaki´s element

znajduje si¸e na tym drzewie. Post¸epujemy podob-

nie jak przy wstawianiu elementów. Zaczynamy od korzenia drzewa

i szukamy

elementu

za pomoc¸a poni˙zszego algorytmu.

1.6. Zadania

15

Rysunek 1.6: Drzewo dla ci¸agu: 128,76,106,402,100,46,354,1018,112,28, 396,35

Algorytm szukania elementu

na drzewie

.

Aby stwierdzi´c, czy element

znajduje si¸e na drzewie

:

je˙zeli

jest puste, to koniec, elementu

nie ma na drzewie,

je˙zeli

nie jest puste, to porównujemy

z warto´sci¸a

:

je˙zeli

(

, to koniec, znale´zli´smy element

na drzewie,

je˙zeli

, to szukamy

w lewym poddrzewie

,

je˙zeli

, to szukamy

w prawym poddrzewie

.

W drzewie poszukiwa ´n binarnych czas wyszukiwania lub wstawiania elementu jest

, gdzie

jest wysoko´sci¸a drzewa. W obu algorytmach tylko raz przechodzimy od

korzenia w dół do li´scia. Najlepiej by było, gdyby wysoko´s´c drzewa była rz¸edu logarytm
od liczby wierzchołków, ale nie w ka˙zdym drzewie poszukiwa ´n binarnych tak musi by´c.

1.6

Zadania

1. Ile wierzchołków mo˙ze mie´c drzewo binarne wysoko´sci

?

2. Przeszukaj metod¸a „w gł¸ab” („wszerz”) drzewo z rysunku 1.7.

3. Narysuj drzewo dla wyra˙zenie

. Przedstaw to wyra˙zenie w postaci

postfixowej i prefixowej.

16

Rozdział 1. Struktury danych

4. Narysuj drzewo dla wyra˙zenie

. Przedstaw to wyra˙zenie w postaci

infixowej i prefixowej. Oblicz warto´s´c tego wyra˙zenia. Przedstaw to wyra˙zenie w
postaci infixowej i prefixowej.

5. Wypisz w postaci infixowej, prefixowej i postfixowej wyra˙zenie przedstawione na

rysunku 7.

Rysunek 1.7: Drzewo wyra˙zenia

6. Narysuj drzewo poszukiwa ´n binarnych dla nast¸epuj¸acego ci¸agu liczb: 30, 43, 13, 8,

50, 40, 20, 19, 22.

7. Narysuj drzewo poszukiwa ´n binarnych dla nast¸epuj¸acego ci¸agu słów: słowik, wró-

bel, kos, jaskółka, kogut, dzi¸ecioł, gil, kukułka, szczygieł, sowa, kruk, czubatka.

[Fragment wiersza Ptasie radio Juliana Tuwima]

8. Udowodnij, ˙ze ka˙zde drzewo o

werzchołkach ma

kraw¸edzi.

9. Udowodnij, ˙ze ka˙zde pełne drzewo binarne o

li´sciach ma

wierzchołków

wewn¸etrznych.

Wskazówka. Drzewo binarne nazywa si¸e pełne, je˙zeli ka˙zdy jego wierzchołek ma
albo dwóch synów, albo nie ma synów wcale (jest li´sciem).