php-resource



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

Login

 
eingeloggt bleiben || php-forumjetzt anmelden
 

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, 44x 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, 205x 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

OnPremise versus Cloud - das richtige System finden
Wir beleuchten in diesem Artikel, die Vor- und Nachteile für Cloud oder OnPremise Systemen. Und warum es definitiv Zeit wird in die Cloud zu wechseln.

09.05.2022 | julia_mjr

Warum Texterstellung mit künstlicher Intelligenz richtig gut ist
Warum Texterstellung mit künstlicher Intelligenz richtig gut istKünstliche Intelligenz ist dabei, die Welt zu erobern. Die größten Unternehmen entwickeln Systeme, die einen Text für Sie schreiben können. Und sie machen das sehr gut.

05.01.2022 | Berni


 

Aktuelle PHP Scripte

phpBasics Counter

Der Counter arbeitet mit einer klassischen einstellbaren IP-Reloadsperre. Er zählt die Besucher, die Seitenaufrufe und ermittelt auch die aktuellen Onlineuser. Zur Datenspeicherung wird eine MySQL-Datenbank genutzt. Der Counter überprüft seine Instal

09.09.2022 numaek | Kategorie: PHP/ Counter
MyPHPlib-Bibliotheksverwaltung

MyPHPlib ist eine Scriptsammlung, mit der die Bibliotheksverwaltung incl. Ausleihe und Recherche gelingt. Die Scriptsammlung wird seit Mitte 2005 entwickelt und ist besonders an den Bedürfnissen von Schulen angepasst.

11.08.2022 RobertG | Kategorie: PHP/ Management
responsive vertikales Menu

Diese Menu basiert auf php, jQuery, css und ajax. Wer sein Menu mit nested sets vertikal realisieren will, findet darin eine gute Lösung.

11.08.2022 COVISIONMEDIA | Kategorie: JAVASCRIPT/ Navigation
 Alle PHP Scripte anzeigen

Alle Zeitangaben in WEZ +2. Es ist jetzt 20:16 Uhr.