Generischer Binärbaum - löschen

[Neele]

Hallo,

für eine Hausaufgabe soll ich einen generischen binären Suchbaum erstellen. Das funktioniert auch schon so weit, bloß mit dem Löschen eines Objekts habe ich noch Probleme. Erstmal der Code:

/**
 * Yet another AVL tree implementation done in Java
 * This one contains recursion to do its job
 *
 * @param <t> java generic wildcard
 */
public class GenericBinaryTree<t extends="" comparable<t="">> {

    /**
     * Das aktuelle T
     */
    private T item;

    /**
     * Der linke Teilbaum
     */
    private GenericBinaryTree<t> left;

    /**
     *Der rechte Teilbaum
     */
    private GenericBinaryTree<t> right;

    /**
     * Konstruktor, erzeugt leere Liste
     */
    public GenericBinaryTree() {
        this.item = null;
        this.left = null;
        this.right = null;
    }

    /**
     * Ueberprueft ob der Baum leer ist
     *
     * @return true, Baum ist leer
     */
    public boolean isEmpty() {
        return this.left == null && this.right == null;
    }

    /**
     * Gibt die Anzahl der Elemente im Baum zurück
     *
     * @return die Groesse
     */
    public int length() {
        if (this.isEmpty()) {
            return 0;
        } else {
            return (this.left.length() + this.right.length() + 1);
        }
    }

    /**
     * Prueft ob ein T in der Liste ist
     *
     * @param x das T
     * @return true, x ist in der Liste enthalten
     */
    public boolean isInList(T x) {
        if (this.isEmpty()) {
            return false;
        } else if (this.item.equals(x)) {
            return true;
        } else {
            return (this.left.isInList(x) || this.right.isInList(x));
        }
    }

    /**
     * Gibt das i-te T der Liste zurueck
     *
     * @param i der Index
     * @return das i-te T
     * @throws IndexOutOfBoundsException wenn i < 0 oder  i >= length()
     */
    public T getItem(int i) throws IndexOutOfBoundsException {
        if (i < 0 || i >= this.length()) {
            throw new IndexOutOfBoundsException();
        } else if (i < this.left.length()) {
            return this.left.getItem(i);
        } else if (i > this.left.length()) {
            return this.right.getItem(i - this.left.length() - 1);
        } else {
            return this.item;
        }
    }

    /**
     * Gets height of tree
     * 
     * @return height
     */
    public int height() {
        if (this.isEmpty()) {
            return 0;
        } else {
            int a = this.left.height();
            int b = this.right.height();
            return a < b ? b + 1 : a + 1;
        }
    }

    /**
     * Fuegt ein Element sortiert in den Baum ein
     *
     * @param x das Element
     * @return der geaenderte Baum
     */
    public GenericBinaryTree<t> insert(T x) {
        if (x.equals(null)) {
            return this;
        }
        if (this.isEmpty()) {
            GenericBinaryTree<t> tmpleft = new GenericBinaryTree<t>();
            GenericBinaryTree<t> tmpright = new GenericBinaryTree<t>();
            this.left = tmpleft;
            this.right = tmpright;
            this.item = x;
            return this;
        } else if (this.item.compareTo(x) <= 0){
            return this.right.insert(x);
        } else {
            return this.left.insert(x);
        }
    }

    /**
     * Loescht das erste vorkommen des Ts x
     *
     * @param x das T
     * @return die geanderte Liste
     */
    public GenericBinaryTree<t> delete(T x) {
        if (!this.isInList(x)){
            return this;
        } else if (this.item.equals(x)) {
            return this.delete();
        } else if (this.item.compareTo(x) <= 0) {
            return this.right.delete(x);
        } else {
            return this.left.delete(x);
        }
    }

    /**
     * Loescht die Wurzel des Baums
     *
     * @return die geanderte Liste
     */
    public GenericBinaryTree<t> delete() {
        if (this.isEmpty()) {
            return this;
        } else if (this.left.isEmpty()) {
            this.item = this.right.item;
            this.left = this.right.left;
            this.right = this.right.right;
            return this;
        } else if (this.right.isEmpty()) {
            this.item = this.left.item;
            this.left = this.left.left;
            this.right = this.left.right;
            return this;
        } else {
            //TODO
            T x = this.right.getItem(0); //this should be copied instead
            this.left.delete(x);
            this.item = x;
            return this;
        }
    }

    /**
     *macht aus der Liste nen kurzen String
     *(gezählte Elemente)
     *
     *@return String
     */
    public String toShortString() {
        String s = "";
        int k = 0;
        if (this.isEmpty()) {
            s = "-empty- \n";
        } else {
            int j = 1; 
            for (int i = 0; i < this.length(); i++) {
                if (i + 1 < this.length() && this.getItem(i).equals(this.getItem(i + 1))) {
                    j++;
                } else {
                    s = s + k + " - " + this.getItem(i).toString() + " (" + j + "x)\n";
                    j = 1;
                    k++;
                }
            }
        }
        return s;
    };


