Viikko 6: TMC-tehtävät

TMC viikko 6

Tehtävien deadline: ma 23.2. klo 01:59

Viikon teemana on erilasiten metodien toteuttaminen binääripuille. Rekursiosta on erittäin paljon hyötyä! Mahdollisesti hyödyllienen esimerkki.


Tehtävä 1

Sinulle on annettu binääripuu ja tehtäväsi on laskea, montako kertaa arvo x esiintyy puussa.

Toteutus

Toteuta seuraava metodi:

int laskeArvot(Puu puu, int x)

Parametri puu on binääripuu, jossa on 1..105 solmua. Parametri x on etsittävä arvo.

Metodin tulee palauttaa, montako kertaa x esiintyy puussa.

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(laskeArvot(puu, 1));
System.out.println(laskeArvot(puu, 2));
System.out.println(laskeArvot(puu, 3));

Koodin tulostuksen tulisi olla seuraava:

1
2
3

Tehtävä 2

Sinulle on annettu binääripuu ja tehtäväsi on tutkia, onko puu täydellinen, eli onko jokainen polku juuresta alaspäin yhtä pitkä.

Toteutus

Toteuta seuraava metodi:

boolean taydellinen(Puu puu)

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

Metodin tulee palauttaa true, jos puu on täydellinen, ja muuten false.

Esimerkki

Seuraava koodi testaa metodia:

Puu puu = 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(taydellinen(puu));

Koodin tulostuksen tulisi olla seuraava:

true

Tehtävä 3

Sinulle on annettu kaksi binääripuuta, ja tehtäväsi on tutkia, ovatko puun 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ä 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

#metodin kutsuhaluttu palautusarvo
1jalki("BDACE", "DBCAE")"DCEAB"
2jalki("ABCD", "DCBA")"DCBA"
3jalki("ABCD", "ACDB")"DCBA"
4jalki("GEABFCD", "AEBGCFD")"ABECDFG"