php-resource



Zurück   PHP-Scripte PHP-Tutorials PHP-Jobs und vieles mehr > Entwicklung > PHP Developer Forum
 

Login

 
eingeloggt bleiben
star Jetzt registrieren   star Passwort vergessen
 

 

 


PHP Developer Forum Hier habt ihr die Möglichkeit, eure Skriptprobleme mit anderen Anwendern zu diskutieren. Seid so fair und beantwortet auch Fragen von anderen Anwendern. Dieses Forum ist sowohl für ANFÄNGER als auch für PHP-Profis! Fragen zu Laravel, YII oder anderen PHP-Frameworks.

Antwort
 
LinkBack Themen-Optionen Thema bewerten
  #1 (permalink)  
Alt 11-12-2006, 21:34
schuetz10
 Newbie
Links : Onlinestatus : schuetz10 ist offline
Registriert seit: Dec 2006
Beiträge: 2
schuetz10 ist zur Zeit noch ein unbeschriebenes Blatt
schuetz10 eine Nachricht über ICQ schicken
Unhappy 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

Geändert von schuetz10 (11-12-2006 um 21:40 Uhr)
Mit Zitat antworten
  #2 (permalink)  
Alt 11-12-2006, 21:45
penizillin
 PHP Guru
Links : Onlinestatus : penizillin ist offline
Registriert seit: Feb 2004
Beiträge: 10.166
penizillin ist zur Zeit noch ein unbeschriebenes Blatt
Standard

http://en.wikipedia.org/wiki/Tree_traversal erklärt, was ein "inorder" durchlauf ist. dann weißt du, wonach du googlen kannst.
Mit Zitat antworten
  #3 (permalink)  
Alt 12-12-2006, 14:34
zerni
 Member
Links : Onlinestatus : zerni ist offline
Registriert seit: Oct 2006
Beiträge: 268
zerni ist zur Zeit noch ein unbeschriebenes Blatt
Standard

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

könnte dir das ganze nur in Java anbieten
Mit Zitat antworten
  #4 (permalink)  
Alt 12-12-2006, 18:32
schuetz10
 Newbie
Links : Onlinestatus : schuetz10 ist offline
Registriert seit: Dec 2006
Beiträge: 2
schuetz10 ist zur Zeit noch ein unbeschriebenes Blatt
schuetz10 eine Nachricht über ICQ schicken
Standard

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
Mit Zitat antworten
  #5 (permalink)  
Alt 12-12-2006, 18:42
zerni
 Member
Links : Onlinestatus : zerni ist offline
Registriert seit: Oct 2006
Beiträge: 268
zerni ist zur Zeit noch ein unbeschriebenes Blatt
Standard

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
Dateityp: zip testbaum.zip (17,6 KB, 42x aufgerufen)

Geändert von zerni (12-12-2006 um 18:45 Uhr)
Mit Zitat antworten
  #6 (permalink)  
Alt 12-12-2006, 19:02
PHP-Desaster
 PHP Expert
Links : Onlinestatus : PHP-Desaster ist offline
Registriert seit: Mar 2006
Beiträge: 3.105
PHP-Desaster befindet sich auf einem aufstrebenden Ast
Standard

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
Dateityp: pdf travers.pdf (41,6 KB, 196x aufgerufen)
Mit Zitat antworten
Antwort

Lesezeichen


Aktive Benutzer in diesem Thema: 1 (Registrierte Benutzer: 0, Gäste: 1)
 

Themen-Optionen
Thema bewerten
Thema bewerten:

Forumregeln
Es ist Ihnen nicht erlaubt, neue Themen zu verfassen.
Es ist Ihnen nicht erlaubt, auf Beiträge zu antworten.
Es ist Ihnen nicht erlaubt, Anhänge hochzuladen.
Es ist Ihnen nicht erlaubt, Ihre Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are an


PHP News

Die RIGID-FLEX-Technologie
Die RIGID-FLEX-TechnologieDie sogenannte "Flexible Elektronik" , oftmals auch als "Flexible Schaltungen" bezeichnet, ist eine zeitgemäße Technologie zum Montieren von elektronischen Schaltungen.

06.12.2018 | Berni

ebiz-trader 7.5.0 mit PHP7 Unterstützung veröffentlicht
ebiz-trader 7.5.0 mit PHP7 Unterstützung veröffentlichtDie bekannte Marktplatzsoftware ebiz-trader ist in der Version 7.5.0 veröffentlicht worden.

28.05.2018 | Berni


 

Aktuelle PHP Scripte

EJS TreeGrid ansehen EJS TreeGrid

EJS TreeGrid is DHTML component written in pure JavaScript to display and edit data in table, grid, tree view or grid with tree on HTML page

09.04.2019 coqsoft@ | Kategorie: JAVASCRIPT/ Components
Suchmaschine redaktionell, Branchenportal zum Geld verdienen

Programmbeschreibung Die Bezahl-Suchmaschine ist in Perl und PHP programmiert (eigenes CGI-Verzeichnis notwendig), benötigt PHP aber keine MySQL-Datenbank. Webmaster haben mit dieser Suchmaschine neben der normalen kostenlosen Registrierung von Lin

06.04.2019 skripte@ | Kategorie: PHP/ Suchmaschinen
Oog Photo-Video-Gallery

Mit Oog Photo-Gallery können Sie einfach und stilvoll Bilder (auch Video & Audio) auf Ihrem PHP5-Webserver veröffentlichen und verwalten. Lizenz: GNU GPL v2

06.04.2019 trottbrand@ | Kategorie: PHP/ Bilder
 Alle PHP Scripte anzeigen

Alle Zeitangaben in WEZ +2. Es ist jetzt 03:45 Uhr.