Fachrat Informatik - Forum

hallöle.

hab mal ne frage zu den orderdurchläufen. wir sollen ja feststellen ob es binäre bäume gibt die gleich bei pre- und inorder durchlaufen werden. sind denn "leere" blätter zugelassen? also sowas wie
1
x 2

x= leer

in der vorlesung haben wir die leeren felder nicht behandelt aber im grunde ist ja jeder external knoten ein internal mit 2 x da drunter:
a
x x

also für alle die es interessiert: Ein Elter muss keine 2 Kinder haben.

aufgabe 1b)
Aus welchen Kombinationen von Pre-, In-, und Postorderdurchläufen kann die Struktur eines beliebigen binären Baums wiederhergestellt werden? Geben Sie für eine mögliche Kombination einen Algorithmus im Pseudocode an. Eingabeparameter seien die entsprechenden Durchläufe in Form von Vektoren.

frage zu 1b)
wie habe ich mir das vorzustellen? ich bekomme einen vektor ABCD und soll daraus wieder den baum herstellen? aber dazu müsste ich ja wissen ob es postorder, preorder oder inorder durchlauf war....?

unklare aufgabe, oder weiss jemand was man hier machen soll?

tut mir echt leid aber damit kann ich nix anfangen und so wie ich das sehe bin ich da ja nicht der einzige. aber aufgabe 2 macht einem da auch nicht gerade mut...da weiss ich auch nicht recht weiter. bin ja gespannt ob mehr als 5% diese aufgaben lösen können.

bei aufgabe 1a) musst du dir genau anschauen wie die ganzen durchläufe aussehen. am besten machst du dir nen beispiel und schreibst dir die 3 durchläufe auf. dann schaust du unter welchen bedingungen sich die durchäufe gleichen. so solltest du zu dem ergebnis kommen dass bei man vielleicht nur kinder in eine richtung haben kann. also rechts oder links. ich hoffe das hilft dir noch!