Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Binärbaum wiederherstellen
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> Binärbaum wiederherstellen
 
Autor Nachricht
Caidian
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 04.09.2008
Beiträge: 7

BeitragVerfasst am: 04 Sep 2008 - 10:47:52    Titel: Binärbaum wiederherstellen

Die Aufgabe:
Aufgabe 3 (Bin¨are Suchb¨aume II)

3.1a) Geben Sie falls m¨oglich einen Algorithmus an, der aus einer Preorder Ausgabe den eindeutigen bin¨aren Suchbaum
rekonstruiert und wenden Sie ihn anschließend auf folgende Preorder Ausgabe an.
13, 8, 5, 9, 19, 17, 24

3.1b) Geben Sie falls m¨oglich einen Algorithmus an, der aus einer Postorder Ausgabe den eindeutigen bin¨aren Suchbaum
rekonstruiert und wenden Sie ihn anschließend auf folgende Postorder Ausgabe an.
6, 9, 2, 16, 20, 23, 14

3.1c) Geben Sie falls m¨oglich einen Algorithmus an, der aus einer Inorder Ausgabe den eindeutigen bin¨aren Suchbaum
rekonstruiert und wenden Sie ihn anschließend auf folgende Inorder Ausgabe an.
3, 5, 7, 17, 20, 23, 42
Smutje
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 18.07.2008
Beiträge: 3004
Wohnort: Gießen

BeitragVerfasst am: 04 Sep 2008 - 10:54:27    Titel:

erspar dir doch in zukunft einfach die arbeit, die aufgabenstellungen deiner dozenten abzukopieren und verlink die pdfs einfach ganz, das wär doch was, oder?

... Rolling Eyes
Caidian
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 04.09.2008
Beiträge: 7

BeitragVerfasst am: 04 Sep 2008 - 11:42:19    Titel:

Und was fürn Vorteil bringt das? Ich meine Ich check die eine Aufgabe nicht ganz und hätte gerne Hilfe....
Annihilator
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 18.05.2007
Beiträge: 6394
Wohnort: (hier nicht mehr aktiv)

BeitragVerfasst am: 04 Sep 2008 - 12:47:08    Titel:

Für Preorder
Da fängt man ja immer mit dem übergeordneten Knoten an, also muss die erste Zahl, die da steht, der Wurzel-Knoten des Suchbaums sein, also 13. Alle Werte der Liste, die kleiner sind, gehören zum linken Teilbaum und alle die größer sind (oder auch gleich) zum rechten. Bei den beiden neuen Teillisten verfährst du genauso. Wenn eine ein- oder nullelementige Liste erreicht ist, dann tue nichts. Das kannst du schön rekursiv aufrufen und erhältst einen eindeutigen binären Suchbaum:

Code:

13
  8
    5
    9
  19
    17
    24


Müsstest das ganze vielleicht noch in Pseudo-Code pressen, aber ich denke, das bekommst du hin. Macht dir mal eigene Gedanken zu Post- und Inorder!
Smutje
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 18.07.2008
Beiträge: 3004
Wohnort: Gießen

BeitragVerfasst am: 04 Sep 2008 - 13:14:47    Titel:

Caidian hat folgendes geschrieben:
Und was fürn Vorteil bringt das? Ich meine Ich check die eine Aufgabe nicht ganz und hätte gerne Hilfe....


tjo, dann mach dir das nächste mal halt die mühe und schreib das dazu, wo du nicht weiterkommst und welche ideen du hast, sind hier ja schließlich keine hausaufgabenstelle hier...
Caidian
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 04.09.2008
Beiträge: 7

BeitragVerfasst am: 08 Sep 2008 - 13:57:12    Titel:

bei Post und Inorder hätte ich gesagt: das es nicht eindeutig ist, da sie beide bei den Blätter anfangen. Preorder hingegen fängt bei der Wurzel an.

Stimmt das?
Tolotos
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 20.01.2007
Beiträge: 307

BeitragVerfasst am: 08 Sep 2008 - 14:54:38    Titel:

Caidian hat folgendes geschrieben:
bei Post und Inorder hätte ich gesagt: das es nicht eindeutig ist, da sie beide bei den Blätter anfangen.
Stimmt das?

Nein!

Caidian hat folgendes geschrieben:
Preorder hingegen fängt bei der Wurzel an.
Stimmt das?

Ja!
Jockelx
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 24.06.2005
Beiträge: 3596

BeitragVerfasst am: 08 Sep 2008 - 15:15:59    Titel:

Annihilator hat folgendes geschrieben:
Das kannst du schön rekursiv aufrufen und erhältst einen eindeutigen binären Suchbaum:

Code:

13
  8
    5
    9
  19
    17
    24



Ist das so? Was spricht z.B. gegen den folgenden Baum?

Code:

           13
        /     \
      8        5
              /   \
            9      19
                  /  \
                 17   24
Annihilator
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 18.05.2007
Beiträge: 6394
Wohnort: (hier nicht mehr aktiv)

BeitragVerfasst am: 08 Sep 2008 - 16:02:08    Titel:

Die Tatsache, dass es sich dabei nicht um einen binären Suchbaum handelt, spricht sehr dagegen, da nämlich nach genau einem solchen gefragt wurde.
Jockelx
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 24.06.2005
Beiträge: 3596

BeitragVerfasst am: 08 Sep 2008 - 16:06:32    Titel:

Ah, okay, dann macht das mit dem 'eindeutig' Sinn.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> Binärbaum wiederherstellen
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum