Viikko 6: TMC-tehtävät

Tehtävien deadline: ma-su yö 29.2. 1:59.

Viikon teemana on erilaisten metodien toteuttaminen binääripuille. Rekursiosta on erittäin paljon hyötyä!

Tehtävä 1

Sinulle on annettu binääripuu ja tehtäväsi on selvittää, mikä on pienin puussa esiintyvä arvo.

Toteutus

Toteuta seuraava metodi:

int minimi(Puu puu)

Parametri puu on binääripuu, jossa on 1..105 solmua. Solmuissa esiintyvät arvot ovat välillä 1..109.

Metodin tulee palauttaa pienin puussa esiintyvä arvo.

Esimerkki

Seuraava koodi testaa metodia:

Puu puu = new Puu(7,
                  new Puu(5,
                          new Puu(2, null, null),
                          null),
                  new Puu(6,
                          new Puu(3, null, null),
                          new Puu(1, null, null)));

System.out.println(minimi(puu));

Koodin tulostuksen tulisi olla seuraava:

1

Tehtävä 2

Sinulle on annettu kaksi binääripuuta, ja tehtäväsi on tutkia, ovatko puut samanlaiset eli onko puiden rakenne samanlainen ja onko niissä samat arvot kaikissa kohdissa.

Toteutus

Toteuta seuraava metodi:

boolean samanlaiset(Puu a, Puu b)

Parametrit a ja b ovat tutkittavat binääripuut. Molemmat sisältävät 1..105 solmua.

Metodin tulee palauttaa true, jos puut ovat samanlaiset, ja muuten false.

Esimerkki

Seuraava koodi testaa metodia:

Puu puu1 = new Puu(1,
                   new Puu(3,
                           new Puu(2, null, null),
                           new Puu(1, null, null)),
                   new Puu(3,
                           new Puu(3, null, null),
                           new Puu(2, null, null)));

Puu puu2 = new Puu(1,
                   new Puu(3,
                           new Puu(2, null, null),
                           new Puu(1, null, null)),
                   new Puu(3,
                           new Puu(3, null, null),
                           new Puu(2, null, null)));
        
System.out.println(samanlaiset(puu1, puu2));

Koodin tulostuksen tulisi olla seuraava:

true

Tehtävä 3

Sinulle on annettu binääripuu ja tehtäväsi on tutkia, toteuttaako puu ns. AVL-ehdon, eli onko jokaisen puun solmun vasemman ja oikean alipuun korkeuksien ero korkeintaan 1. Tämä ehto on tärkeä AVL-puun, joka on eräs tasapainoitettu binäärihakupuu, toteutuksessa. Tasapainotettuihin binäärihakupuihin päästään seuraavalla viikolla.

Toteutus

Toteuta seuraava metodi:

boolean onkoAVL(Puu puu)

Parametri puu on binääripuu, jossa on 1..105 solmua.

Metodin tulee palauttaa true, jos puu toteuttaa AVL-ehdon, ja muuten false.

Esimerkkejä

Seuraavat puut täyttävät AVL-ehdon:

    o              o             o
   / \            / \           / \
  o   o          o   o         o   o
 /\   /\        /   / \       / \  |\
o  o o  o      o   o   o     o   o o o
       / \          \       / \ / \
      o   o          o      o o o o

Seuraavat puut eivät täytä AVL-ehtoa:

    o               o            o
   / \             / \          / \
  o   o           o   o        o   o
 /\   /\         /   / \      / \   \
o  o o  o       o   o   o    o   o   o
       / \     /     \      / \ / \ / \
      o   o   o       o     o o o o o o
       \
        o

Yllä olevat esimerkkipuut ovat esimerkkisyötteinä.

Tehtävä 4

Tiedetään, että puussa jokaisen solmuparin välillä on yksikäsitteinen polku, joka kulkee enintään kerran minkään solun läpi. Tehtävänäsi on etsiä pisin mahdollinen tällaisen polun pituus puusta, joka annetaan syötteenä.

Toteutus

Toteuta seuraava metodi:

int pisinPolku(Puu puu)

Parametri puu on binääripuu, jossa on 1..105 solmua.

Metodin tulee palauttaa pisimmän polun pituus jonkin kahden solmun välillä.

Esimerkki

Seuraava koodi testaa metodia:

Puu puu = new Puu(1,
                  new Puu(3,
                          new Puu(2, null, null),
                          null),
                  new Puu(3,
                          new Puu(3, null, null),
                          new Puu(2, null, null)));

System.out.println(pisinPolku(puu));

Koodin tulostuksen tulisi olla seuraava:

4

Tehtävä 5

Sinulle on annettu binääripuun esi- ja sisäjärjestys. Tehtäväsi on muodostaa niiden perusteella jälkijärjestys.

Esijärjestys käy ensin puun juuressa, sitten vasemmassa alipuussa ja lopuksi oikeassa alipuussa. Sisäjärjestys käy ensin vasemmassa alipuussa, sitten puun juuressa ja lopuksi oikeassa alipuussa. Jälkijärjestys käy ensin vasemmassa alipuussa, sitten oikeassa alipuussa ja lopuksi puun juuressa.

Esimerkiksi binääripuuta

     B
    / \
   D   A
      / \
     C   E

vastaa esijärjestys BDACE, sisäjärjestys DBCAE ja jälkijärjestys DCEAB.

Toteutus

Toteuta seuraava metodi:

String jalki(String esi, String sisa)

Parametrit esi ja sisa kuvaavat binääripuun esi- ja sisäjärjestyksen. Binääripuussa on 1..26 solmua ja niiden tunnukset ovat suuret kirjaimet A:sta lähtien.

Metodin tulee palauttaa binääripuun jälkijärjestys vastaavassa muodossa.

Esimerkit