Vezbe

package main;

import labis.cvorovi.CvorStabla;
import labis.exception.LabisException;
import labis.stabla.ABinarnoStablo;

public class BinanoStablo extends ABinarnoStablo{

    public boolean daLiPostojiIsti(CvorStabla k, CvorStabla neki){
        if(k==null || neki==null){
            return false;
        }

        if(k.podatak == neki.podatak && k != neki){
            return true;
        }else{
            return daLiPostojiIsti(k.levo, neki) || daLiPostojiIsti(k.desno, neki);
        }
    }

    public CvorStabla vratiMaksimalanPolulist(CvorStabla k) throws LabisException{
        if(k == null){
            return k;
        }

        CvorStabla maxPolulist = null;
        CvorStabla maxLevi = vratiMaksimalanPolulist(k.levo);
        CvorStabla maxDesni = vratiMaksimalanPolulist(k.desno);

        if((k.levo == null && k.desno!=null) || (k.levo !=null && k.desno==null)){
            maxPolulist = k;
        }
        if(maxPolulist == null || (maxLevi !=null && maxLevi.podatak > maxPolulist.podatak)){
            maxPolulist = maxLevi;
        }

        if(maxPolulist == null || (maxDesni !=null && maxDesni.podatak > maxPolulist.podatak)){
            maxPolulist = maxDesni;
        }

        return maxPolulist;
    }

    public void ubaci(CvorStabla k,int podatak) throws LabisException{
        if(k == null){
            koren = new CvorStabla(podatak,null,null);
            return;
        }
        if(k.podatak > podatak){
            if(k.levo==null){
                CvorStabla novi = new CvorStabla(podatak,null,null);
                k.levo = novi;
                return;
            }else{
                ubaci(k.levo,podatak);
            }
        }else{
            if(k.desno == null){
                CvorStabla novi = new CvorStabla(podatak,null,null);
                k.desno = novi;
                return;
            }else{
                ubaci(k.desno,podatak);
            }
        }
    }

    public void izbaci(int podatak) throws LabisException{
        CvorStabla cvor = pronadji(koren,podatak);//VRACA POKAZIVAC NA CVOR AKO GA NADJEMO

        if(cvor == null){
            return;
        }

        if(cvor.levo !=null && cvor.desno !=null){//UNUTRASNJI CVOR!!!
            CvorStabla maxL = maxCvor(cvor.levo);//VRACA POKAZIVAC NA NAJVECI POKAZIVAC U LEVOM STABLU
            cvor.podatak = maxL.podatak;
            izbaciListIliPoluList(maxL);
        }

        izbaciListIliPoluList(cvor);
    }

    private void izbaciListIliPoluList(CvorStabla cvor) {
        CvorStabla roditelj = nadjiRoditelja(koren,cvor);
        CvorStabla dete = null;
        dete = cvor.levo !=null ? cvor.levo:cvor.desno; // ako vazi uslov vrati prvi, ako nije vrati ovaj drugi!

        if(roditelj == null){
            koren = dete;
        }else{
            if(roditelj.levo == cvor){
                roditelj.levo = dete;
            }else{
                roditelj.desno = dete;
            }
        }
    }

    private CvorStabla nadjiRoditelja(CvorStabla tekuci, CvorStabla cvor) {
        if(tekuci == null || tekuci == cvor){
            return null;
        }
        if(cvor.podatak < tekuci.podatak){
            if(tekuci.levo != null && tekuci.levo == cvor){
                return tekuci;//ZNACI OVO JE ONDA RODITELJ!!!
            }
            return nadjiRoditelja(tekuci.levo, cvor);
        }else{
            if(tekuci.desno != null && tekuci.desno == cvor){
                return tekuci;
            }
            return nadjiRoditelja(tekuci.desno, cvor);
        }

    }

    private CvorStabla maxCvor(CvorStabla tekuci) {
        while(tekuci !=null && tekuci.desno !=null){
            tekuci = tekuci.desno;
        }
        return tekuci;
    }

    private CvorStabla pronadji(CvorStabla tekuci, int podatak) {
        while(tekuci!=null){
            if(tekuci.podatak == podatak){
                return tekuci;
            }
            if(tekuci.podatak > podatak){
                tekuci = tekuci.levo;
            }else{
                tekuci = tekuci.desno;
            }
        }
        return tekuci;//BICE NULL
    }

    public static void main(String[] args) {
        System.out.println("CIGLANA PETAK VECE POSLE RACUNOVODSTVA!");
    }

}