Binärbaum preorder Algorithmus

[Fehlersucher]

Hallo,

ich soll einen (rekursiven) Algorithmus schreiben um einen Binärbaum der Klasse TBinaryTree nach dem preorder Algorithmus zu durchlaufen. Der Baum soll dann in einem String wiederzufinden sein, welcher später in einem Edit angezeigt wird.

Dazu darf ich nur die Befehle nutzen, welche auf Seite 12 zu finden sind:
http://www.standardsicherung.nrw.de/....php?file=3181

Nun habe ich schon das hier geschafft:

Anmerkung:
In den Wurzelknoten/Blättern etc. wurden Objekte gespeichert, welche später in Strings umgewandelt werden müssen, was nach dem Schema unten auch richtig funktioniert und für den Algorithmus nebensächlich ist.

Durch die Kettenklasse wird aus dem Objekt der String.

Code:

  function TBaumklasse.preorderfunc(baum:TBinaryTree):string;
  var  
      x, Text : string;
  begin
  if baum.isEmpty = false then
   begin
    x :=  Kettenklasse(baum.getobject).gibString;  // Bis hier wurde das Objekt in einen String umgewandelt 
    Text := Text + x;
    preorderfunc(baum.getLeftTree);
    preorderfunc(baum.getRightTree);
     result := Text;
   end;
    
   end;

Unglücklicherweise funktioniert die Funktion gar nicht richtig.
Ich bekomme als result immer nur den String eines Objekts bzw. Wurzelknotens raus.

Was ist bei mir falsch?

Gruß

[sx2008]

Wenn du eine Funktion rekursiv aufrufst dann musst du auch das Ergebnis der Funktion entgegennehmen!

Delphi-Quellcode:

function TBaumklasse.preorderfunc(baum:TBinaryTree):string;
var
   x, Text : string;
begin
  if not baum.isEmpty then
  begin
    Result := Kettenklasse(baum.getobject).gibString; // Bis hier wurde das Objekt in einen String umgewandelt
    Result := Result + '[' +  preorderfunc(baum.getLeftTree) + ']';
    Result := Result + '[' + preorderfunc(baum.getRightTree) + ']';
  end
  else Result := '';
end;

[Fehlersucher]

Danke für deine Hilfe.

Leider funktioniert es immer noch nicht.

Ich habe meinen Code durch deine Verbesserung ersetzt.

Es wird aber (wie vorher) nur der String eines Objektes angezeigt.


Wenn ich die Funktion aufrufe (und den Binärbaum noch nicht durchschritten habe) wird (nur) der erste Wurzelknoten angezeigt.
Wenn ich jedoch den Binärbaum durchschreite und beispielsweise am dritten Wurzelknoten angekommen bin, wird nach dem Funktionsaufruf (nur) der dritte Wurzelknoten angezeigt.

Woran kann das liegen?

Gruß

[sx2008]

Zitat von Fehlersucher:

Es wird aber (wie vorher) nur der String eines Objektes angezeigt.

WO wird der String angezeigt? Im Debugger der IDE?

Es kommt immer drauf an, wo man den Breakpoint setzt.
Ausserdem ist das Debuggen von rekursiven Funktionen nicht so einfach.
Man verliert sehr leicht den Überblick auf welcher Aufruftiefe man sich bewegt.
Mit einer kleinen Erweiterung (Parameter level) kann man die Tiefe der rekursiven Aufrufe mitzählen:

Delphi-Quellcode:

function TBaumklasse.preorderfunc(baum:TBinaryTree; level:Integer):string;
begin
  if not baum.isEmpty then
  begin
    Result := Kettenklasse(baum.getobject).gibString;
    Result := Result + '[' + preorderfunc(baum.getLeftTree, level+1) + ']';
    Result := Result + '[' + preorderfunc(baum.getRightTree,level+1) + ']';
  end
  else Result := '(empty)';  // zum Test um leere Knoten zu entdecken
end;

[Fehlersucher]

Zitat von sx2008:

Zitat von Fehlersucher:

Es wird aber (wie vorher) nur der String eines Objektes angezeigt.

WO wird der String angezeigt? Im Debugger der IDE?

Nein im Edit.

Ich rufe die Funktion so auf:

Delphi-Quellcode:

function TBaumklasse.make:string
begin
result := preorderfunc(Hauptbaum);
end;

// dann in anderer unit auf eine Buttonclick Methode:
Edit1.text := Hauptform.make

Ich musste noch die Funktion make machen, da der Hauptbaum in einer anderen unit nicht bekannt ist und daher das nicht ginge:

Edit1.text := preorderfunc(Hauptbaum)
Gruß

[sx2008]

Wenn dein Baum effektiv nur aus einem Knoten besteht, dann wird auch nur ein Knoten angezeigt.
Wenn die Funktion gibString() in manchen Fällen einen leeren String liefert, dann sind die Knoten quasi unsichtbar obwohl sie da sind.
Um leere Knoten erkennen zu können dann kannst du die Funktion aus Beitrag #4 verwenden.

Ein Baum mit einem Knoten würde dann so in einen String übersetzt:

Code:

Name123[(empty)][(empty)]

[entwickler]

Hallo zusammen

@Fehlersucher: Mensch hast du ein Glück!!! Wir machen genau dasselbe in Informatik. Letzte Woche haben wir die Komplettlösung unseres Lehrers bekommen (Wir sollen den Baum jetzt nämlich sortieren lassen, aber das funktioniert noch nicht).
Das Projekt wurde mit Lazarus geschrieben, aber du kannst dir die einzelnen Prozeduren/ Funktionen einfach aus den Units herauskopieren . Diese funktionieren auch (soweit ich weiss) alle rekursiv (unser Lehrer bestand darauf).
Die Aufrufe "Get~" belegen den Baum im entsprechenden Verfahren (Pre-, Post- oder Inorder), die Aufrufe "Set~" geben den Bauminhalt (also dessen Knotendaten) im gewünschten Auslesenverfahren wieder aus.

Weitere Fragen kannst du gerne an mich stellen

[BUG]

Ist das euer Code oder der des Lehrers?
Manche Lehrer/Dozenten/Institutionen drücken mithilfe des Urheberrechts durch, dass die Lösungen ihrer Aufgaben nicht im Netz zu finden sind. Also Vorsicht mit so etwas.

[sx2008]

Zitat von entwickler:

Mensch hast du ein Glück!!!

Naja, Glück ist wenn man das Thema verstanden und umgesetzt hat und später für die eigene Leistung eine gute Note bekommt.
Fremde Projekte kopieren und als eigene Leistung auszugeben ist geschummelt.

[entwickler]

@BUG: Das ist der Code, den wir zusammen als Kurs erarbeitet haben und den unser Lehrer dann nochmal für jeden zusammengestellt hat.

@sx2008: Naja, mit deiner Kernaussage hst du irgendwie recht. Ich denke aber nicht, dass Fehlersucher das ganze Projekt gleich vollständig übernimmt, weil sich das Sortierverfahren (ohne Änderungen vorzunehmen) nur auf den von uns implementierten Binärbaum anwenden lässt. Die Eigenleistung besteht, denke ich, darin, die Funktionen/ Prozeduren dann an den eigenen Baum anzupassen
Sry, wenn das falsch rübergekommen ist