Løsningsforslag
Oppgavesett 3

Les først oppgaveteksten for øvelse 4.

Oppgave 1

1.1

public class bt1 {

    bt1(int n) {
        size = n;
        nodes = new int[size];
        clearTree();
    }

    private void clearTree() {
        for (int i = 0; i < size; i++)
            nodes[i] = 0;
    }

    public int verdi(int i){
        return nodes[i - 1];    // Rot = 1
    }

    public int lagTre(int x) {
        clearTree();
        nodes[0] = x;
        return 1;               // Rot
    }

    public void lagIntern(int i, int x, int y) {
        settInn(venstre(i),x);
        settInn(hoyre(i),y);
    }

    public int foreld(int i) {
        return i/2;      // Integer division truncates
    }

    public int venstre(int i) {
        return 2*i;
    }

    public int hoyre(int i) {
        return 2*i+1;
    }

    public boolean erIntern(int i) {
        return ((verdi(venstre(i)) != 0) || (verdi(hoyre(i)) != 0));
    }

    public boolean erEkstern(int i) {
        return !erIntern(i);
    }

    public boolean erRot(int i) {
        return (i == 1);
    }

    public void swap(int i, int j) {
        int temp = verdi(j);
        settInn(j, verdi(i));
        settInn(i, temp);
    }

    public void settInn(int i, int x) {
        nodes[i-1] = x;
    }

    public void fjernEkstern(int i) {
        nodes[i-1] = 0;
    }

    public int antall() {
        int n = 0;
        for (int i = 1; i < (size + 1); i++)
            if (verdi(i) != 0)
                n++;
        return n;
    }

    public void skrivUtPre(int i) {
        skriv(i);
        if (erIntern(i)) {
            skrivUtPre(venstre(i));
            skrivUtPre(hoyre(i));
        }
    }

    public void skrivUtPost(int i) {
        if (erIntern(i)) {
            skrivUtPost(venstre(i));
            skrivUtPost(hoyre(i));
        }
        skriv(i);
    }

    public void skrivUtInn(int i) {
        if (erIntern(i))
            skrivUtInn(venstre(i));
        skriv(i);
        if (erIntern(i))
            skrivUtInn(hoyre(i));
    }

    private void skriv(int i) {
        System.out.println("Node " + i + ": " + verdi(i));
    }

}
---------------------------
Testing:

public class bttest {
 
    public static void main(String[] args) {

        bt1 tre = new bt1(100);

        int rot = tre.lagTre(9);
        tre.skrivUtPre(rot);

        tre.lagIntern(rot, 3, 6);

        tre.lagIntern(tre.venstre(rot), 2, 8);
        System.out.println(tre.verdi(tre.hoyre(tre.venstre(tre.foreld(tre.hoyre(rot))))));  //8

        tre.swap(tre.venstre(rot), tre.hoyre(rot));

        System.out.println("Pre: ");
        tre.skrivUtPre(rot);

        System.out.println("Post: ");
        tre.skrivUtPost(rot);

        System.out.println("Inn: ");
        tre.skrivUtInn(rot);

        System.out.println("Antall: " + tre.antall());
    }
}
 

1.2

public class ArrayBt implements bt{

    private int size = 100;
    private ArrayPosisjon[] nodes;

    ArrayBt(int n) {
        size = n;
        nodes = new ArrayPosisjon[size];
        for (int i = 0; i < size; i++) {
            nodes[i] = new ArrayPosisjon();
            nodes[i].setIndex(i+1);
        }
    }

    private void clearTree() {
        for (int i = 0; i < size; i++)
            nodes[i].setElement(null);
    }

    public Posisjon lagTre(Object x) {
        clearTree();
        nodes[0].setElement(x);
        return nodes[0];
    }

    public void lagIntern(Posisjon p, Object x, Object y) {
        settInn(venstre(p),x);
        settInn(hoyre(p),y);
    }

    public Posisjon foreld(Posisjon p) {
        ArrayPosisjon a = null;
        try {
            a = (ArrayPosisjon) p;
        } catch(ClassCastException ex) {
            System.err.println("ArrayBt: feil type Posisjon-objekt!");
            System.exit(0);
        }
        return nodes[a.getIndex()/2 - 1];      // Integer division truncates
    }

    public Posisjon venstre(Posisjon p) {
        ArrayPosisjon a = null;
        try {
            a = (ArrayPosisjon) p;
        } catch(ClassCastException ex) {
            System.err.println("ArrayBt: feil type Posisjon-objekt!");
            System.exit(0);
        }
        return nodes[2*a.getIndex() - 1];
    }

