Seite 1 von 1

Unklarheit im Javaübungsblatt

Verfasst: 7. Sep 2017 11:55
von Adrian1995
Hey Leute,

ich hab soeben mit den Übungsblatt angefangen und bin bei Aufgabe 1.1 auf die erste Unklarheit gestoßen.
Ist hier mit binärem Baum ein binärere Suchbaum gemeint? Was bedeutet ich könnte im iterativen Fall ein Comperator zur Hilfe ziehen um jeweils nur einen der beiden Teilbäume zu durchsuchen.

Oder unterliegt der Baum keiner Ordnung und ich muss mit traverse in jedem Fall den ganzen Baum durchsuchen.

Diese Frage bezieht sich damit auch darauf ob die anderen Bäume irgendeiner Ordnung unterliegen.

Außerdem noch die Frage ob der Gleichheitscheck auf Referenz- oder Objektgleicheit geschehen soll (also equals() oder ==) und wie es in der Klausur sein wird wenn nichts gesondert angegeben ist.

Vielen Dank im voraus.

Re: Unklarheit im Javaübungsblatt

Verfasst: 7. Sep 2017 11:59
von Adrian1995
Wäre folgendes z.b. eine zulässige Lösung für die Klausur ?

Code: Alles auswählen

public boolean find(TreeNodeB<T> wurzel, T element) {
     if (wurzel == null)
        return false;
     Stack<TreeNodeB<T>> stack = new Stack<TreeNodeB<T>>();
     stack.push(wurzel);

     while (!stack.isEmpty()) {
         TreeNodeB<T> aktElement = stack.pop();
         if (aktElement.key.equals(element))
             return true;
         if (aktElement.left != null)
            stack.push(aktElement.left);
         if (aktElement.right != null)
            stack.push(aktElement.right);
     }
return false;
}

Re: Unklarheit im Javaübungsblatt

Verfasst: 12. Sep 2017 10:48
von Dome2403
Leider bekommt man hier mal wieder keine Antwort...

Ich habe es auch mit einem Stack gelöst, jetzt ist aber die Frage ob man Stacks und ihre Aufrufe(pop(),push(),empty()) in der Klausur verwenden darf?

Weißt du da mehr?

Re: Unklarheit im Javaübungsblatt

Verfasst: 12. Sep 2017 11:47
von Hans123
Also da es in AuD ja auch um Datenstrukturen geht und ein Stack genau das ist, wäre es ja dumm, wenn es nicht zulässig wäre. Zumal es unnötig kompliziert wäre, einen Baum (wenn man ihn denn schon iterativ durchgehen muss) ohne Stack durchzugehen.