    public String toString2(String str) {
    
        String newstr = str + " -> " + this.item + "\n";
        
        if (this.left != null) {
            newstr += this.left.toString2(str + "l");
        }

        if (this.right != null) {
            newstr += this.right.toString2(str + "r");
        }

        return newstr;
    }

    /**
     *macht aus der Liste nen String
     *
     *@return String
     */
    public String toString() {
        String s = "";
        if (this.isEmpty()) {
            System.out.print( "-empty- \n");
        } else {
            for (int i = 0; i < this.length(); i++) {
                System.out.print(s + i + " - " + this.getItem(i).toString() + "\n");
            }
        }
        return s;
    }


    /**
     * main method for testing purposes
     *
     * @param args commandline arguments
     */
    public static void main(String[] args) {
        GenericBinaryTree<quest> l = new GenericBinaryTree<quest>();

        int[] a = {3, 2, 0, 1, 5, 4, 6};
        int citm = a.length;
        Quest[] itm = new Quest[citm];
        
        System.out.println("Empty: (true) " + l.isEmpty());
        System.out.println("Height: (0) " + l.height());
        System.out.println("Length: (0) " + l.length());

        System.out.println("Items to add...");
        for (int i = 0; i < citm; i++) {
            itm[i] = new Quest("Quest " + a[i], "Prequest " + i, "Item " + i, i+2);
            //itm[i].setName("Item No. " + ((int) (Math.random() * 100)) );
            System.out.println(i + ". " + itm[i]);
        }
        
        
        System.out.println("\nList stuff...");

        for (int i = 0; i < citm; i++) {
            l.insert(itm[i]);
            System.out.println("length: " + l.length());
            System.out.println(l);
        }


        System.out.println("== GET FIRST ITEM");
        System.out.println(l.getItem(0));


        System.out.println("== GET ITEM BY INDEX");
        for (int i = 0; i < citm; i++) {
            System.out.println("getItem(" + i + ") -> " + l.getItem(i));
        }

        System.out.println(l.toString2(""));

        System.out.println("== DELETE FIRST");
        l.delete();
        System.out.println("deleted");
        System.out.println(l);

        System.out.println(l.toString2(""));

        System.out.println("== CHECK IF IN LIST");
        for (int i = 0; i < citm; i++) {
            if (l.isInList(itm[i])) {
                System.out.println("  found   \"" + itm[i] + "\"");
            } else {
                System.out.println("not found \"" + itm[i] + "\"");
            }
        }

        System.out.println("== DELETE ALL");
        for (int i = 0; i < citm; i++) {
            System.out.println("delete(" + itm[i] + ")");
            l.delete(itm[i]);
            System.out.println("deleted");
            System.out.println(l);
        }

        System.out.println("== END OF TEST");
    }
}

Könnt ihr mir helfen a) das Element in Zeile 167 tatsächlich zu kopieren und
<s>b) herauszufinden, woher die NullPointerException kommt, die zurzeit geworfen wird?</s>

Edit zu b): Ich verstehe, woher die Exception kommt: dadurch, dass ich die Wurzel des Baumes verändere, verändert sich auch der Teilbaum, der eigentlich leer sein sollte - und ein nicht-leerer Knoten, dessen Kinder null sind, führt zu NullPointerExceptions

Vielen Dank im Vorraus!
Neele</quest></quest></t></t></t></t></t></t></t></t></t></t></t>

 

[Neele]

Inzwischen habe ich, mit der Hilfe eines Kumpels, eine Lösung gefunden. Die delete()-Methode (ehemals Zeile 152-170) sieht jetzt so aus:

    /**
     * Loescht die Wurzel des Baums
     *
     * @return die geanderte Liste
     */
    public GenericBinaryTree<T> delete() {
        if (this.isEmpty()) {
            return this;
        } else if (this.left.isEmpty()) {
            this.item = this.right.item;
            this.left = this.right.left;
            this.right = this.right.right;
            return this;
        } else if (this.right.isEmpty()) {
            this.item = this.left.item;
            this.right = this.left.right;
            this.left = this.left.left;
            return this;
        } else {
            T x = this.right.getItem(0).clone(); 
            this.right.delete(this.right.getItem(0));
            this.item = x;
            return this;
        }
    }

Damit ist das kopier-Problem gelößt. Um sicherzustellen, dass die Methode clone() auch im Datentypen vorhanden ist, hat sich Zeile 7 geändert:

public class GenericBinaryTree<T extends Secret<T>> implements List<T> {

und das interface Secret sieht so aus:

public interface Secret<T> extends Comparable<T> {
    T clone();    
}

So einfach kann es sein! Für Verbesserungsvorschläge bin ich natürlich offen.

Liebe Grüße, Neele