matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenPascalBinäre Bäume (Pascal)
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
Forum "Pascal" - Binäre Bäume (Pascal)
Binäre Bäume (Pascal) < Pascal < Programmiersprachen < Praxis < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Pascal"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Binäre Bäume (Pascal): Frage
Status: (Frage) reagiert/warte auf Reaktion Status 
Datum: 18:06 Do 07.04.2005
Autor: LaAlemanita

Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt


Ich habe ein kleines Problem. Wir besprechen in unserem Informatikgrundkurs gerade binäre Bäume und sollen jetzt Porzeduren zum Löschen einzelner Daten schreiben. So weit so gut....ich habe jetzt eine Prozedur geschrieben, die die Zeiger des RECORDS wieder auf NIL setzt, also die auf dem Zeiger gespeicherten Daten löscht. Das ist ja bei den einfachsten Fällen nötig, also wenn das letzte bzw. erste Element gelöscht werden muss, an dem keine andere Elemente mehr dranhängen. Auch kontne ich eine Prozedur schreiben, die den Zeiger auf ein anderes RECORD zeigen lässt, das ist ja für Fälle nötig, wenn noch ein anderer Datensatz an dem Zeiger hängt. Jetzt komm ich aber nicht weiter. Ich schaffe es nicht, eine Prozedur zu schreiben, für den Fall dass das Oberste Element (also an dem alle anderen dranhängen) gelöscht werden soll. Ich weiß nicht, wie ich es anstellen kann, ein neues oberstes Element zu ermitteln, am obersten hängen ja so gut wie immer zwei Datensätze. Welches davon wird nun oberstes? Und wie rück ich dies in einer Prozedur aus? Für Hilfestellungen wäre ich echt dankbar,

liebe Grüße,
Barbara

        
Bezug
Binäre Bäume (Pascal): Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:42 Do 07.04.2005
Autor: Lizard

Ich hab zwar keine Erfahrung mit Pascal, aber die generelle Vorgehensweise ist doch, wenn ich mich recht erinnere, einfach den linken Unterbaum zu nehmen und ganz links unten am rechten Unterbaum einzufügen, oder? Das sähe dann so aus:

      4
     / [mm] \backslash [/mm]
    3   5
   / [mm] \backslash [/mm]
  1  2

wird zu

      5
     /
    3
   / [mm] \backslash [/mm]
  1  2

Sollte eigentlich hinkommen, aber vielleicht antwortet ja noch jemand ein bißchen ausführlicher auf die Frage ;)

Bezug
                
Bezug
Binäre Bäume (Pascal): Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:36 Fr 08.04.2005
Autor: LaAlemanita

Mh, so weit war ich auch schon mal, ich bekomme nur immer Probleme wenn ich z.B. diesen "Baum" habe:

                                    f
                               /        [mm] \ [/mm]
                              c         k
                          /      \     /   [mm] \ [/mm]
                       a         e   h    o

Welches wird dann mein neuer Buchstabe (soll ja alphabetisch geordnet bleiben)? Und was mache ich mit den Buchstaben die dadran hängen? Und wie setzte ich das ganze in pascal um?

Bezug
                        
Bezug
Binäre Bäume (Pascal): Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:34 Fr 08.04.2005
Autor: Lizard


> Mh, so weit war ich auch schon mal, ich bekomme nur immer
> Probleme wenn ich z.B. diesen "Baum" habe:
>  
>                                     f
>                                 /        [mm]\backslash[/mm]
>                                c         k
>                            /      \     /   [mm]\backslash[/mm]
>                         a         e   h    o
>  
> Welches wird dann mein neuer Buchstabe (soll ja
> alphabetisch geordnet bleiben)? Und was mache ich mit den
> Buchstaben die dadran hängen? Und wie setzte ich das ganze
> in pascal um?


Hmm, wie kommst du darauf, daß es da eine alphabetische Ordnung geben muß? Die einzige Ordnungseigenschaft von Binärbäumen ist die, daß im linken Unterbaum eines Knotens mit Beschriftung $x [mm] \in \IN$ [/mm] nur Knoten mit Beschriftung kleiner (gleich) $x$ vorkommen, und im rechten Unterbaum nur Knoten mit Beschriftung größer (gleich) $x$.

Wenn du im Beispiel den Unterbaum am Knoten $c$ nimmst, und den an den Knoten $h$ hängst, ist dies gewährleistet - wenn diese Eigenschaft vorher auch schon für den gesamten Baum gehalten hat. Insofern sehe ich nicht ganz dein Problem, zumindest solange du nicht darauf bestehst, daß du beim "Lesen" des Baums von links nach rechts die richtige alphabetische Reihenfolge erhältst. Allerdings gilt durchaus die Aussage, daß alle Buchstaben im linken Unterbaum eines Knotens (z.B. $k$ oder $h$) im Alphabet vor diesem Buchstaben kommen, und alle Knoten in einem rechten Unterbaum im Alphabet nachher kommen - sollte das also gemeint gewesen sein, gibt es da keine Probleme.

