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());