Seite 1 von 1

6 Übung ----> (G 6.3 Darstellung von Baumen) unverständl

Verfasst: 11. Jul 2007 01:00
von oren78
Ich hab eine Frage zu der G 6.3 b iii) also: "Halbsequentielle Darstellung"

ich versuch krampfhaft nachzuvollziehen, weswegen
in der Tabelle an der Adresse: 1 Spalte: "rechter Sohn"
eine 5 steht...

Müsste es nicht richtig sein: C (bzw. 3) dort einzutragen??
Zumindest verstehe ich das so, wenn ich die Definition in
Skript: 7 (Bäume), Seite: 27 anschaue...

Hat sich in der Musterlösung ein kleiner Fehler eingeschlichen,
oder verstehe ich es einfach anders..??


Bitte um Aufklärung :-)

Verfasst: 11. Jul 2007 08:51
von mantra
Ich weiß nicht, ob die Lösung inzwischen geändert wurde, aber ich habe es mir mal eben angesehen und es sieht (in diesem Fall) richtig aus:
An Adresse 5 steht ein C.

Allerdings müsste da noch eine NULL-Zeile nach Adresse 2, denn B hat keinen linken Nachfolger.
Dadurch würden sich die folgenden Indizes natürlich verschieben.

Verfasst: 11. Jul 2007 11:05
von oren78
alles klar, hat sich erledigt...

hab übersehen das in der Halbsequenz. - Datstellung alles in Pre-Order gespeichert ist...seltsamerweise steht es auch NICHT in unseren Folien, dafür jedoch in die alten (Sommersemester 06) ;-)

egal...jedenfalls danke :-)

Verfasst: 8. Sep 2007 15:48
von Dutchie
hallo,

eine frage zur G 6.4 c.):

wie haben die da die erfolglose Suche bei den Bäumen gemacht?
ich zähle jeweils pro Baum nur 15 Knoten :?:

danke schon mal für die hilfe,

dutchie

Verfasst: 8. Sep 2007 20:15
von Dutchie
ok, hab die erfolglose Suche verstanden und es hat sich erledigt.
wer es wissen will,kann mich gerne nochmal fragen.

Verfasst: 12. Sep 2007 16:51
von banshee
Wäre cool, wenn du nochmal erklären könntest, wie man auf den Zähler kommt. Für den Nenner zählt man ja einfach alle Knoten + die imaginären Knoten an den Blättern mit. Und ich dachte selbiges macht man auch für den Zähler, also zb für einen Baum, der auf Stufe 2 vollständig ist:

1+2+2+3+3+3+3+4+4+4+4+4+4+4+4 für den Zähler. Stimmt aber nicht

Verfasst: 12. Sep 2007 19:41
von wach
Blaetter werden mit der Stufe des Knotens, an dem sie haengen gezaehlt. Weil man ja hier keinen Vergleich mehr durchfuehren muss.

Verfasst: 21. Sep 2007 00:17
von citta
Kann sein, dass die Frage im Repetitorium gefallen ist, ist mir dann wohl entgangen.

Bei der Halbsequentiellen Darstellung gibt es ja die Blatt-Indikatoren, die einem sagen, ob der nächste Eintrag tatsächlich ein linker Sohn ist, oder nicht. Schön und gut, aber was ist, wenn der Baum kein Suchbaum ist und bei einem inneren Knoten es keinen linken, aber einen rechten Sohn gibt. Dann ist das Blatt-flag false (wie in der Lösung zur entsprechenden Übungsaufgabe 6.3b), jedoch ist der nächste Eintrag ja nicht der Eintrag des linken Sohnes.

Wie müsste man das Problem jetzt lösen?
a) Blatt? durch "Kein linker Sohn?" ersetzen
b) null-Einträge nach so einem inneren Knoten machen und diese als Blätter markieren
c) "Geschickt" erkennen, dass das der Folgeeintrag kein linker Sohn ist durch die Rsohn-Einträge, die zuvor gekommen sind (wäre aber eher kompliziert)

Verfasst: 21. Sep 2007 02:40
von tgp
Die Frage ist sogar im Repetitoriumsthread gefallen ;)

Die Knoten sind in pre-order gespeichert, weshalb der linke Sohn direkt nach dem Vater kommen muss. Steht da aber der Eintrag, auf den unter "rechter Sohn" verwiesen wird, handelt es sich eben um den rechten Sohn. Also gibt es keinen linken und die Darstellung ist eindeutig.