Unklarheit im Javaübungsblatt

Adrian1995
Neuling
Neuling
Beiträge: 4
Registriert: 7. Sep 2017 11:45

Unklarheit im Javaübungsblatt

Beitrag von Adrian1995 » 7. Sep 2017 11:55

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.
Zuletzt geändert von Adrian1995 am 7. Sep 2017 15:34, insgesamt 3-mal geändert.

Adrian1995
Neuling
Neuling
Beiträge: 4
Registriert: 7. Sep 2017 11:45

Re: Unklarheit im Javaübungsblatt

Beitrag von Adrian1995 » 7. Sep 2017 11:59

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;
}

Dome2403
Nichts ist wie es scheint
Beiträge: 23
Registriert: 6. Mai 2017 13:24

Re: Unklarheit im Javaübungsblatt

Beitrag von Dome2403 » 12. Sep 2017 10:48

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?

Hans123
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 12. Jun 2017 13:23

Re: Unklarheit im Javaübungsblatt

Beitrag von Hans123 » 12. Sep 2017 11:47

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)

Anton Haubner
Neuling
Neuling
Beiträge: 5
Registriert: 21. Apr 2017 09:35

Re: Unklarheit im Javaübungsblatt

Beitrag von Anton Haubner » 18. Sep 2017 21:23

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!

Hans123
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 12. Jun 2017 13:23

Re: Unklarheit im Javaübungsblatt

Beitrag von Hans123 » 19. Sep 2017 10:31

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.

Anton Haubner
Neuling
Neuling
Beiträge: 5
Registriert: 21. Apr 2017 09:35

Re: Unklarheit im Javaübungsblatt

Beitrag von Anton Haubner » 19. Sep 2017 12:06

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.
Zuletzt geändert von Anton Haubner am 19. Sep 2017 13:41, insgesamt 1-mal geändert.

Dome2403
Nichts ist wie es scheint
Beiträge: 23
Registriert: 6. Mai 2017 13:24

Re: Unklarheit im Javaübungsblatt

Beitrag von Dome2403 » 19. Sep 2017 12:33

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.

Hans123
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 12. Jun 2017 13:23

Re: Unklarheit im Javaübungsblatt

Beitrag von Hans123 » 19. Sep 2017 16:53

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.

Hans123
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 12. Jun 2017 13:23

Re: Unklarheit im Javaübungsblatt

Beitrag von Hans123 » 22. Sep 2017 11:36

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.

nozyde
Erstie
Erstie
Beiträge: 20
Registriert: 7. Jun 2017 21:22

Re: Unklarheit im Javaübungsblatt

Beitrag von nozyde » 23. Sep 2017 01:27

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).

Antworten

Zurück zu „Archiv“