Tietorakenteet / syksy 2009 / Linna

Harjoitus 5, viikko 41

1. Piirrä binaaripuu (mikäli mahdollista), jonka solmut ovat esijärjestyksessä

ABCDEFGHIJ ja samanaikaisesti sisäjärjestyksessä

a) DCBFEGAHJI b) CBDFAHEGIJ.

2. Binääripuun solmut on annettu kahdessa järjestyksessä:

(1) INOULFPMA ja (2) UOLNIMPAF

Piirrä vastaava binääripuu (mikäli mahdollista), kun samanaikaisesti

a) järjestys (1) on esijärjestys ja järjestys (2) on sisäjärjestys.

b) järjestys (1) on sisäjärjestys ja järjestys (2) on jälkijärjestys.

c) järjestys (1) on esijärjestys ja järjestys (2) on jälkijärjestys.

3. Tarkastellaan etsintäpuuta, joka on aluksi tyhjä. Puuhun lisätään avaimet 5, 3,

9, 4, 6, 8, 1, 7 ja 2 (tässä järjestyksessä). Piirrä etsintäpuu avainten lisäämisen

jälkeen.

4. Sijoita luvut 1, 2, …,14 melkein täydelliseen 14-solmuiseen binääripuun

solmuihin siten, että binääripuusta tulee

a) etsintäpuu b) kasa

5. Binääripuu on toteutettu käyttäen normaalia linkitettyä esitystapaa. Laadi

algoritmi, joka käy läpi binääripuun solmut tasojärjestyksessä. Kullakin tasolla solmut käsitellään vasemmalta oikealle.