Baum aus Postorder/Inorder < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:55 Do 11.09.2008 | | Autor: | Boki87 |
| Aufgabe | Es geht um folgende Frage:
[Dateianhang nicht öffentlich]
|
Meiner Meinung nach ist der Baum nicht möglich...aber das kann eigentlich auch nicht sein...
Aus dem Postorder weiß man das die 10 in der Wurzel sein muss...
Aus Inorder weiß man die 5 muss ganz unter links sein.
Und aus Postorder und Inorder weiß man das 5,4,8,11,7 links von der 10 sein müssen und 9,3,6,2,1 rechts von der 10 sein müssen. Ich komme so weit:
8
/ [mm] \
[/mm]
4 11
/
5
Jetzt stimmt für die Inorder...aber nicht für die Postorder...aber ich weiß nicht wie ich das unter einen Hut bringe...entweder stimmt bei mir Inorder oder Postorder...aber nie beides. Kann mir jemand helfen???
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
| |
|
Hallo Boki87!
> Es geht um folgende Frage:
> [Dateianhang nicht öffentlich]
>
>
>
> Meiner Meinung nach ist der Baum nicht möglich...aber das
> kann eigentlich auch nicht sein...
>
> Aus dem Postorder weiß man das die 10 in der Wurzel sein
> muss...
> Aus Inorder weiß man die 5 muss ganz unter links sein.
> Und aus Postorder und Inorder weiß man das 5,4,8,11,7 links
> von der 10 sein müssen und 9,3,6,2,1 rechts von der 10 sein
> müssen. Ich komme so weit:
>
>
> 8
> / [mm]\[/mm]
> 4 11
> /
> 5
>
> Jetzt stimmt für die Inorder...aber nicht für die
> Postorder...aber ich weiß nicht wie ich das unter einen Hut
> bringe...entweder stimmt bei mir Inorder oder
> Postorder...aber nie beides. Kann mir jemand helfen???
Zugegeben: ich fand die Aufgabe schwieriger als ich dachte, habe so etwas aber noch nie gemacht. Hab' mal einfach drauf los rumprobiert, aber deine Überlegungen scheinen zu stimmen. Ich komme auf folgenden Baum:
Die Wurzel 10 hat zwei Kinder, nämlich (von links nach rechts) die 8 und die 6. Die 8 wiederum hat die Kinder 4 und 7, diese haben jeweils nur ein linkes Kind, die 4 hat die 5 als Kind und die 7 die 11. Die 6, also rechts von der 10, hat die Kinder 9 und 2, die beide nur ein rechtes Kind haben, nämlich die 9 hat die 3 und die 2 hat die 1.
Ich glaube, dies hier zu "zeichnen" ginge nicht gut, vllt kannst du's dir aber auf Papier zeichnen und sagen, ob du damit einverstanden bist.  Kann mich ja auch verguckt haben...
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:05 Fr 12.09.2008 | | Autor: | bazzzty |
> Es geht um folgende Frage:
> [Dateianhang nicht öffentlich]
> Aus dem Postorder weiß man das die 10 in der Wurzel sein
> muss...
Und damit hast Du die Aufgabe eigentlich schon gelöst. Leider hast Du es nicht gemerkt ;)
Wenn Du aus der Postorder-Numerierung ablesen kannst, daß die 10 die Wurzel ist, dann kannst Du aus der Inorder-Numerierung ablesen, welche Knoten im linken und rechten Teilbaum liegen. Sogar noch mehr: Du kennst die Post- und Inorder-Numerierungen der Teilbäume:
links: Inorder 5 4 8 11 7, Postorder 5 4 11 7 8
rechts: Inorder 9 3 6 2 1, Postorder 3 9 1 2 6
Und jetzt geht es genau so weiter: Wurzel des linken Teilbaumes ist die 8, wegen der Postorder, die Teilbäume sind 5 4 und 11 7 (sowohl in In- als auch in Postorder).
Klar, wie es weitergeht?
(An dieser Vorgehensweise kann man übrigens super erkennen, warum In- und Post/Preorder Binärbäume eindeutig beschreiben.)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:35 Fr 12.09.2008 | | Autor: | Boki87 |
Ahh super...vielen Dank.
Ich hätte noch eine weiter Frage, ist es möglich einen eindeutigen Baum nur aus Preorder und Postorder zu erstellen...also meiner Meinung geht ein kleiner Baum, aber ich bin mir nicht sicher?
|
|
|
| |
|
Hallo Boki87!
> Ahh super...vielen Dank.
> Ich hätte noch eine weiter Frage, ist es möglich einen
> eindeutigen Baum nur aus Preorder und Postorder zu
> erstellen...also meiner Meinung geht ein kleiner Baum, aber
> ich bin mir nicht sicher?
Wenn ich mich nicht irre, stand in deiner Aufgabenstellung, dass es keinen eindeutigen Baum gibt, wenn sowohl Pre- als auch Postorder bekannt sind. Demnach kann es keinen eindeutigen geben, wenn nur eines von beiden bekannt ist, oder? 
Viele Grüße
Bastiane
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:44 Fr 12.09.2008 | | Autor: | Boki87 |
Ja das dachte ich bisher auch, aber anscheinend geht das bei manchen Bäumen...ich bin nämlich in einer anderen Prüfung auf folgende Aufgabe gestoßen:
[Dateianhang nicht öffentlich]
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:49 Fr 12.09.2008 | | Autor: | Bastiane |
Hallo Boki87!
> Ja das dachte ich bisher auch, aber anscheinend geht das
> bei manchen Bäumen...ich bin nämlich in einer anderen
> Prüfung auf folgende Aufgabe gestoßen:
>
> [Dateianhang nicht öffentlich]
Ich könnte es zwar nicht begründen, aber vllt geht das bei vollständigen Bäumen? Oder bei Bäumen, die nur linke oder nur rechte Kinder haben?
Viele Grüße
Bastiane
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:23 Sa 13.09.2008 | | Autor: | Boki87 |
Also wenn es nur rechte oder linke Kinder hat kann nicht sein, ich habe folgendes Gegenbeispiel:
4
/
3
/
2
/
1
Preorder: 4,3,2,1
Postorder: 1,2,3,4
Aus dieser Preorder und Postorder lässt sich auch folgender Baum bilden(es muss ja nicht umbedingt ein Suchbaum sein):
4
/
3
/
2
[mm] \backslash
[/mm]
1
Was meinst du mit einem vollstädnigem Baum, dass jeder Knoten 2 Kinder hat?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:51 Sa 13.09.2008 | | Autor: | Bastiane |
Hallo Boki87!
> Also wenn es nur rechte oder linke Kinder hat kann nicht
> sein, ich habe folgendes Gegenbeispiel:
>
> 4
> /
> 3
> /
> 2
> /
> 1
>
> Preorder: 4,3,2,1
> Postorder: 1,2,3,4
>
> Aus dieser Preorder und Postorder lässt sich auch folgender
> Baum bilden(es muss ja nicht umbedingt ein Suchbaum sein):
>
> 4
> /
> 3
> /
> 2
> [mm]\backslash[/mm]
> 1
Ja, da hast du wohl Recht.
> Was meinst du mit einem vollstädnigem Baum, dass jeder
> Knoten 2 Kinder hat?
Genau, meines Wissens ist die gängige Bezeichnung dafür vollständiger Baum. Aber wahrscheinlich hast du da auch direkt ein Gegenbeispiel zu? Hab' mir da ehrlich gesagt keine weiteren Gedanken zu gemacht. Aber irgendein simples Prinzip muss es da ja wohl geben, so wie die Aufgabe gestellt ist...
Viele Grüße
Bastiane
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:42 Sa 13.09.2008 | | Autor: | Boki87 |
Hallo
des mit dem vollständigem Baum könnte stimmen, jedenfalls finde ich auf Anhieb kein Gegenbeispiel :)
Danke schön
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:27 Mo 15.09.2008 | | Autor: | bazzzty |
Vielleicht diese zwei Tipps:
(a) Eindeutig können nur vollständige Bäume sein, denn wenn ein Knoten nur einen Nachfolger hat, dann läßt sich weder in Prä- noch in Postorder sagen, ob der links oder rechts hängt.
(b) Malt euch doch mal einen vollständigen Baum der Höhe 3 auf und notiert die beiden Numerierungen. Ihr erkennt die Wurzel? Woran? Was kann man über den Knoten sagen, der in der Präorder-Numerierung direkt nach der Wurzel kommt? Was über den Knoten, der in der Postorder-Numerierung direkt vor der Wurzel?
Wird das Prinzip klar?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:28 Mo 15.09.2008 | | Autor: | bazzzty |
Nein, das geht mit beliebig großen Bäumen. Die Tipps dazu habe ich im anderen Post geschrieben.
|
|
|
|