Zu deinem Code noch eine Anmerkung: Die Methode, die checkt, ob der Stack leer ist, heißt einfach nur empty().
(s. https://docs.oracle.com/javase/7/docs/a ... Stack.html)

Re: Unklarheit im Javaübungsblatt

Verfasst: 18. Sep 2017 21:23
von Anton Haubner
Ich weiß nicht ob diies inzwischen an anderer Stelle bereits geklärt wurde, aber Ich interessiere mich auch sehr für die Frage, in wie fern man bereits vorhandene Java Datenstrukturen in den Klausuraufgaben verwenden darf, wie beispielsweise Stack<E> um über Bäume zu iterieren (traverse).

Ich würde mich daher sehr über eine offizielle Stellungsnahme hier freuen.
Vielen Dank!

Re: Unklarheit im Javaübungsblatt

Verfasst: 19. Sep 2017 10:31
von Hans123
Um mal meine erste Aussage zu korrigieren: Ich empfehle euch, alle Aufgaben auch mal ohne zusätzliche Datenstruktur durchzugehen, da alles aus java.util in den beiden Altklausuren jeweils verboten war.

Re: Unklarheit im Javaübungsblatt

Verfasst: 19. Sep 2017 12:06
von Anton Haubner
Hmm.. traverse ohne Stack auszuführen ist allerdings auch nicht schön, es geht zwar, indem man beispielsweise den Eingabebaum temporär modifiziert, allerdings kann das doch auch nicht Sinn der Sache sein, wenn in der VL die Methode mit Stack vorgestellt wurde.

EDIT: Auf dem Java Übungsblatt steht sogar
Hinweis: Die Ihnen aus der Vorlesung bekannte Methode traverse für binäre Suchbäume ilustriert
das Muster für iterative Implementationen von Methoden, die den ganzen Baum durchlaufen sollen.
ich schätze mit "Die Ihnen aus der Vorlesung bekannte Methode traverse" ist dieser Algorithmus hier gemeint, der eben einen Stack verwendet.

Re: Unklarheit im Javaübungsblatt

Verfasst: 19. Sep 2017 12:33
von Dome2403
Schade, dass sich nicht mal ein offizieller dazu äußern kann, da diese Fragen offensichtlich von den studierenden nicht beantwortet werden kann. Aber wenn ich sehe, dass der letzte Post eines offiziellen im Thread Rund um die Klausur, welche in etwas mehr als einer Woche ist, vor mehr als 14 Tagen war, frage ich mich wozu man solch ein Forum überhaupt einführt. Ich persönlich habe 3 Threads eröffnet teilweise sogar mit Hinweisen auf evtl. Fehler auf dem Java Übungsblatt mit welchem man sich auf die Klausur vorbereiten soll und habe weder von Studierenden(was ich nicht verurteile) noch von offizieller Seite Rückmeldung bekommen.
Aber dieses Problem wurde schon sehr ausführlich geschildert, leider auch hier keine Reaktion eines offiziellen...(viewtopic.php?f=167&t=36412)

Daher ist dieses Forum in meinen Augen unnütz, was ich sehr bedauere, da ich persönlich 80km zur Uni pendle und daher ein Sprechstundenbesuch mit enormen Aufwand verbunden ist.

Re: Unklarheit im Javaübungsblatt

Verfasst: 19. Sep 2017 16:53
von Hans123
Anton Haubner hat geschrieben:
19. Sep 2017 12:06

EDIT: Auf dem Java Übungsblatt steht sogar
Hinweis: Die Ihnen aus der Vorlesung bekannte Methode traverse für binäre Suchbäume ilustriert
das Muster für iterative Implementationen von Methoden, die den ganzen Baum durchlaufen sollen.
ich schätze mit "Die Ihnen aus der Vorlesung bekannte Methode traverse" ist dieser Algorithmus hier gemeint, der eben einen Stack verwendet.
Joa, vermute mal dass es das bestätigen sollte. Alles andere wäre Irreführung, wenn sich dazu natürlich nicht mehr offiziell vorher geäußert wird. Das würde aber an ein Wunder grenzen und ist im Allgemeinen auszuschließen.

Re: Unklarheit im Javaübungsblatt

Verfasst: 22. Sep 2017 11:36
von Hans123
Ich bin ja mittlerweile dazu geneigt, alle unbeantworteten Beiträge hier zu melden, damit Herr Weihe vielleicht auch mal hier reinschaut. Theoretisch hätte man hier die letzten 10 Tage alles mögliche machen können, nur interessiert hätte es wohl keinen.

Re: Unklarheit im Javaübungsblatt

Verfasst: 23. Sep 2017 01:27
von nozyde
Also wenn man die Lösungsblätter der letzten Klausuren betrachtet sieht man, dass es Punktabzug gab, wenn man andere java.util Elemente verwendet hat. Daher eigentlich keine Queue und kein Stack.

Rekursiv ist das Traversieren über einen Binärbaum übrigens kein Hexenwerk (beachte, je nach Klausuraufgabe statt "==" Operator, den Comperator verwenden - außerdem ist der Code nicht elegant oder effizient, nur zweckmäßig):

Code: Alles auswählen

// 1.1.5.d binary tree recursive (unsorted) --------------------------------------------
public boolean findRec(TreeNode<T> root, T key) {
    if (root == null) {
        return false;
    }
    
    return findRecVal(root, key);
}

// recursive call
public boolean findRecVal(TreeNode<T> node, T key) {
    if (node.key == key) {
        return true;
    }
    
    if (node.left != null) {
        return findRecVal(node.left, key);
    }
    
    if (node.right != null) {
        return findRecVal(node.right, key);
    }

    return false;
}
//--------------------------------------------------------------------------------------
Geht man das Ganze iterativ an wird es schon schwerer, ist aber mit der Morris Traversierung, zumindest in "in-order" Reihenfolge, möglich (einfach mal YouTube anschmeißen).

Code: Alles auswählen

// 1.1.5.c binary tree iterative (unsorted = morris inorder traversal) -----------------
public boolean findIt (TreeNode<T> root, T key) {
    if (root == null) {
        return false;
    }
    
    TreeNode<T> cur = root;
    while (cur != null) {
        if (cur.key == key) {
            return true;
        }

        if (cur.left == null) {
            cur = cur.right;
        }

        if (cur.left != null) {
            TreeNode<T> pre = cur.left;
            
            while (pre.right != null && pre.right != cur) {
                pre = pre.right;
                
                if (pre.right == null) {
                    pre.right = cur;
                    cur = cur.left;
                }

                if (pre.right != null) {
                    pre.right = null;
                    cur = cur.right;
                }
            }
        }
    }

    return false;
}
// -------------------------------------------------------------------------------------
Ich gehe dennoch davon aus, dass wenn in der Klausur eine iterative Implementierung einer Traversierung eines unsortierten Baumes stattfinden sollte, in der Aufgabenstellung definiert wird, dass ein Stack verwendet werden darf / muss. Da jedoch letztes Jahr bereits eine rekursive Traversierung Aufgabe war, glaube ich nicht daran, dass dieses Jahr wieder traversiert werden soll (natürlich nur meine Vermutung).