///////////////////////////////////////////////////////////////////
// Uke 40
//
///////////////////////////////////////////////////////////////////
// Oppgave 1 og 2
//

class BinNode {
  int verdi;
  int andredata;
  BinNode venstre;
  BinNode hoyre;
  BinNode opp;

  BinNode(int verdi, int a, BinNode opp) {
    this.opp = opp;
    this.verdi = verdi;
    andredata = a;
  }

  BinNode nesteInfiks() {
    if (hoyre != null) {
      // venstre er allerede behandlet. Skal finne f?rste i h?yre subtre.
      BinNode neste = hoyre;
      while (neste.venstre != null) neste = neste.venstre;
      return neste;
    } else {
    // Har skrevet ut hele dette subtreet.
    // M? lete oppover til vi finner en forgjenger som ikke er behandlet,
    // det vil si at denne ligger i venstre subtre.
      BinNode neste = opp, fnode = this;
      while (neste != null && neste.venstre != fnode) {
        fnode = neste;
        neste = neste.opp;
      }
      return neste;
    }
  }

  BinNode nestePrefiks() {
    if (venstre != null) return venstre;
    else if (hoyre != null) return hoyre;
    else {// Er i en bladnode. M? lete oppover til vi kommer fra venstre
          // og til en forgjengernode som har et h?yrebarn (som blir neste).
      BinNode neste = opp, fnode = this;
      while (neste != null && (neste.hoyre == fnode || neste.hoyre == null)) {
        fnode = neste;
        neste = neste.opp;
      }
      if (neste == null) return null;
      else return neste.hoyre;
    }
  }

  BinNode nestePostfiks() {
    // I postfiks behandles en node alltid etter alle nodene i begge
    // subtr?rne. Vi m? dermed alltid lete oppover i treet igjen.
    if (opp == null) return null;      // ferdig
    if (opp.hoyre == this) return opp; // opp siste i subtreet med opp som rot
    // Hit hvis opp.venstre == this
    BinNode neste = opp.hoyre;
    if (neste == null) return opp;  // opp har ikke h?yre subtre
    // finn minste i h?yre subtre til opp
    while (neste.venstre != null) neste = neste.venstre;
    return neste;
  }
}
////////////////////////////

public class BinSokeTre {
  BinNode rot=null;

  void settInn(int i, int a) {
    rot = settInn(i, a, rot, null);
  }

  BinNode settInn(int i, int a, BinNode n, BinNode opp) {
    if (n==null) n = new BinNode(i, a, opp);
    else if (i<n.verdi) n.venstre = settInn(i, a, n.venstre, n);
    else if (i>n.verdi) n.hoyre = settInn(i, a, n.hoyre, n);
    else {//duplikat
//alt1: gj?r ingenting:
//    ; 
// alt2: sett inn duplikat til h?yre:
//      n.hoyre = settInn(i, a, n.hoyre, n);
// alt3: sett inn duplikat til venstre:
//      n.venstre = settInn(i, a, n.venstre, n); 
// alt 4: se oppgave 2.c
      BinNode h = n.hoyre;
      if (h==null) n.hoyre = new BinNode(i, a, n);
      else if (h.verdi==i) {
        BinNode hv = h.venstre;
        h.venstre = new BinNode(i, a, h);
        h.venstre.venstre = hv;
        if (hv!=null) hv.opp = h.venstre;
      } else {
        n.hoyre = new BinNode(i, a, n);
        n.hoyre.hoyre = h;
        h.opp = n.hoyre;
      }

    }
    return n;
  }

  BinNode forsteInfiks() {
    BinNode n = rot;
    if (n==null) return null;
    while (n.venstre!=null) n = n.venstre;
    return n;
  }

  BinNode forstePrefiks() {
    return rot;
  }

  BinNode forstePostfiks() {
    BinNode n = rot;
    if (n==null) return null;
    while (true) {
      if (n.venstre!=null) n = n.venstre;
      else if (n.hoyre!=null) n = n.hoyre;
      else return n;
    }
  }
}
////////////////////////////

public class TestProg {
  public static void main(String[] args) {
    // Inndata til programmet.
    // Eksempel:
    int [] inn = {6, 2, 15, 2, 1, 1, 9, 2, 12, 9, 2, 2, 8, 2, 17};

    BinSokeTre tre = new BinSokeTre();

    for (int i=0; i<inn.length; i++) {
      tre.settInn(inn[i], i);
    } 
    System.out.println("Innlesing ferdig.");
    System.out.println("Infiks.");
    BinNode n = tre.forsteInfiks();
    while (n!=null) {
      System.out.print(n.verdi+","+n.andredata+" ");
      if (n.venstre!=null) System.out.print("v:"+n.venstre.verdi+" ");
      if (n.hoyre!=null) System.out.print("h:"+n.hoyre.verdi+" ");
      if (n.opp!=null) System.out.print("o:"+n.opp.verdi+" ");
      System.out.println(".");
      n = n.nesteInfiks();
    }
  
    System.out.println("Prefiks.");
    n = tre.forstePrefiks();
    while (n!=null) {
      System.out.print(n.verdi+" ");
      n = n.nestePrefiks();
    }
    System.out.println(".");

    System.out.println("Postfiks.");
    n = tre.forstePostfiks();
    while (n!=null) {
      System.out.print(n.verdi+" ");
      n = n.nestePostfiks();
    }
    System.out.println(".");
  }
}

///////////////////////////////////////////////////////////////////
// Oppgave 3
//

/*
 * Oppgave 3
 * L?sning: Snu alle opp-pekerne mellom den gamle og den nye roten.
 * Merk at dette ligner veldig p? koden for ? snu en enkellenket
 * (pekerkjede-)liste!
 */
void forandreRot(BinNode nyRot) {
  BinNode n1 = nyRot, n2 = nyRot.opp, n3;
  nyRot.opp = null;

  while (n2 != null) {
    n3 = n2.opp;
    // N? ligger n1, n2, n3 etter hverandre
    // langs den gamle veien mot roten.
    n2.opp = n1;
    n1 = n2;
    n2 = n3;
  }
}

///////////////////////////////////////////////////////////////////
// Oppgave 4
//
a) LIFO gir prefiks-rekkef?lge. 
   FIFO gir bredde f?rst (dybde 0, 1, 2, . . ). Hverde dybde fra h?yre
   mot venstre. 

b) Prefiks-variant hvor h?yre subtre behandles f?r venstre subtre.

c) Hovedpoenget for ? overbevise seg om at invarianten gjelder er:
   * en node behandles ikke f?r den er tatt ut av lista
   * tas ut av lista kommer etter puttes inn i lista
   * puttes inn i lista av forelder-noden etter at denne er behandlet.