Løsningsforslag - oppgaver i Avsnitt 5.1.14


Oppgave 1

  public boolean isomorf(BinTre<?> tre)
  {
    int[] a = nodeposisjonerNivåorden();
    int[] b = tre.nodeposisjonerNivåorden();

    return Arrays.equals(a, b);
  }

Oppgave 2

  private static boolean equals(Node<?> p, Node<?> q)
  {
    if (p == null && q == null) return true;   // to tomme trær
    if (p == null ^ q == null) return false;   // tomt og ikke tomt
    if (p.verdi == null ^ q.verdi == null) return false;
    return ((p.verdi == null && q.verdi == null)
                        || (p.verdi.equals(q.verdi))) &&
      equals(p.venstre, q.venstre) && equals(p.høyre, q.høyre);
  }

Oppgave 3

  public boolean equals(BinTre<T> tre)
  {
    if (this == tre) return true;
    if (antall != tre.antall) return false;
    return equals(rot,tre.rot);
  }

Oppgave 4

  private static <T> void kopi(Node<T> p, Node<T> q)
  {
    if (q.venstre != null)
    {
      p.venstre = new Node<>(q.venstre.verdi);
      kopi(p.venstre,q.venstre);
    }
    if (q.høyre != null)
    {
      p.høyre = new Node<>(q.høyre.verdi);
      kopi(p.høyre,q.høyre);
    }
  }

  public BinTre(BinTre<T> tre)     // ny kopieringskonstruktør
  {
    if (tre.rot != null)
    {
      rot = new Node<>(tre.rot.verdi);
      kopi(rot, tre.rot);
      antall = tre.antall;
    }
  }

Oppgave 5

  public int hashCode()
  {
    if (rot == null) return 0;
    int[] a = {0,0};
    hashCode(rot, 1, a);
    return a[0]*a[1];
  }

  private static <T> void hashCode(Node<T> p, int k, int[] a)
  {
    a[0] += k;
    a[1] += p.verdi.hashCode();
    if (p.venstre != null) hashCode(p.venstre, 2*k, a);
    if (p.høyre != null) hashCode(p.høyre, 2*k + 1, a);
  }

Hvis hashCode()-metoden ovenfor brukes, vil flg. to trær være ulike, men gi samme tall. Kanskje du har forslag til hvordan metoden kunne forbedres?

    int[] p = {1,2};
    Integer[] v1 = {1,2};
    Integer[] v2 = {2,1};
    BinTre<Integer> tre1 = new BinTre<>(p,v1);
    BinTre<Integer> tre2 = new BinTre<>(p,v2);

    System.out.println(tre1.equals(tre2));
    System.out.println(tre1.hashCode() + " " + tre2.hashCode());