runtime error in rekursiver funktion mit binary trees

[madRAM]

Hi Leute,

ich habe hier ein kleines Problem mit einer rekursiven Funktion. Ich moechte einen Binaeren Baum der Art:

type
tRefBinBaum = ^ tBinBaum;
tBinBaum = record
links,
rechts : tRefBinBaum;
info : integer
end;

(also den Pascal Klassiker) mit einer rekursiven Funktion nach einer gegebenen Zahl durchsuchen lassen. Meine Funktion sieht dabei so aus:

function BTSearchLeafRek ( inZahl : integer;
inRefWurzel : tRefBinBaum ) : tRefBinBaum;
var
Zeiger : tRefBinBaum;

begin
if (Zeiger <> nil) then
begin
if inZahl < Zeiger^.info then
Zeiger := BTSearchLeafRek (inZahl, Zeiger^.links);
if inZahl > Zeiger^.info then
Zeiger := BTSearchLeafRek (inZahl, Zeiger^.rechts);

BTSearchLeafRek := Zeiger;
end
end;

und gibt mir - fuer alte Hasen wahrscheinlich erwartungsgemaess - einen runtime Error.


Ich hab hier mal gleich zwei Fragen:

1. Ist es ein Denkfehler anzunehmen, dass die Rueckgabezeile innerhalb der if-Abfrage stattfinen muss. Ich glaube irgendwie, wenn ich sie ausserhalb der if-Abfrage unterbringe, dass dann Zeiger IMMER mit nil zurueckgegeben wuerde - oder hab ich da das Konzept der Rekursion nicht verstanden?

2. Muss ich denn wirklich noch eine boolsche Abrage der Art

if (Zeiger <> nil) and not gefunden then

in diese Funktion einbringen. In dem Fall waere doch die ganze Rekursionssache irgendwie bloed, oder?

3. Wie waere diese if-Abfrage:

if (Zeiger <> nil) and Zeiger^.info <> inZahl then

ist das geschickter?

Naja, das waren dann nun doch wieder 3 Fragen, aber egal. Freue mich auf heftigste Kritik und noch mehr gute Ratschlaege ;-)

chris

[madRAM]

Ok, ok, ok,

typischer Anfaengr/Faulenzerfehler. Ich muss mich wirklich etwas mehr an die Kandahre nehmen.

Wenige Minuten, eigentlich waren es wahrscheinlich nur Sekunden, nachdem ich auf den Senden-Button gedrueckt hatte fiel mir mein wirklich bloeder Fehler selber auf. Mit folgender Funktion gibt es natuerlich uebehaupt keine Fehler mehr:

function BTSearchLeafRek ( inZahl : integer;
inRefWurzel : tRefBinBaum ) : tRefBinBaum;
{ liefert einen Zeiger auf die Wurzel mit der gesuchten Zahl inZahl,
oder nil, wenn inZahl nicht im Baum ist
Diese Funktion arbeitet rekursiv }

var
Zeiger : tRefBinBaum;

begin
Zeiger := inRefWurzel;

if (Zeiger <> nil) and (Zeiger^.info <> inZahl) then
if inZahl < Zeiger^.info then
Zeiger := BTSearchLeafRek (inZahl, Zeiger^.links)
else
Zeiger := BTSearchLeafRek (inZahl, Zeiger^.rechts);

BTSearchLeafRek := Zeiger
end;

Und fuer alle, die wie ich gerade erst intensiv mit Pascal und Rekursion und binaeren Baeumen und so anfangen hier eine Beschreibung meiner Anfaengerfehler:

1. Die Urspruengliche Funktion hat zwar eine Variable zur Aufnahme des uebergebenen Baumes vorgesehen, diese Variable wurde aber gar nicht mit dem Baum initialisiert, so dass ich im Grunde auf einem nicht initialisierten Zeiger gearbeitet habe - BOESER FEHLER!!!

2. Ich habe in meiner if-Abfrage gar nicht ueberprueft, ob die gesuchte Zahl ueberhaupt gefunden wurde, da kann man natuerlich IMMER nur bis ans Ende des Baumes laufen, Grrrr

3. statt zwei if-Abfragen - eine auf kleiner und eine auf groesser ist hier selbstverstaendlich eine if-else Abfrage zu waehlen.

Alles in allem, kann man hier deutlich sehen, was fuer ein Anfaenger ich bin ;-)

Naja, aus Fehlern lernt man und zu meiner Ehrenrettung, ich habe es selber herausgefunden.

chris

[Diogenes]

Mach Dir nichts draus: so mad geht's in Deinem Wet-RAM ( :) ) gar nicht zu. Ich programmier schon seit Jahren in Pascal und mir passieren auch noch solche Fehler. (Zeigerhandling ist ja doch nicht so einfach, weil Du einen Teil der Speicherverwaltung übernehemen mußt.) Aber eine Nachlässigkeit ist es, das hast Du recht.

Ich bin auf jeden Fall aber froh, daß Du zu einer vernünftigen Selbstkritik fähig bist. Solche Leute brauchen wir. Wollkommen im Orden vom Hl. Niklas *kicher*

Und noch etwas: Bitte schreib' sauberer. Benutz' den CODE-Tag für Source-Zitate. Es könnte ja sein, daß einer, der hier 'reinschaut, ein ähnliches Problem wie Du hat. Dein Post hilft dann gar nichts, wenn er so unsauber geschrieben ist, daß man ihn nicht versteht oder gar wegen der Unschönheit ignoriert.

[madRAM]

Ich bin auf jeden Fall aber froh, daß Du zu einer vernünftigen Selbstkritik fähig bist. Solche Leute brauchen wir. Wollkommen im Orden vom Hl. Niklas *kicher*
Naja, meiner Meinung nach sollte man immer selbstkritisch sein. Es gibt am eigenen Verhalten und Tun immer etwas zu verbessern.


Und noch etwas: Bitte schreib' sauberer. Benutz' den CODE-Tag für Source-Zitate. Es könnte ja sein, daß einer, der hier 'reinschaut, ein ähnliches Problem wie Du hat. Dein Post hilft dann gar nichts, wenn er so unsauber geschrieben ist, daß man ihn nicht versteht oder gar wegen der Unschönheit ignoriert.
Danke fuer den Hinweis. Ich kannte das CODE Tag noch gar nicht. Hab mich aber selber schon gefragt, wie bei anderen Postings der Code so sauber aussehen kann. Next time, versprochen.

Gruss,

chris