Drzewa binarne.

Scenariusz lekcji informatyki

Leon Plebanek

Temat: Drzewa binarne

Klasa: 3 Gimnazjum (kółko informatyczne)

Czas trwania: 90 minut

Cele: zapamiętanie

- definicji drzewa binarnego stopnia n
- zależności rekurencyjnej między drzewami binarnymi kolejnych stopni
- zapisanie procedury rysującej drzewo binarne w języku logo
- zdefiniowanie procedury wyświetlającej pokaz drzew binarnych

Potrzebne wiadomości: procedury pierwotne języka Logo dot. grafiki żółwia, procedury z
parametrami, procedura rekurencyjna, rekurencja końcowa i niekońcowa

Metody i formy pracy: wykład, pogadanka, praca równym frontem, praca w grupach, praca
samodzielna

Środki dydaktyczne: komputery z oprogramowaniem Logomocja - Imagine w środowisku Windows,
tablica

Przebieg lekcji:
- przypomnienie wiadomości o procedurach rekurencyjnych w Logo
- przedstawienie figury drzewo binarne z parametrami :stopień :bok

drzewo :stopień :bok

- zdefiniowanie drzewa stopnia 0 o boku :bok

drzewo 0 :bok NP :bok WS :bok

- zdefiniowanie drzewa stopnia 1 o boku :bok

drzewo 1 :bok NP :bok
LW 45
NP :bok / 2 WS :bok / 2

Strona 1 z 4

PW 90
NP :bok / 2 WS :bok / 2
LW 45
WS :bok

- zastąpienie w powyższej definicji linijki 3 i 5 wywołaniami rekurencyjnymi drzewo 0 :bok / 2

drzewo 1 :bok NP : bok
LW 45
drzewo 0 :bok / 2
PW 90
drzewo 0 :bok / 2
LW 45
WS :bok

- zdefiniowanie drzewa stopnia 2 o boku :bok

drzewo 2 :bok NP :bok
LW 45
NP :bok / 2
LW 45
NP :bok / 4 WS :bok / 4
PW 90
NP :bok / 4 WS :bok / 4
LW 45
WS :bok / 2
PW 90
NP :bok / 2
LW 45
NP :bok / 4 WS :bok / 4
PW 90
NP :bok / 4 WS :bok / 4
LW 45
WS :bok / 2
LW 45
WS :bok

- zastąpienie linijek 5, 7, 13, 15 wywołaniami rekurencyjnymi drzewo 0 :bok / 4

drzewo 2 :bok NP :bok
LW 45
NP :bok / 2
LW 45
drzewo 0 :bok / 4
PW 90
drzewo 0 :bok / 4
LW 45
WS :bok / 2
PW 90
NP :bok / 2
LW 45
drzewo 0 :bok / 4
PW 90
drzewo 0 :bok / 4
LW 45
WS :bok / 2
LW 45
WS :bok

Strona 2 z 4

- zastąpienie linijek 3, 9, 11, 17 wywołaniami rekurencyjnymi drzewo 1 :bok / 2

drzewo 2 :bok NP :bok
LW 45
drzewo 1 :bok / 2
PW 90
drzewo 1 :bok / 2
LW 45
WS :bok

- odkrycie zależności rekurencyjnej dla drzewa stopnia :n

drzewo :n :bok NP :bok
LW 45
drzewo :n - 1 :bok / 2
PW 90
drzewo :n - 1 :bok / 2
LW 45
WS :bok

- zdefiniowanie procedury drzewo :n :bok w języku ...