Viikko 5: Tiivistelmä

Viikon 5 aiheena on luentomateriaalin sivut 154–197.

Binääripuu

Binääripuu on puurakenne, jossa jokaiseen solmuun voi liittyy vasen ja oikea alipuu.

Tässä on esimerkki binääripuusta:

      7
     / \
    4   2
   /   / \
  6   7   5
         / \
        1   4

Binääripuu on binäärihakupuu, jos jokaisessa solmussa kaikki vasemman alipuun solmut ovat pienempiä ja kaikki oikean alipuun solmut ovat suurempia.

Tässä on esimerkki binäärihakupuusta:

      4
     / \
    2   6
   /   / \
  1   5   9
         / \
        7   10

Binäärihakupuun hyötynä on, että siitä voi etsiä solmua huipulta aloittaen valitsemalla aina sen alipuun, jossa solmun tulisi olla.

Java-toteutus

Javassa binääripuun voi toteuttaa seuraavasti:

public class Puu {
    int arvo;
    Puu vasen;
    Puu oikea;
 
    public Puu(int arvo, Puu vasen, Puu oikea) {
        this.arvo = arvo;
        this.vasen = vasen;
        this.oikea = oikea;
    }   
}

Kenttä arvo sisältää solmussa olevan luvun, ja kentät vasen ja oikea viittaavat vasempaan ja oikeaan alipuuhun.

Esimerkiksi binääripuun

      4
     / \
    1   7
       / \
      2   5

voi nyt määritellä näin:

Puu x = new Puu(4,
                new Puu(1, null, null),
                new Puu(7,
                        new Puu(2, null, null),
                        new Puu(5, null, null)));