Die Buchstaben, die bei einem zu versetzenden Baum "daran" hängen, werden mit umgepflanzt, weil du eben den ganzen Unterbaum verschiebst. Dazu genügt es, die Referenz (oder wie das in Pascal eben heißt), die von $h$ auf dessen linkes Kind zeigt, auf den schon vorher erstellten Knoten $c$ verweisen zu lassen, denn "ab da" stimmt ja alles wieder (d.h. in $c$ und dessen Unterbäumen sind die Referenzen alle richtig gesetzt). Wie das konkret geht, weiß vielleicht jemand anders, deshalb habe ich ja auch bloß eine "Mitteilung" und keine "Antwort" geschrieben.


Bezug
                                
Bezug
Binäre Bäume (Pascal): Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 11:06 Sa 09.04.2005
Autor: bazzzty


> > Welches wird dann mein neuer Buchstabe (soll ja
> > alphabetisch geordnet bleiben)? Und was mache ich mit den
> > Buchstaben die dadran hängen? Und wie setzte ich das ganze
> > in pascal um?
>
> Hmm, wie kommst du darauf, daß es da eine alphabetische
> Ordnung geben muß? Die einzige Ordnungseigenschaft von
> Binärbäumen ist die, daß im linken Unterbaum eines Knotens
> mit Beschriftung [mm]x \in \IN[/mm] nur Knoten mit Beschriftung
> kleiner (gleich) [mm]x[/mm] vorkommen, und im rechten Unterbaum nur
> Knoten mit Beschriftung größer (gleich) [mm]x[/mm].

Wenn  man einen solchen Baum vor sich hat, daß liefert ein in-order-Durchlauf der Blätter eine sortierte Ausgabe. Wenn  man die Wurzel eines Teilbaumes löscht, läßt sich deshalb diese Eigenschaft am leichtesten erhalten, wenn man das Blatt, was in so einer Ausgabe direkt vor oder nach der Wurzel käme, als neue Wurzel auswählt, also im Beispiel e oder h (als Ersatz für f. Damit läßt sich jedes Löschen auf das Löschen eines Blattes zurückführen.

Zum Nachdenken (bei einer Implementierung) bleibt aber trotzdem noch: Wie bekomme ich dieses Element (schnell), ohne den ganzen Baum zu traversieren, auch wenn der Baum nicht balanciert ist?

Bezug
                                        
Bezug
Binäre Bäume (Pascal): Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 13:35 Sa 09.04.2005
Autor: Lizard

Hallo,

> Wenn  man einen solchen Baum vor sich hat, dann liefert ein
> in-order-Durchlauf der Blätter eine sortierte Ausgabe. Wenn
>  man die Wurzel eines Teilbaumes löscht, läßt sich deshalb
> diese Eigenschaft am leichtesten erhalten, wenn man das
> Blatt, was in so einer Ausgabe direkt vor oder nach der
> Wurzel käme, als neue Wurzel auswählt, also im Beispiel e
> oder h (als Ersatz für f. Damit läßt sich jedes Löschen auf
> das Löschen eines Blattes zurückführen.

Ah ja, du hast natürlich Recht... mein Ansatz wäre zwar nicht falsch gewesen, aber deiner ist sicherlich effektiver, wenn man auf eine geeignete Datenstruktur zurückgreift (und auch eleganter, der Baum wird nicht so stark debalanciert). Ist also wohl besser, es so zu machen!


Bezug
        
Bezug
Binäre Bäume (Pascal): Rückfrage
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:45 Sa 09.04.2005
Autor: SEA

Hallo !

Ich glaube, du hast beim Löschen deines Baumes einen Fehler gemacht!
Es reicht nähmlich nicht zu, die Zeigervariablen auf "nil" zu setzen!!!
Dadurch wird nur der Zeiger auf eine Null-Adresse gesetzt aber der Speicher nicht wieder für andere Daten freigegeben.

Nun bin ich mir aber nicht sicher, ob ich dein Problem richtig verstanden habe:
Willst du das oberste sowie alle daran hängenden Elemente löschen?!
Wenn Ja:

Hierzu ist eine rekursive Prozedur nötig, die den ganzen Baum abklappert und von hinten die Daten löscht (Befehl: dispose()). Normalerweise wird somit auch der Anker (das oberste Element) entfernt.

Ich hoffe ich konnte dir etwas helfen ...
Wenn du deinen Quelltext hier nocheinmal postest, kann ich dich evtl. noch etwas besser unterstützen :-)

Tschü

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Pascal"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]