PHP-Scripte PHP-Tutorials PHP-Jobs und vieles mehr

PHP-Scripte PHP-Tutorials PHP-Jobs und vieles mehr (https://www.php-resource.de/forum/)
-   PHP Developer Forum (https://www.php-resource.de/forum/php-developer-forum/)
-   -   Binärbäume (https://www.php-resource.de/forum/php-developer-forum/79123-binaerbaeume.html)

schuetz10 11-12-2006 21:34

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 :D 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 :D), 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

penizillin 11-12-2006 21:45

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

zerni 12-12-2006 14:34

Bäume und Listen hab ich auch gemacht, aber schon in der 12. Klasse :)

könnte dir das ganze nur in Java anbieten

schuetz10 12-12-2006 18:32

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

zerni 12-12-2006 18:42

Liste der Anhänge anzeigen (Anzahl: 1)
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!

PHP-Desaster 12-12-2006 19:02

Liste der Anhänge anzeigen (Anzahl: 1)
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!


Alle Zeitangaben in WEZ +2. Es ist jetzt 18:33 Uhr.

Powered by vBulletin® Version 3.8.2 (Deutsch)
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.
Search Engine Friendly URLs by vBSEO 3.3.0
[c] ebiz-consult GmbH & Co. KG