//obs: byt manm från Trad.java till Träd.java för att kunna kompilera!

public class  Träd<E extends Comparable<E>>{
    
    private Nod root = null; 
    
    ///////////////////////////
    ///K O N S T R U K T O R E R
    public Träd(){
    }

    
    ///////////////////
    ///M U T A T O R E R
    public boolean sättIn(E nyttElement){
	Nod nyNod = new Nod(nyttElement);
	if(root==null){
	    root = nyNod; 
	    return true;
	}
	else return sättIn(root, nyNod);
    }
    private boolean sättIn(Nod förälder, Nod sättInMig){
	if(förälder==null){
	    return false;
	} 
	//Vänster
	if(sättInMig.compareTo(förälder)<0){ 
	    if(förälder.vänster==null){
		förälder.vänster = sättInMig;
		sättInMig.förälder = förälder; 
		return true; 
	    }
	    else
		return sättIn(förälder.vänster, sättInMig); 
	}
	//sätt in till höger
	else if(sättInMig.compareTo(förälder)>0){ 
	    if(förälder.höger==null){
		förälder.höger = sättInMig;
		sättInMig.förälder = förälder; 
		return true; 
	    }
	    else
		return sättIn(förälder.höger, sättInMig); 
	}
	else{
	    return false; //Sätt inte in
	}
    }

    
    /////////////////////
    ///S E L E K T O R E R
    
    public boolean ärTom(){
	return root == null; 
    }
    
    
    public E getMinstaBarn(){
	return (root==null)?null:getMinstaBarn(root).element;
    }
    public E getStörstaBarn(){
	return (root==null)?null:getStörstaBarn(root).element;
    }
    private Nod getMinstaBarn(Nod n){
	if (n==null) return null; 
	while(n.vänster!=null)
	    n = n.vänster; 
	return n; 
    }
    private Nod getStörstaBarn(Nod n){
	if (n==null) return null; 
	while(n.höger!=null)
	    n = n.höger; 
	return n; 
    }
    
    
    /////////////////////////
    ///H J Ä L P K L A S S E R
    
    private class Nod{
	//Containerklassen är en inre klass och delar typ-parametern E med den yttre klassen
	E element = null; 
	Nod vänster = null; 
	Nod höger = null; 
	Nod förälder = null; 
	Nod(){
	}
	Nod(Nod n){
	    this.element = n.element; 
	    this.vänster = n.vänster; 
	    this.höger   = n.höger; 
	    this.förälder= n.förälder; 
	}
	Nod(E element){
	    this.element = element; 
	}
	public boolean harBarn(){
	    return (vänster!=null || höger!=null);
	}
	public String toString(){
	    return "e:"+element.toString(); 
	}
	public void ersättInfo(Nod n){
	    this.element = n.element; 
	}
	public int compareTo(Nod nod){
	    return this.element.compareTo(nod.element);
	}
    }
    
    
    
}