Untitled

package no.oslomet.cs.algdat;

import java.util.*;

public class SøkeBinærTre<T>  implements Beholder<T> {

    public static void main(String[] args) {
        SøkeBinærTre<Integer> tre = new SøkeBinærTre<>(Comparator.naturalOrder());
        int[] a = {6, 3, 9, 1, 5, 7, 10, 2, 4, 8, 11, 6, 8};
        for (int verdi : a) tre.leggInn(verdi);
        for (Integer verdi : tre) System.out.println(verdi);
    }

    // En del kode er ferdig implementert, hopp til linje 91 for Oppgave 1

    private static final class Node<T> { // En indre nodeklasse
        private T verdi; // Nodens verdi
        private Node<T> venstre, høyre, forelder; // barn og forelder

        // Konstruktører
        private Node(T verdi, Node<T> v, Node<T> h, Node<T> f) {
            this.verdi = verdi;
            venstre = v; høyre = h; forelder = f;
        }
        private Node(T verdi, Node<T> f) {
            this(verdi, null, null, f);
        }

        @Override
        public String toString() {return verdi.toString();}
    } // class Node

    private final class SBTIterator implements Iterator<T> {
        Node<T> neste;
        public SBTIterator() {
            neste = førstePostorden(rot);
        }

        public boolean hasNext() {
            return (neste != null);
        }

        public T next() {
            Node<T> denne = neste;
            neste = nestePostorden(denne);
            return denne.verdi;
        }
    }

    public Iterator<T> iterator() {
        return new SBTIterator();
    }

    private Node<T> rot;
    private int antall;

    private final Comparator<? super T> comp;

    public SøkeBinærTre(Comparator<? super T> c) {
        rot = null; antall = 0;
        comp = c;
    }

    public boolean inneholder(T verdi) {
        if (verdi == null) return false;

        Node<T> p = rot;
        while (p != null) {
            int cmp = comp.compare(verdi, p.verdi);
            if (cmp < 0) p = p.venstre;
            else if (cmp > 0) p = p.høyre;
            else return true;
        }
        return false;
    }

    public int antall() { return antall; }

    public String toStringPostOrder() {
        if (tom()) return "[]";

        StringJoiner s = new StringJoiner(", ", "[", "]");

        Node<T> p = førstePostorden(rot);
        while (p != null) {
            s.add(p.verdi.toString());
            p = nestePostorden(p);
        }

        return s.toString();
    }

    public boolean tom() { return antall == 0; }

    // Oppgave 1
    public boolean leggInn(T verdi) {
        // Sjekker om vi prøver legge inn null
        Objects.requireNonNull(verdi, "Kan ikke sende inn null i treet.");

        // Om treet er tomt, legg inn ny node som rot
        if (tom()) {
            rot = new Node<>(verdi, null);
            antall++;
            return true;
        }

        Node<T> n = rot;
        int cmp;
        while (true) { // Returnerer inni, så burde komme oss ut av løkka
            cmp = comp.compare(verdi, n.verdi);
            if (cmp < 0) {
                // Skal vi til venstre?
                if (n.venstre == null) {
                    // Om venstreplass er ledig, legg inn her.
                    n.venstre = new Node<>(verdi, n);
                    antall++;
                    return true;
                } else {
                    n = n.venstre;
                }
            } else {
                // Vi skal til høyre
                if (n.høyre == null) {
                    // Om høyreplass er ledig, legg inn her.
                    n.høyre = new Node<>(verdi, n);
                    antall++;
                    return true;
                } else {
                    n = n.høyre;
                }
            }
        }
    }


    // Oppgave 2

