581325-0 Tietorakenteet, loppukoe 8.6.2001/AW

1. Binääripuu esittää sellaista sukupuuta, jossa juurena on "minä". Juuren alipuut ovat "äiti" ja "isä", jne. Puun määrittely alkaa seuraavasti:

      public class Sukupuu {
   
        private class Sukulainen {
          private String nimi;
          private int syntymävuosi;
          private Sukulainen äiti, isä;
        }
   
        private Sukulainen juuri;
   
        public Sukupuu() {
          juuri = null;
        }
        ...
   

   Ohjelmoi luokkaan metodi (määrittele toiminta myös virhetilanteissa)
   • public void tulostaVanhinSynnyttäjä() tulostaa sen esivanhemman nimen, joka on synnyttänyt lapsensa vanhimpana. Jos henkilö ei ole yksikäsitteinen, kaikki vanhimmat tulostetaan.

2. Alunperin tyhjään AVL-puuhun viedään ensin avaimet 57, 34, 39, 50, 55 ja 53. Piirrä AVL-puu näiden lisäysten jälkeen. Sitten puuhun lisätään vielä avaimet 90, 80, 70 ja 60. Piirrä AVL-puu näiden lisäysten jälkeen.

   Lopuksi puu tulkitaankin vain tavalliseksi hakupuuksi ja siitä poistetaan remove-operaatiolla avain 57. Piirrä hakupuu tämän poiston jälkeen. (Kahdesta poisto-operaation vaihtoehtoisesta toteutuksesta tässä käytetään periaatetta: "vasemman alipuun maksimi".)

   Häviääkö hakupuun AVL-ominaisuus poiston seurauksena? Jos häviää, miksi se häviää?

   Huom: Vastauksessa on siis vain kolme kuvaa!

3. Binäärikeko on toteutettu taulukkona. Keon alkiot toteuttavat rajapintaluokan ComparableAndPrintable:

    
           public interface ComparableAndPrintable {
             public int compareTo(Object toinen);
             public String toString();
           }
      

   Täsmennä keon talletustapa ja ohjelmoi ilmentymämetodi, joka tulostaa keon alkiot esijärjestyksessä.