Tweet
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:
Das hätte dann folgende "Datenstruktur":
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
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
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
Kommentar