    // Trenger ofte finne en spesifikk node, tar det like gjerne ut i egen logikk.
    // Tar inn en verdi (å finne) og en node ("rotnoden", lar oss lette i subtrær)
    // Gir ut første node i subtreet med n som rot som har gitt verdi. Gir null om vi ikke finner verdien.
    private Node<T> finnNode(T verdi, Node<T> n) {
        if (verdi == null) return null;

        while (n != null) {
            int cmp = comp.compare(verdi, n.verdi);
            if (cmp < 0)
                n = n.venstre;
            else if (cmp > 0)
                n = n.høyre;
            else
                break;
        }
        return n;
    }

    public int antall(T verdi){
        // Om vi har tomt tre vil alle verdier gi 0. Om vi spør om null, vil svaret alltid være 0.
        if (tom() || verdi == null) return 0;

        // Har rota verdien vi leter etter? Om ja, begynn telling på 1.
        int ant = 0;

        Node<T> n = finnNode(verdi, rot); // Første node med gitt verdi.
        while (n != null) {
            ant++; // Dette teller den *forrige* funnede noden
            n = finnNode(verdi, n.høyre); // Finn neste node med verdien, i det høyre subtreet.
            /*
            Dette er litt tregere enn det hadde trengt. Neste node har samme verdi som forrige, så vi
            vet at vi primært skal mot venstre, og maks 1 steg mot høyre av gangen. Men logikken er lettere
            å følge om vi bruker finnNode her, i stedet for å gå gjennom stegene selv.
            */
        }

        return ant;
    }

    // Oppgave 3
    private Node<T> førstePostorden(Node<T> p) {
        if (p.venstre != null) {
            // Om du har et venstrebarn, er du ikke først i postorden, og riktig svar er første i postorden
            // i ditt venstre subtre
            return førstePostorden(p.venstre);
        } else if (p.høyre != null) {
            // Om du ikke har et venstrebarn, men har et høyrebarn, er du ikke først i postorden, og riktig svar
            // er første i postorden i ditt høyre subtre
            return førstePostorden(p.høyre);
        } else {
            // Om du verken har venstre eller høyrebarn, så er rota først i postorden i dette subtreet
            return p;
        }
    }

    private Node<T> nestePostorden(Node<T> p) {
        // Om du er rota, er det ingen etter deg
        if (p == rot) return null;

        // Om du er til din foreldres høyre, eller din forelder ikke har flere barn, er din forelder neste i postorden
        if (p.forelder.høyre == p || p.forelder.høyre == null)
            return p.forelder;

        // Om du er til din foreldres venstre, og din forelder har flere barn, finn første i postorden til din foreldres høyre.
        return førstePostorden(p.forelder.høyre);
    }

    // Oppgave 4
    public void postOrden(Oppgave<? super T> oppgave) {
        /*
        Både førstePostorden og nestePostorden er i min implementasjon rekursive, poenget med denne oppgaven
        var bare at *denne* funksjonen ikke kaller på seg selv. Går bra at funksjonene førstePostorden og
        nestePostorden er rekursive.

        Denne metoden er jo veldig lik toStringPostorder, så trikset er jo å bare se hvordan den er skrevet.
         */
        if (tom()) return;

        Node<T> n = førstePostorden(rot);
        while (n != null) {
            oppgave.utførOppgave(n.verdi);
            n = nestePostorden(n);
        }
    }

    public void postOrdenRekursiv(Oppgave<? super T> oppgave) {
        postOrdenRekursiv(rot, oppgave); // Ferdig implementert
    }

    private void postOrdenRekursiv(Node<T> p, Oppgave<? super T> oppgave) {
        if (p == null) return;
        postOrdenRekursiv(p.venstre, oppgave);
        postOrdenRekursiv(p.høyre, oppgave);
        oppgave.utførOppgave(p.verdi); // Blir postorden siden utførOppgave er sist
    }

    // Oppgave 5
    public boolean fjern(T verdi) {
        // Vi finner noden som skal fjernes, og fjerner denne. Om vi ikke finner noden, er ikke verdien der.
        Node<T> n = finnNode(verdi, rot);
        if (n != null) {
            fjern(n);
            antall--;
            // Antall må trekkes fra her, og ikke i fjern(Node), siden fjern(Node) kalles rekursivt og ville da trukket fra flere ganger
            return true;
        }
        return false;
    }

