INF1020 l?sningsforslag uke 1
=============================


OPPGAVE 2:
----------

a) O(n^2)

b) O(log2(n))


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

public class Traverser {
  public static void main(String[] args) {
    Node rot = new Node(1,
                        new Node(2, new Node(4,
                                               null,
                                               new Node(5,
                                                        new Node(6,
                                                                 null,
                                                                 null),
                                                        null)),
                                 new Node(3,
                                          new Node(7,
                                                   null,
                                                   null),
                                          null)),
                        null);

    traverser(rot, 0);
    rot.skrivUt();
  }

  static void traverser(Node tre, int db) {
    Node barn;
    
    // Dybden kan umiddelbart gis riktig verdi.
    tre.dybde = db;
    
    // Antall og h?yde settes forel?pig som om det er en bladnode.
    tre.antall = 1;
    tre.hoyde = 0;
    
    if (tre.forsteBarn == null) {
      // Dette er en bladnode
      tre.bladAvstand = 0;
    } else {
      // Skal finne MINSTE avstand til en bladnode,
      // denne er i hvert fall mindre enn MAX_VALUE.
      tre.bladAvstand = Integer.MAX_VALUE;
    }
    
    barn = tre.forsteBarn;
    while (barn != null) {
      traverser(barn, db + 1);     
      tre.antall += barn.antall;
      if (barn.hoyde + 1 > tre.hoyde) {
	    tre.hoyde = barn.hoyde + 1;
      }
      if (barn.bladAvstand + 1 < tre.bladAvstand) {
	    tre.bladAvstand = barn.bladAvstand + 1;
      }      
      barn = barn.nesteSosken;
    }   
  }
}



class Node {
  int data;
  Node forsteBarn, nesteSosken;
  int dybde, hoyde, antall, bladAvstand;

  Node(int d, Node f, Node n) {
    data = d;
    forsteBarn = f;
    nesteSosken = n;
  }

  void skrivUt() {
    System.out.println(data + ": ");
    System.out.println("   Dybde: " + dybde);
    System.out.println("   H?yde: " + hoyde);
    System.out.println("   Antall: " + antall);
    System.out.println("   BladAvstand: " + bladAvstand);
    System.out.print("");
    if (forsteBarn != null) {
      forsteBarn.skrivUt();
    }
    if (nesteSosken != null) {
      nesteSosken.skrivUt();
    }
  }
}


OPPGAVE 5:
----------

/* L?sning: Snu alle forelder-pekerne mellom den gamle og den nye roten */

void forandreRot(Node nyRot) {
  Node n1, n2, n3;
  n1 = nyRot;
  n2 = nyRot.forelder;
  nyRot.forelder = null;

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

    n2.forelder = n1;
    n1 = n2;
    n2 = n3;
  }
}