8.1 Iterative Traversierung

AnnaW
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 29. Jul 2012 23:05

8.1 Iterative Traversierung

Beitrag von AnnaW »

Hallo,

auf dem Übungsblatt steht: "Traversieren Sie das gegebene Beispiel iterativ unter Verwendung von Binary search tree: traverse. Bearbeiten Sie dann das vorgegebene Beispiel...anhand Ihrer Iterationen..."

Verstehe ich das richtig, dass die Lösung nur eine sortierte Liste mit allen Einträgen aus dem Baum erwartet und eben einen leeren Stack, oder sollen wir tatsächlich jeden Schritt darstellen?

Viele Grüße

Anna

R_Egert
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 180
Registriert: 8. Sep 2009 23:27

Re: 8.1 Iterative Traversierung

Beitrag von R_Egert »

Naja es sind mehrere Fälle darzustellen und das sind eben Ausschnitte aus der Durchführung der Traversierung, also nicht das Endergebnis^^. Oder was meinen Sie genau?

Viele Grüße,

Rolf
Tutor:
  • Einführung in Trusted Systems WS11/12, WS12/13, WS13/14, WS14/15
  • GDI II SS11, SS12, SS13, SS14
  • Einführung in die Kryptographie WS14/15

AnnaW
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 29. Jul 2012 23:05

Re: 8.1 Iterative Traversierung

Beitrag von AnnaW »

In den Folien z.B. fangen wir an der Wurzel an und gehen jeden Knoten einzeln durch und es wird jeder Schritt in einem Bild dargestellt. Bis wir wieder am Knoten sind. Das wären geschätzt 50 Bildchen die man dann darstellen müsste. Ich kann mir nicht vorstellen, dass das der Sinn der Aufgabe ist. Deswegen die Frage, was mit "Traversieren Sie das gegebene Beispiel iterativ unter Verwendung von Binary search tree: traverse. Bearbeiten Sie DANN das vorgegebene Beispiel...anhand Ihrer Iterationen..." gemeint ist. Das mit den Iterationen ist klar. Aber was davor?

Viele Grüße

Anna

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: 8.1 Iterative Traversierung

Beitrag von JannikV »

Du musst beim Traversieren nicht jedes Bildchen malen, aber nützliche Dinge zeichnerisch unterstützen (ich weiß, das klingt nach ziemlich dämlichen Geschwafel xD).
Nützlich wäre es zum Beispiel wenn ein Stack dargestellt ist, an dem man sieht dass du Elemente draufgelegt und wieder runtergenommen hast, usw.

VG

AnnaW
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 29. Jul 2012 23:05

Re: 8.1 Iterative Traversierung

Beitrag von AnnaW »

Ok, alles klar. Das macht mehr Sinn, als stupide alle Bilder zu malen ^^ Danke schön :-)

robertH
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 29. Apr 2013 13:11

Re: 8.1 Iterative Traversierung

Beitrag von robertH »

Ich habe mich gerade gefragt wie genau wir uns in den Zeichnungen an das Wiki halten sollen.

Nach dem Durchlesen des Wikis würde ich einen Pointer elem zeichnen, der auf ein Stackelement zeigt und einen Pointer elem.node bzw. im Induction Step dann nur noch node (da node := elem.node), der auf einen
Baumknoten zeigt. In dem Video zeigt der elem-Pointer jedoch direkt auf einen Baumknoten... Wäre das so auch in Ordnung (weil man ja weiß wie es eigentlich korrekterweise gedacht ist) ?

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: 8.1 Iterative Traversierung

Beitrag von JannikV »

Wenn deine Zeichnung hilfreich ist um zu verstehen wie traversiert wird ist das in Ordnung. Es muss natürlich nicht alles 100 % gleich aussehen.

robertH
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 29. Apr 2013 13:11

Re: 8.1 Iterative Traversierung

Beitrag von robertH »

Danke für die schnelle Antwort.

Ich hätte noch eine weitere Frage zu Binary-Search-Tree: traverse. Müsste im Wiki bei der Invariante nicht auch so etwas stehen, wie "keys in L are in ascending order" oder ergibt sich das aus der Invariante Nummer 1 und 2 ?

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: 8.1 Iterative Traversierung

Beitrag von JannikV »

Ja, daraus und aus der Implementationsinvariante der Datenstruktur.

Hirsch
Erstie
Erstie
Beiträge: 14
Registriert: 28. Apr 2013 18:21

Re: 8.1 Iterative Traversierung

Beitrag von Hirsch »

Wie soll den der Fall 5.5 aus dem Wiki eintreten?

Nach 5.4 ist doch elem.seenChildren = 2.

Anderfalls würde das bedeuten, dass man elem.left vorher nicht besucht hätte, was aber Vorraussetzung ist um überhaupt zu Fall 5 zu gelangen.

robertH
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 29. Apr 2013 13:11

Re: 8.1 Iterative Traversierung

Beitrag von robertH »

Überlege dir mal wie es aussieht, wenn du von einem Knoten der selbst ein linker Kinderknoten ist, wie der 11, zurückgehst.

Hirsch
Erstie
Erstie
Beiträge: 14
Registriert: 28. Apr 2013 18:21

Re: 8.1 Iterative Traversierung

Beitrag von Hirsch »

Alles klar. Danke dir!

Antworten

Zurück zu „Archiv“