Fachrat Informatik - Forum

Tag!

Ich vermute mal, dass man das nächste Element jeweils an der linkesten, möglichen Stelle anfügen muss, so dass es ein fast vollständiger BinBaum bleibt.

Aber ich habe auch eine Frage dazu: Kann ein Heap auch ein vollständiger Baum sein?


Gruss Jens

Quoted

Original von compost
Aber ich habe auch eine Frage dazu: Kann ein Heap auch ein vollständiger Baum sein?

Ich vermute schwer, dass mit fast vollständig auch vollständig eingeschlossen ist, da beim Anfügen von Elementen ja zwangsläufig ein vollständiger, binärer Baum erzeugt wird, bis zum nächsten (links angehängten) Element.

Weiterhin ist bei "heap fast vollständig" das erste Google Ergebnis Dieses, wobei vollständige, binäre Bäume (b und c) als Heap auftauchen.

@Diktator
Wie compost sagte, muss ein fast vollständiger, binärer Baum gewährleistet sein, also dürfen nur rechte Elemente auf unterster Ebene fehlen, man hängt also von links nach rechts an, hat man einen vollständigen Baum, fängt man eine neue Ebene an, wiederum links.

Bei Aufgabe 2 ist mir schon die Aufgabenstellung unverständlich.

Was ist in a) mit rekonstruieren gemeint? Was ist zu erzeugen?
Es gäbe mehrere Möglichkeiten:

1. die sequentielle Darstellung mit öffnenden Klammern als String
   
2. ein binärer Baum als Zeigerstruktur im Speicher
   
3. eine grafische Ausgabe
   [/list=1]
   
   Aus der Aufgabenstellung geht m.E. nichts eindeutig hervor.
   
   In Teil b) verwirrt mich, dass k offenbar auch von n abhängen muss. Weiterhin stellt sich mir die Frage, wieviel Bit man braucht, um eine Klammer zu kodieren. Theoretisch würde ein Bit ausreichen (Klammer ja/nein), doch das würde ja u.U. zu Uneindeutigkeiten führen.
   Außerdem: Wenn man ein zusätzliches Bit für "Klammer ja/nein" einplant, müsste es jedem Knoten zugeordnet werden, was bedeutete, dass n zusätzliche Bits gebraucht werden.
   Doch ich weiß nicht, ob ich damit richtig liege und ob ich die Aufgabenstellung überhaupt verstanden habe.

Quoted

von migu Was ist in a) mit rekonstruieren gemeint? Was ist zu erzeugen?

ich denke, es ist mir ziemlicher sicherheit ein baum als zeigerstruktur im speicher gemeint. im sinne des adt TREE aus dem skript.


mfg

cowhen

Quoted

Original von migu
Was ist in a) mit rekonstruieren gemeint? Was ist zu erzeugen?
Es gäbe mehrere Möglichkeiten:

1. die sequentielle Darstellung mit öffnenden Klammern als String
   
2. ein binärer Baum als Zeigerstruktur im Speicher
   
3. eine grafische Ausgabe
   [/list=1]

[list=1]Ich tippe mal stark auf Alternative 2 (wobei allerdings kein binärer, sondern ein geordneter Baum gemeint ist -> das steht auch so im Aufgabentext). Die beiden anderen Möglichkeiten machen IMHO nicht allzuviel Sinn.

Quoted

Aus der Aufgabenstellung geht m.E. nichts eindeutig hervor.

So unverständlich finde ich die gar nicht.

Quoted

In Teil b) verwirrt mich, dass k offenbar auch von n abhängen muss.

k hängt nicht von n ab. In allen Knoten könnte ja z. B. auch der gleiche Wert abgelegt sein. Dann bräuchte man nur ein Symbol und somit wäre k beliebig.

Quoted

Weiterhin stellt sich mir die Frage, wieviel Bit man braucht, um eine Klammer zu kodieren. Theoretisch würde ein Bit ausreichen (Klammer ja/nein), doch das würde ja u.U. zu Uneindeutigkeiten führen.

Genau diese Uneindeutigkeiten gilt es durch geschickte Codierung zu vermeiden.

Quoted

Außerdem: Wenn man ein zusätzliches Bit für "Klammer ja/nein" einplant, müsste es jedem Knoten zugeordnet werden, was bedeutete, dass n zusätzliche Bits gebraucht werden.

Vergiß aber nicht, daß auf einen Knoten mehrere Klammern folgen können. Ein einzelnes Bit wäre dann nicht eindeutig.[/list]

Quoted

Original von Joachim

Quoted

Original von migu
Was ist in a) mit rekonstruieren gemeint? Was ist zu erzeugen?
Es gäbe mehrere Möglichkeiten:

1. die sequentielle Darstellung mit öffnenden Klammern als String
   
2. ein binärer Baum als Zeigerstruktur im Speicher
   
3. eine grafische Ausgabe
   [/list=1]

[list=1]Ich tippe mal stark auf Alternative 2 (wobei allerdings kein binärer, sondern ein geordneter Baum gemeint ist -> das steht auch so im Aufgabentext).
[/list]

[list=1]

So war das gedacht.

Grüße,

Niklas[/list]