Tehtävä 3, Markus Ekholm
========================

Metodit tarkastettiin erillisinä:
 - syvyydestä ja korkeudesta sai max. 3 pistettä
 - lehtien tulostamisesta max. 2 p.

Pisteiden saamisen kannalta olennaista oli, että 
a) oli ymmärretty, mitä pitää tehdä (esim. solmun korkeuden ja syvyyden
ero,
   mikä on lehti jne.)
b) metodit toimivat suht. oikein

Pikkuvirheistä (esim. korkeus-metodi palauttaa todellista korkeutta
yhden
isomman tai pienemmän arvon) tiputettiin kolmannespiste tai puoli
pistettä
virheen laadusta riippuen.

Tyypillisiä isompia virheitä olivat:
 - unohdetaan rekursiossa ottaa paluuarvo talteen
 - yritetään palauttaa jotain void-metodista
 - null-arvojen testaamisen unohtaminen
 - yritetään käydä puuta läpi tyyliin (while (p!= null) p=p.vasen)
 - syvyys-metodissa lasketaan korkeutta
 - tulostaLehdet - metodissa tulostetaan koko puu
 - pidettiin puuta hakupuuna (syvyys-metodi)

/////////////////////////////////////////////////////////////////////////////

//
// Tietorakenteet, kevät 2000
// 1. välikoe 3.3.2000 
//
// 3.tehtävä
// Ratkaisuehdotus, Markus Ekholm 3.4.2000
//
/////////////////////////////////////////////////////////////////////////////


public class Puu {

    private class Solmu {
	Object tieto;
	Solmu vasen, oikea;
    }
    
    private Solmu juuri;

    public Puu() {
	juuri = null;
    }

    // ...

    public int korkeus() { // palauttaa arvonaan binääripuun korkeuden 
    
	if (juuri==null) return -1; // tyhjästä puusta palautetaan -1
	else return korkeus(juuri);
    }

    private int korkeus (Solmu juuri) {
	
	if (juuri==null) return -1;  
	
	int v= korkeus(juuri.vasen);  // lasketaan vasemman alipuun korkeus
	int o= korkeus(juuri.oikea);  // .. ja sama oikealle

	if (v>o) return v+1;          // korkeus=suurempi alipuiden korkeuk-
	else return o+1;              // sista +1
    }

    private int syvyys(Solmu s) { // palauttaa arvonaan annetun solmun syvyyden
	
	if (juuri==null) return -1;   // ei voi löytyä täältä => -1
	else return syvyys(juuri, s, 0);
    }

    private int syvyys (Solmu juuri, Solmu etsi, int syvyys) {
	
	if (juuri==null) 
	    return -1;                 // ei voi olla täällä => -1
	else if (juuri.equals(etsi)) 
	    return syvyys;             // löytyi, palautetaan syvyys
	else {
	    int v= syvyys(juuri.vasen, etsi, syvyys+1); // etsitään molemmista
	    int o= syvyys(juuri.oikea, etsi, syvyys+1); // alipuista

	    if (v==-1 && o==-1) return -1;  // jos ei löytynyt kummastakaan
	    else if (v>o) return v;         // löytyi vasemmalta
	    else return o;                  // löytyi oikealta
	}
    }

    public void tulostaLehdet() { //tulostaa puun lehdet vasemmalta oikealle 
	if (juuri==null)                   
	    System.out.println("Tyhjä puu");  // ei lehtiä
 	else tulostaLehdet(juuri);            
    }

    private void tulostaLehdet(Solmu juuri) {
	if (juuri==null) return;             // tyhjä solmu, palataan
	else if (juuri.vasen==null && juuri.oikea==null) // ollaan lehdessä
	    System.out.print(" | "+juuri.tieto); // tulostetaan tieto
	else {
	    tulostaLehdet(juuri.vasen);  // muuten rekurs. kutsu, ensin
	    tulostaLehdet(juuri.oikea);  // vasen, sitten oikea
	}
    }
}