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

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

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

Beitrag 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 :-)

Benutzeravatar
mantra
Computerversteher
Computerversteher
Beiträge: 385
Registriert: 23. Okt 2005 23:56
Wohnort: Wiesbaden

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

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Beitrag 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 :-)

Dutchie
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 8. Feb 2005 09:41

Beitrag 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

Dutchie
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 8. Feb 2005 09:41

Beitrag von Dutchie »

ok, hab die erfolglose Suche verstanden und es hat sich erledigt.
wer es wissen will,kann mich gerne nochmal fragen.

banshee
Nerd
Nerd
Beiträge: 684
Registriert: 22. Okt 2006 18:46

Beitrag 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

wach
Computerversteher
Computerversteher
Beiträge: 323
Registriert: 25. Okt 2004 09:08

Beitrag von wach »

Blaetter werden mit der Stufe des Knotens, an dem sie haengen gezaehlt. Weil man ja hier keinen Vergleich mehr durchfuehren muss.

citta
Mausschubser
Mausschubser
Beiträge: 96
Registriert: 7. Nov 2006 21:52

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

tgp
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 268
Registriert: 15. Nov 2006 21:41

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

Antworten

Zurück zu „Archiv“