    private void fjern(Node<T> n) {
        // Gitt en (ikke-null) node, fjerner denne
        Node<T> f = n.forelder;

        /*
        Option 1: Noden har ingen barn. Vi fjerner denne ved å oppdatere forelderens peker til null.
         */
        if (n.venstre == null && n.høyre == null) {
            if (f == null) {
                // Vi er rota, setter rot til null.
                rot = null;
            } else if (f.venstre == n) {
                // Vi er venstrebarnet til forelder
                f.venstre = null;
            }
            else {
                // Vi er høyrebarnet til forelder
                f.høyre = null;
            }
            n.forelder = null; // Null ut foreldrepeker
        }
        /*
        Option 2: Noden har to barn. Jeg sjekker dette her, for da *vet* jeg
        at noden må ha nøyaktig ett barn etter dette. Ellers måtte jeg sjekket
        noe a la (n.venstre != null && n.høyre == null).

        Vi finner neste node i inorden, flytter dens verdi opp hit, og sletter den
        noden i stedet.
         */
        else if (n.venstre != null && n.høyre != null) {
            Node<T> r = n.høyre;
            while (r.venstre != null) r = r.venstre;
            // Bytt verdi med neste i inorden
            n.verdi = r.verdi;
            // Fjern denne noden. Den vil ha maks ett høyrebarn.
            fjern(r);
        }
        /*
        Option 3: Noden har kun et venstrebarn.
        Vi setter forelders peker til å peke på dette venstrebarnet.
         */
        else if (n.venstre != null) {
            if (f == null) {
                // Vi er rota. Må oppdatere rotnoden
                rot = n.venstre;
            } else if (f.venstre == n) {
                f.venstre = n.venstre;
            } else {
                f.høyre = n.venstre;
            }
            n.venstre.forelder = f;
            n.forelder = null; n.venstre = null; // Null ut pekere
        }
        /*
        Option 4: Noden har kun et høyrebarn.
        Samme som option 3, essensielt.
         */
        else {
            // Noden har nøyaktig ett høyrebarn
            if (f == null) {
                // Vi er rota. Må oppdatere rotnoden
                rot = n.høyre;
            } else if (f.venstre == n) {
                f.venstre = n.høyre;
            } else {
                f.høyre = n.høyre;
            }
            n.høyre.forelder = f;
            n.forelder = null; n.høyre = null; // Null ut pekere
        }
    }

    public int fjernAlle(T verdi) {
        Deque<Node<T>> stabel = new ArrayDeque<>();
        // Bruker kø så vi sletter nederste element først
        // Ellers måtte vi flyttet hver lik verdi opp til toppen hver gang, helt til siste

        Node<T> n = finnNode(verdi, rot);
        while (n != null) {
            stabel.addFirst(n); // Legg til funnet node på stabel
            n = finnNode(verdi, n.høyre);
        }
        int fjernet = stabel.size();
        while (!stabel.isEmpty())
            fjern(stabel.removeFirst());
        antall = antall - fjernet;
        return fjernet;
    }
    public void nullstill() {
        if (tom()) return;

        // Gå gjennom treet i postorden, slett noder når du kommer til dem
        // Hver node som slettes vil da ha 0 barn. (Dette kun sant om postorden)
        Node<T> n = førstePostorden(rot);
        Node<T> fj;
        while (n != null) {
            fj = n; // Må ha midlertidig node, gå videre i postorden før vi sletter noden.
            n = nestePostorden(n);
            fjern(fj);
            antall--;
            // Kunne bare satt antall = 0 til slutt.
            // Ved å trekke fra hver gang er det derimot lettere å se om noe har gått galt, da får vi feil antall.
        }
    }
}