Zur Haupt­na­vi­ga­ti­on sprin­gen [Alt]+[0] Zum Sei­ten­in­halt sprin­gen [Alt]+[1]

Dop­pel­stun­de 8: Baum­tra­ver­sie­run­gen [nur LF]

Als nächs­tes wer­den die un­ter­schied­li­chen Tra­ver­sie­rungs­me­tho­den für Bi­när­bäu­me be­han­delt. Die Prä­sen­ta­ti­on 10_ba­e­u­me_2.odp zeigt im ers­ten Teil zu­nächst, wie Al­go­rith­men grund­sätz­lich struk­tu­riert sind, die alle Kno­ten eines Bi­när­baums durch­lau­fen. Sinn­vol­ler­wei­se wer­den diese re­kur­siv for­mu­liert, weil sich diese Lö­sung am ein­fachs­ten for­mu­lie­ren las­sen. Die Schü­le­rin­nen und Schü­ler sol­len er­ken­nen, dass die prin­zi­pi­el­le Struk­tur beim Zäh­len der Kno­ten oder Auf­sum­mie­ren der Kno­ten­wer­te ei­gent­lich gleich ist.

Im An­schluss daran wer­den im dem Auf­ga­ben­blatt 10_baumal­go­rith­men.odt drei ein­fa­che Baumal­go­rith­men im­ple­men­tiert, um die An­zahl und die Tiefe eines Baums zu be­stim­men und einen Wert im Baum su­chen zu las­sen. Wenn Hig­her-Order-Funk­tio­nen aus­führ­lich be­han­delt wur­den, kann man hier auch ver­su­chen, eine Im­ple­men­ta­ti­on von An­zahl- und Tie­fen­be­stim­mung mit die­ser Tech­nik um­zu­set­zen.

Da­nach wird die Prä­sen­ta­ti­on fort­ge­setzt. Dort wer­den die Un­ter­schie­de zwi­schen Pre­or­der-, Pos­t­or­der- und In­or­der-Tra­ver­sie­rung er­klärt und je­weils An­wen­dungs­bei­spie­le be­schrie­ben. Zur Fes­ti­gung die­ser Prin­zi­pi­en wird da­nach das Auf­ga­ben­blatt 10_­tra­ver­sie­run­gen.odt be­ar­bei­tet. Darin wer­den die Tra­ver­sie­rungs­stra­te­gi­en zu­nächst auf Pa­pier durch­ge­führt und für An­wen­dungs­fäl­le be­stimmt, wel­che Tra­ver­sie­rung je­weils er­for­der­lich ist. Hier ist aus­drück­lich keine Im­ple­men­tie­rung son­dern eine Be­schrei­bung in Pseu­do­code ver­langt.

Als Dif­fe­ren­zie­rung kann al­ler­dings in Auf­ga­be 4 eine Im­ple­men­ta­ti­on durch­ge­führt wer­den. Das Pro­gramm­ge­rüst, das be­reit­ge­stellt wird, ent­hält zum einen eine GUI und zum an­de­ren be­reits die Funk­tio­na­li­tät, um aus einem ein­ge­ge­be­nen Term eine Baum­dar­stel­lung zu er­zeu­gen (und den Term dabei auch auf syn­tak­ti­sche Kor­rekt­heit zu über­prü­fen). Hier soll ei­ner­seits der Zahl­wert eines Re­chen­baums be­stimmt wer­den (eine Pos­t­or­der-Tra­ver­sie­rung) und an­de­rer­seits eine li­nea­re String-Dar­stel­lung aus­ge­ge­ben wer­den (eine In­or­der-Tra­ver­sie­rung). Bei letz­te­rer Auf­ga­be kann man aber nicht ein­fach den oben ein­ge­ge­be­nen String wie­der­ver­wen­den: Sinn der Auf­ga­be ist auch, dass un­nö­ti­ge Klam­mern ent­fernt wer­den. Hier­bei ist den Schü­le­rin­nen und Schü­lern selbst über­las­sen, einen Al­go­rith­mus bzw. eine Ent­schei­dungs­re­gel zu ent­wi­ckeln, wann Klam­mern zu set­zen sind und wann nicht.

 

Un­ter­richts­ver­lauf: Her­un­ter­la­den [odt][187 KB]

 

Wei­ter zu DS 9: Re­kur­si­ve Al­go­rith­men