OOP Über einen AVL-Baum iterieren (NullPointer)

[Butterbrot]

Guten Abend Community,

momentan schreibe ich an einem binären Suchbaum, über den ich iterieren möchte. Sobald ich aber meinen Iterator, der nach der Tiefensuche iteriert, ausführe erhalte ich eine NullPointerException. Dieser Nullpointer ergibt sich, sobald ich in der Zeile "stack.push(current)", also tippe ich darauf, dass mein "current" nichts ist. Sobald ich aber anstatt dem Startwert, die Wurzel "root" am Anfang der Klasse verwende, erhalte ich ebenfalls einen NullPointer. Nun ist meine Frage, mit was ich meinen Startwert nun instanziieren muss oder ob mein Ansatz generell falsch ist? Generell habe ich etwas Schwierigkeiten den Iterator zu schreiben und wäre über jegliche Tipps und Anregungen sehr dankbar. Ich habe folgende Klasse geschrieben und habe zwar nur mit der Iterator()-Methode ein paar Probleme, dennoch poste ich die gesamte Klasse, damit sich Fragen im Vorfeld ergeben sollten bzw. man die Struktur besser erkennen kann. Danke im Voraus 🙂

public class AuDTree<E extends Comparable<? super E>> implements AuDTreeInterface<E> {

    private class Node{

        public Node left;
        public Node right;
        public Node parent;
        public E value;

        public Node(E value){
            left = null;
            right = null;
            parent = null;
            this.value = value;
        }

    }

    public Node root;

    public AuDTree(){
        this.root = null;
    }


    @Override
    public boolean isEmpty() {
        if(root == null){
            return true;
        }
        else{
            return false;
        }

    }

    @Override
    public int count() {

        return count(root);

    }

    private int count(Node n) {
        if (n == null) return 0; 
        else { 
            int l = 1;
            l += count(n.left); 
            l += count(n.right); 
            return l; 
        }

    }

    @Override
    public int getHeight() {
        return getHeight(root);
    }

    private int getHeight(Node n) {
        if (n == null) {
            return -1;
        }
        return Math.max(getHeight(n.left), getHeight(n.right)) + 1;
    }

    @Override
    public boolean isAVLTree() {
        return isAVLTree(root);

    }

    public boolean isAVLTree(Node n){

        if(root == null) return true;

        if(root.value.compareTo(getMinValue()) <= 0 || root.value.compareTo(getMaxValue()) >=0) {
            return false;
        }

        else{
            if(n.left != null)isAVLTree(n.left);
            if(n.right != null)isAVLTree(n.right);

            if(getHeight(n.left) - getHeight(n.right) > 1 || getHeight(n.right) - getHeight(n.left) > 1 ){
                return false;
            }
            return true;

        }

    }

    @Override
    public boolean contains(E value) {

        if(isEmpty()) return false;
        else{
            Node current = root;

            while (current != null) {
                int comparison = value.compareTo(current.value);
                if (comparison == 0) {
                    return true;
                } else if (comparison < 0) {
                    current = current.left;
                } else { //comparison > 0
                    current = current.right;
                }
            }

            return false;
        }

    }

    @Override
    public void insert(E value) throws ElementExistsException {
        if(contains(value)) throw new ElementExistsException();
        else{
            if(root == null) root = new Node(value);
            else{
                Node father = null;
                Node k = root;
                while(k != null){
                    father = k;
                    if(value.compareTo(k.value) < 0){
                        k = k.left;
                    }
                    else{
                        if(value.compareTo(k.value) > 0){
                            k = k.right;
                        }
                    }
                }

                if(value.compareTo(father.value) < 0){
                    father.left = new Node(value);
                }
                else{
                    father.right = new Node(value);
                }
            }
        }
    }


    @Override
    public void remove(E value) throws ElementExistsException {
        if(!contains(value)) throw new ElementExistsException("Gibts nicht!");
        else{
            Node node = finds(value);
            node = deleteNode(node);
        }
    }

    private Node deleteNode(Node node){

        Node newNode = node;

        if(node.left == null && node.right == null) newNode = null;
        else if(node.left != null && node.right == null) newNode = node.left;
        else if(node.left == null && node.right != null) newNode = node.right;
        else{
            if(quantityofchildren(biggest(node.left)) == 0){
                newNode = biggest(node.left);
            }
            else{
                Node secondNode = node;
                newNode = biggest(node.left);
                secondNode = biggest(node.left).left;
            }

        }

        return node;
    }

    private Node finds(E value){

        Node current = root;

        while (current != null) {
            int comparison = value.compareTo(current.value);
            if (comparison == 0) {
                return current;
            } else if (comparison < 0) {
                current = current.left;
            } else { //comparison > 0
                current = current.right;
            }
        }

        return current;

    }

    private int quantityofchildren(Node node){

        return getHeight(node);
    }

    private String leftorrightchildren(Node node){

        if(node.value.compareTo(node.parent.value) > 0) return "right";
        else return "left";
    }

    private Node biggest(Node node){

        Node start = node;

        while(start.right != null){
            start = start.right;
        }

        return start;

    }

    private E smallest(Node node){

        Node start = node;

        while(start.left != null){
            start = start.left;
        }

        return start.value;
    }


    @Override
    public Iterator<E> iterator() {

        return new Iterator<E>(){
            Node start;
            Node current;
            int counter;
            Stack<Node> stack;

            public void iterator() {
                start = new Node(null);
                counter++;
                stack = new Stack<Node>();
                current = start;
                stack.empty();
            }
           
            @Override
            public boolean hasNext() {
                if(counter == count(root)) return false;
                else return true;
            }

            @Override
            public E next() {
                stack.push(current);
                counter++;
                if(current.left.value != null) return current.left.value;
                else return current.right.value;
            }

        };
    }

