Binärbäume

Einklappen
X
 
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • Binärbäume

    Guten Abend!


    Ich habe ein imo großes Problem. Und zwar müssen wir bei unserem Informatik Lehrer jedes Semester ein Semesterprojekt erstellen, welches dann eben doch einen Großteil der Note ausmacht.

    Und wie's der Himmel, bzw. ich so will, hab ich mir das Thema Binärbäume ausgesucht (es wurden einige Themen von ihm Vorgeschlagen, und dass war dann imo das interressanteste )

    Naja, ich beschäftige mich jetzt schon seit einigen Tagen mit dem Thema, aber ich scheitere daran, den Baum "geordnet" bzw. sortiert ausgegeben.

    Zur "Datenorganisation":

    Ich habe die einzelnen Einträge des Baums in einer Textdatei gespeichert, welche ich einlese, und mir als Array organisiere.

    Jeder Knoten hat folgende Werte:

    Id, also (Knoten) Nummer;
    Inhalt, in meinem Fall ein Name;
    Vor, also der "Vaterknoten";
    Li, also das linke Kind vom Knoten (wenn keiner Vorhanden ist, ist der Wert 0)
    Re, das Rechte Kind vom Knoten (wie schon bei Li gilt, wenn keiner Vorhanden ist, Wert 0)

    Ein Beispielbaum:

    Code:
    Karl
    |
    |-Otto
    |   |
    |   |-Paul
    |   |  |
    |   |  |-Zap
    |   |
    |   |-Mona
    |
    |-Fritz
        |
        |-Berta
            |
            |-Eva
            |
            |-Adam
    Das hätte dann folgende "Datenstruktur":

    Code:
     
    ---------------------------------
    | ID  | Inhalt  | Vor | Li | Re |
    ---------------------------------
    | 1     Karl       0    2    3  |
    | 2     Fritz      1    4    0  |
    | 3     Otto       1    5    6  |
    | 4     Berta      2    8    7  |
    | 5     Mona       3    0    0  |
    | 6     Paul       3    0    10 |
    | 7     Eva        4    0    0  |
    | 8     Adam       4    0    0  |
    | 9     Zap        6    0    0  |
    ---------------------------------

    Was ich schon habe, ich finde das erste Element (vom Alphabetischen her) heraus (dieses befindet sich im Baum ja ganz links) und ich finde das letzte Element heraus, dieses befindet sich folglich ganz rechts.

    Was ich jetzt noch brauche, und mein derzeitiges Problem ist, ist die Ausgabe. Dabei muss noch nichtmal die Einrückung wie beim Beispielbaum gezeigt drinnen sein (ich hätte natürlich nichts dagegen ), mein Ziel ist es einfach mal eine Liste dazustehen haben, die den ganzen Baum (mehr oder weniger) geordnet enthält.

    Über weitere Dinge hab ich bis jetzt noch nicht nachgedacht (hinzufügen eines Eintrags, etc.), wobei ich auch für Erklärungen dankbar wäre, wie man dass am besten löst.

    Ich hab da irgendwie keinen Plan, wie ich das realisieren soll. Hat da einer einen Vorschlag für mich, oder einen Link, wo das ganze möglichst einfach erklärt ist, am Besten auch noch mit PHP Codeschnipsel?

    Ich bin für jede konstruktiven Beitrag dankbar, und würde mich über Antworten freuen!

    mfg
    schuetz10
    Zuletzt geändert von schuetz10; 11.12.2006, 21:40.

  • #2
    http://en.wikipedia.org/wiki/Tree_traversal erklärt, was ein "inorder" durchlauf ist. dann weißt du, wonach du googlen kannst.

    Kommentar


    • #3
      Bäume und Listen hab ich auch gemacht, aber schon in der 12. Klasse

      könnte dir das ganze nur in Java anbieten
      Killerspiele sollten in der Größenordnung von Kinder********************grafie eingeordnet werden.(G. Beckstein)
      - ...und solche Behauptungen in "falsches Resourcenmanagement"

      Kommentar


      • #4
        Ich bin für alles dankbar


        btw. @ penizillin:

        Jup, also die drei verschiedenen Durchlaufarten (also in-,pre- und postorder hab ich schon gefunden), allerdings helfen die mir irgendwie auch nicht weiter

        naja, ich werde weiter herumprobieren, und wenn ich jemals zu einem anderen Problem komme, werde ich mich wohl wieder melden


        mfg

        Kommentar


        • #5
          ich sehe gerade, dass im Baum doch nix drin ist, an methoden zum ausgeben etc nur ne allgemein, wo du dann aber den knoten angeben musst!

          wäre dann Stichwort Rekursion! du musst den Baum so lange durchgehen mit ein Knoten weder einen linken noch einen rechten Nachfolger hat!

          Ansonsten: http://www.dvs1.informatik.tu-darmst...-teil5-by6.pdf


          ach die Datei ist ein NetBeans Project!
          Angehängte Dateien
          Zuletzt geändert von zerni; 12.12.2006, 18:45.
          Killerspiele sollten in der Größenordnung von Kinder********************grafie eingeordnet werden.(G. Beckstein)
          - ...und solche Behauptungen in "falsches Resourcenmanagement"

          Kommentar


          • #6
            ich habe einmal aus meinem Skript zu Algorithmen die Breiten-/Tiefensuche rausgesucht, die keine Rekursion erfordert! Kannst du dir ja einmal ansehen!!
            >> Vorsicht! Der Pseudocode enthält sowohl Breite als auch Tiefe, musst du dich also einmal reinwuseln!
            Hoffe, du kannst was mit anfangen! Ich habe das schonmal gemacht, ist ziemlich simpel den Pseudocode umzuwandeln in richtige Syntax!
            Angehängte Dateien

            Kommentar

            Lädt...
            X