INF1020 l?sningsforslag uke 2
=============================


OPPGAVE 3:
----------

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


BinNode nestePrefiks() {
    BinNode neste, fnode;
    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).
        neste = forelder;
	fnode = this;
        while (neste != null &&
                  (neste.hoyre == fnode || neste.hoyre == null)) {
            fnode = neste;	   
            neste = neste.forelder;
        }
        if (neste != null) {
            neste = neste.hoyre;
        }
        return neste;
    }
  }


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



OPPGAVE 4:
----------


/*
 *  OPPGAVE B:
 *     Infiks og innsetting til h?yre: FIFO
 *     Infiks og innsetting til venstre: LIFO
 */



/* OPPGAVE C */

void settInn(Object x) {
  BinNode n, ny;
  ny = new BinNode(x);

  if (rot == null) {
    rot = ny;
  } else {
    n = rot;
    while (n != ny) {
      if (ny.element.verdi < n.element.verdi) {
	if (n.venstre == null) {
	  n.venstre = ny;
	}
	n = n.venstre;

      } else if (ny.element.verdi > n.element.verdi) {
	if (n.hoyre == null) {
	  n.hoyre = ny;
	}
	n = n.hoyre;

      } else {
	if (n.hoyre == null || n.hoyre.element.verdi != n.element.verdi) {
	  // ny er node 2 med samme verdi
	  ny.hoyre = n.hoyre;
	  n.hoyre = ny;
	  n = ny;
	} else {
	  // Nummer 3, 4, 5, ....
	  // NB! Setter inn F?RST i listen!
	  ny.venstre = n.hoyre.venstre;
	  n.hoyre.venstre = ny;
	  n = ny;
	}
      }
    }
  }
}



/*
 * OPPGAVE D:
 *    Rekkef?lgen blir i utgangspunktet: 1, 3, 4, ..., 2
 */

void utskrift(BinNode n) {
  if (n != null) {
    utskrift(n.venstre);
    System.out.println(n.element);
    if (n.hoyre != null && n.hoyre.element.verdi == n.element.verdi) {
      System.out.println(n.hoyre.element);
      utskrift(n.hoyre.venstre);
      utskrift(n.hoyre.hoyre);
    } else {
      utskrift(n.hoyre);
    }
  }
}