Iterator erneut!

[ocsme]

Guten Tag,

Aufgabenstellung (Menge als Suchbaum):
Implementieren sie für die Klasse TreeSet die Methode iterator(). Der Iteraltor soll die Elemente der Menge iterativ in aufsteigender Ordnung durchlaufen.

public class TreeSet<T extends Comparable<T>> implements Set<T> {
    
    protected class Node {
        T value;
        Node left, right;
        Node(T v) {
            value=v;
        }
    }
    
    protected Node root = null;
    
    @Override
    public Iterator<T> iterator() {
        
    }

Außerdem sei eine Implementierung der Klasse Stack<T> gegeben.

class Stack<T> extends Vector<T> {
    boolean empty() { ... }
    T pop () { ... }
    T push(T itme) { ... }
    int size() { ... }
}

Eigentlich dachte ich, das ich sowas verstanden habe doch leider nicht wirklich.
Mein Code würde so aussehen:

public class TreeSet<T extends Comparable<T>> implements Set<T> {
    
    protected class Node {
        T value;
        Node left, right;
        Node(T v) {
            value=v;
        }
    }
    
    protected Node root = null;
    
    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            Node current = root;
            Stack<T> s = new Stack<>();
            
            public boolean hasNext() {
                if(current.left != null || current.right != null) {
                    s = inorder(current,s);
                    return true;
                }
                else return false;
            }
            
            public T next() {
                if(!s.isEmpty())       
                    return s.pop();
                else return null;
            }
            
            private Stack<T> inorder(Node root, Stack<T> s) {
                if(root!=null) {
                    inorder(root.left,s);
                    s.push(root.value);
                    inorder(root.right,s);
                }
                return s;
            }
        };
    }

Das Problem ist nur wenn in einer while Schleife hasNext() immer wieder neu aufgerufen wird hängt er bei der größten Zahl in einer endloßschleife Fest!

Doch leider ist mir nichts besseres eingefallen.
Ich wollte erst im Suchbaum ganz nach rechts dann die Zeiger ändern und dann weiter machen. Doch auch das habe ich nicht hin bekommen da ich ja ein T zurück geben muss bei Next() hatte ich das Problem current zu verändern so das ganz rechts das Element weg fällt.

Kann mir dabei jemand weiter Helfen?

LG

 

[ocsme]

Vielleicht ist das hier ja auch zulässig?
Ich hab einfach eine neue Klasse erstellt die mir den Stack im Konstruktor füllt und könnte dann mit dem Stack arbeiten.
Darf man so etwas tun?

@Override
    public Iterator<T> iterator() {
        return new SetIterator(root);
    }
    
    class SetIterator implements Iterator<T> {
        Stack<T> s = new Stack<T>();
        SetIterator(Node root) {
            s = inorder(root,s);
        }
        @Override
        public boolean hasNext() {
            return s.isEmpty()?false:true;
        }

        @Override
        public T next() {
            if(hasNext())
                return s.pop();
            return null;
        }
        
        private Stack<T> inorder(Node root, Stack<T> s) {
            if(root!=null) {
                inorder(root.left,s);
                s.push(root.value);
                inorder(root.right,s);
            }
            return s;
        }
        
    }

 

[mihe7]

Darf man so etwas tun?

So lange remove() nicht gefordert ist, sehe ich nichts, was gegen das Iterator-Interface verstoßen würde.

Darfst Du successor(n) verwenden?

 

[ocsme]

Hallo,
leider weiß ich nicht was successor(n) sind
Hab es gerade mal gegooglet und auf die schnelle bin ich nicht so wirklich schlau draus geworden.

Das Problem bei mir wenn ich es komplett Iterativ versuche eben das return T. Ich sitze irgendwann ganz weit unten im Baum mit meinem Zeiger und komme nicht wieder hoch.
Das ganze war mir dann zu doof, da in der Aufgabe ein Stack mit Implementiert war dachte ich so sollte es auch gehen

Vielleicht lässt sich mein Problem ja mit successor(n) beseitigen. Werde mir das mal anschauen.

Danke @mihe7

 

[mihe7]

eider weiß ich nicht was successor(n) sind

Deine Methode successor() aus dem anderen Thread

 

[ocsme]

Die gegebene Klasse TreeSet darf nicht verändert werden.

Hab diesen Link gefunden

Inorder Successor in Binary Search Tree - GeeksforGeeks

A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

www.geeksforgeeks.org

Doch dort wird der Parent in der Node gespeichert. Das dürfte man eben nicht. Bestimmt wurde deswegen auch der Stack mit angegeben. Denn ich hab mir den Kopf zerbrochen es ohne eine andere Datenstruktur zu machen und kam auf kein Ergebnis (was ja nichts heißt ).

In dem anderen Thread würde ja nur das speichern des Vater Vater Knoten fehlen dann sollte es gehen hoffe ich

LG

 

[mihe7]

Nehmen wir einmal an, path wäre der Pfad zum Knoten mit dem Nachfolger. Dann wäre der darauf folgende In-Order-Nachfolger das linke Blatt des rechten Teilbaums - sofern ein solcher existiert.

Falls kein rechter Teilbaum existiert, kann man den Pfad so lange zurückgehen, bis man auf einen Knoten trifft, der die Wurzel eines linken Teilbaums darstellt. Sofern ein solcher existiert, ist dessen Elternknoten der Nachfolger.

Achtung: nicht getestet (nur hier reingeschrieben)

class TreeIterator implements Iterator<T> {
    Deque<Node> path = new ArrayDeque<>();

    public TreeIterator() {
        if (root != null) {
            appendPathToFirstLeaf(root);
        }
    }

    public boolean hasNext() { return !path.isEmpty(); }

    public T next() {
        if (!hasNext()) { throw new NoSuchElementException(); }
        Node current = path.peekLast();
        T result = current.value;
        if (current.right != null) {
            appendPathToFirstLeaf(current.right);
        } else {
            do {
                current = path.removeLast();
            } while (!path.isEmpty() && path.peekLast().left != current);
        }
        return result;
    }

    private void appendPathToFirstLeaf(Node root) {
        Node current = root;
        while (current != null) {
            path.push(current);
            current = current.left;
        }
    }
}

 

[ocsme]

Ich schaue mir das morgen genauer an
Heute nach 10 Stunden rum probiere rei mag ich nicht mehr

LG

 

[ocsme]

Entschuldigung ich kam heute erst dazu mir deine Lösung an zu schauen

Finde deine Lösung schöner als die meine
Ich kannte auch das Prinzip der Deque bis dorthin nicht (ja wir müssen noch viel Lernen )

Nochmals Danke @mihe7