    @Override
    public Iterator<E> iteratorBFS() {
        return new Iterator<E>(){

            @Override
            public boolean hasNext() {
                // TODO Auto-generated method stub
                return false;
            }

            @Override
            public E next() {
                // TODO Auto-generated method stub
                return null;
            }

        };
    }

    @Override
    public E getMinValue() {

        Node node = root;

        while(node.left != null){
            node = node.left;
        }

        return node.value;
    }

    @Override
    public E getMaxValue() {

        Node node = root;

        while(node.right != null){
            node = node.right;
        }

        return node.value;
    }



    public static void main(String[] args) {

        AuDTree<Integer> a = new AuDTree<Integer>();
        a.insert(3);
        a.insert(2);
        a.insert(4);
        a.insert(1);
        a.insert(0);
        //        System.out.println(a.finds(4));
        //        a.insert(5);
        //        a.insert(4);
        //        a.insert(3);


        //        System.out.println(a.count());
        //        System.out.println(a.contains(3));
        //        System.out.println(a.getHeight());
        //        System.out.println(a.contains(10));
        //        System.out.println(a.isAVLTree());
        //        System.out.println(a.getMinValue());
        //        System.out.println(a.getMaxValue());

        //        a.remove(0);

        for(Integer element : a){
            System.out.println(element);
        }
    }
}

 

[bene2808]

Wird denn die Methode iterator() zum Initialisieren des Iterators irgendwo aufgerufen...?

Und zum Ansatz: Wenn eines der Enden des Baums erreicht wird, also wenn der aktuelle Knoten weder linken noch rechten Nachfolger hat, musst du wieder nach oben.

 

[Butterbrot]

Meinst du sowas:
if(current.left == null && current.right == null) return root.value ?
Wenn ja, stimmt, daran habe ich nicht gedacht.
Aber was genau meinst du mit:

Wird denn die Methode iterator() zum Initialisieren des Iterators irgendwo aufgerufen...?

Muss ich den Iterator etwa in der next()-Methode aufrufen?
Danke im Voraus.

 

[bene2808]

Naja der Iterator scheint, wie du sagst, nach der Tiefensuche in die Tiefe zu gehen, aber von da kommt er nicht mehr raus, um auch noch die anderen Zweige des Baums abzuklappern. Wenn also tatsächlich beide Nachfolger des aktuellen Knotens null sind, musst du am besten in einer Schleife die Struktur wieder so weit nach oben gehen, bis du einen Knoten findest, an dem du einen Zweig noch nicht durchsucht hast (das ist dann wenn dann der rechte, wenn du immer mit dem linken beginnst; hier musst du aber darauf achten, dass du nicht bereits aus dem rechten kommst: sollte dies der Fall sein musst du weiter nach oben).

Zur NullPointerException: Du definierst eine Methode iterator() in deiner lokalen Iterator-Klasse, die aber (oder habe ich etwas übersehen???) nirgends aufgerufen wird. Entsprechend sind die Objekte des Iterators nicht initialisiert und die stack-Variable ist null.

Noch ein paar andere Verbesserungsvorschläge:
In hasNext() rufst du count(Node) auf. Das geschieht dann in jedem Schleifendurchlauf, was bei großen Bäumen sehr ineffizient wäre. Wenn du davon ausgehst, dass sich der Baum während des Iterierens nicht ändert, wäre es hier sinnvoller, die Anzahl einmal zu berechnen und als Integer zu speichern.

Außerdem implementierst du einen Baum. Wie wäre es da mit dem Design Pattern Kompositum mit einem Abschluss-Knoten? Einfach mal googeln, sofern du dich nicht bewusst dagegen entschieden hast😉

 

[Butterbrot]

Also erst einmal danke für die umfangreiche und informierende Antwort. Tut mir leid, dass ich erst jetzt antworte, ich hatte gestern leider noch etwas anderes zu tun. Also ich hab den Code jetzt umgeändert in:

@Override
    public Iterator<E> iterator() {

        return new Iterator<E>(){
            Node start;
            Node current;
            int counter;
            Stack<Node> stack;
            int border = count(root);

            public void iterator() {

                start = new Node(null);
                counter++;
                stack = new Stack<Node>();
                current = start;
                stack.empty();
            }

            @Override
            public boolean hasNext() {
                if(counter == border) return false;
                else return true;
            }

            @Override
            public E next() {
                stack.push(current);
                counter++;
                if(current.left.value != null) return current.left.value;
                else if(current.right.value != null) return current.right.value;
                else if(current.left == null && current.right == null){
                    while(current.right != null){
                        current = current.parent;
                    }
                    //                    return current.value;
                }
                return current.value;
            }

        };
    }

Könntest du mir noch bitte einen Beispiel-Code senden, was du denn genau damit meinst, dass ich den Iterator aufrufen soll.

P.S.: Pattern Design Kompositum haben wir in den Vorlesungen nicht gelernt und müssen wir auch nicht anwenden 🙂

 

[Butterbrot]

Okay nein, passt schon danke. Ich habs mittlerweile selber hingekriegt. Falls später noch jemand auf diesen Forum-Beitrag stoßen sollte hier der Code:

@Override
    public Iterator<E> iterator() {

        return new Iterator<E>(){
            Node current;
            Stack<Node> stack;

            {   
                stack = new Stack<Node>();
                current = root;
                stack.add(root);
            }

            @Override
            public boolean hasNext() {
                if(stack.empty()) return false;
                else return true;
            }

            @Override
            public E next() {
                if(!hasNext()){
                    throw new NoSuchElementException();
                }
                Node n = stack.pop();
                if(n.left != null) stack.push(n.left);
                if(n.right != null) stack.push(n.right);

                return    n.value;           
            }

        };
    }