    public Posisjon hoyre(Posisjon p) {
        ArrayPosisjon a = null;
        try {
            a = (ArrayPosisjon) p;
        } catch(ClassCastException ex) {
            System.err.println("ArrayBt: feil type Posisjon-objekt!");
            System.exit(0);
        }
        return nodes[2*a.getIndex()+1 - 1];
    }

    public boolean erIntern(Posisjon p) {
        return ((venstre(p).getElement() != null) || (hoyre(p).getElement() != null));
    }

    public boolean erEkstern(Posisjon p) {
        return !erIntern(p);
    }

    public boolean erRot(Posisjon p) {
        ArrayPosisjon a = null;
        try {
            a = (ArrayPosisjon) p;
        } catch(ClassCastException ex) {
            System.err.println("ArrayBt: feil type Posisjon-objekt!");
            System.exit(0);
        }
        return (a.getIndex() == 1);
    }

    public void swap(Posisjon p, Posisjon q) {
        Object temp = q.getElement();
        settInn(q, p.getElement());
        settInn(p, temp);
    }

    public void settInn(Posisjon p, Object x) {
        p.setElement(x);
    }

    public void fjernEkstern(Posisjon p) {
        p.setElement(null);
    }

    public int antall(Posisjon rot) {
        if (erIntern(rot))
            return antall(venstre(rot)) + antall(hoyre(rot)) + 1;
        else return 1;
    }

    public void skrivUtPre(Posisjon p) {
        skriv(p);
        if (erIntern(p)) {
            skrivUtPre(venstre(p));
            skrivUtPre(hoyre(p));
        }
    }

    public void skrivUtPost(Posisjon p) {
        if (erIntern(p)) {
            skrivUtPost(venstre(p));
            skrivUtPost(hoyre(p));
        }
        skriv(p);
    }

    public void skrivUtInn(Posisjon p) {
        if (erIntern(p))
            skrivUtInn(venstre(p));
        skriv(p);
        if (erIntern(p))
            skrivUtInn(hoyre(p));
    }

    private void skriv(Posisjon p) {
        ArrayPosisjon a = null;
        try {
            a = (ArrayPosisjon) p;
        } catch(ClassCastException ex) {
            System.err.println("ArrayBt: feil type Posisjon-objekt!");
            System.exit(0);
        }
        System.out.println("Node " + a.getIndex() + ": " + a.getElement());
    }

}
--------------------------------
public class ArrayBtTest {
 
    public static void main(String[] args) {

        bt tre = new ArrayBt(100);

        Posisjon rot = tre.lagTre(new Integer(9));
        tre.skrivUtPre(rot);

        tre.lagIntern(rot, new Integer(3), new Integer(6));

        tre.lagIntern(tre.venstre(rot), new Integer(2), new Integer(8));
        System.out.println(tre.hoyre(tre.venstre(tre.foreld(tre.hoyre(rot)))).getElement());  //8

        tre.swap(tre.venstre(rot), tre.hoyre(rot));

        System.out.println("Pre: ");
        tre.skrivUtPre(rot);

        System.out.println("Post: ");
        tre.skrivUtPost(rot);

        System.out.println("Inn: ");
        tre.skrivUtInn(rot);

        System.out.println("Antall: " + tre.antall(rot));
    }
}
-------------------------
public class ArrayPosisjon implements Posisjon{

    private int indeksITabell;
    private Object element;

    public void setElement(Object e) {
        element = e;
    }

    public Object getElement() {
        return element;
    }
 
    int getIndex() {
        return indeksITabell;
    }

    void setIndex(int i) {
        indeksITabell = i;
    }

    ArrayPosisjon() {
        indeksITabell = 0;
        element = null;
    }

    /*    static Posisjon newPos(Object x, int index) {
        p = new Posisjon;
        p.setIndex(index);
        p.setElement(x);
        }*/
 
}
--------------------------------
public interface Posisjon{

    public void setElement(Object e);
    public Object getElement();
 
}
-------------------------------
public interface bt {

    public Posisjon lagTre(Object x);

    public void lagIntern(Posisjon p, Object x, Object y);

    public Posisjon foreld(Posisjon p);

    public Posisjon venstre(Posisjon p);

    public Posisjon hoyre(Posisjon p);

    public boolean erIntern(Posisjon p);

    public boolean erEkstern(Posisjon p);

    public boolean erRot(Posisjon p);

    public void swap(Posisjon p, Posisjon q);

    public void settInn(Posisjon p, Object x);

    public void fjernEkstern(Posisjon p);

    public int antall(Posisjon rot);

    public void skrivUtPre(Posisjon p);

    public void skrivUtPost(Posisjon p);

    public void skrivUtInn(Posisjon p);

}