Knoten an Baum hinzufügen

[mytar]

Ich versuche vergeblich einen neuen Knoten an einen existierenen Baum hinzuzufügen:

Delphi-Quellcode:

var Top: Knoten;

function Hinzufuegen(Knoten: TKnoten, var Added: Boolean): TKnoten;
begin
  if not Added then
   if Assigned(Knoten) then
    begin //hier wird bis zum letzen existierenden Knoten gesprungen
    if not Assigned(Knoten.Knoten[1]) then
     Hinzufuegen(Knoten.Knoten[1], Added)
    else
     Hinzufuegen(Knoten.Knoten[2], Added);
    end   
   else //sonst wird auf einem freien Zweig ein neuer Knoten erzeugt
    begin
    Knoten := TKnoten.Create; 
    Result := Knoten;
    Added := True;
    end;
end;

Ich rufe diese Funktion mit der globalen Variable Top auf.
Stimmt etwas mit den Var-Parameter nicht?
Kann man die Methode mit Added verbessern?

[mytar]

Eine Instanz von TKnoten besteht wiederum aus beliebig vielen Instanzen von TKnoten, usw.

Ich denke ihr versteht schon. Der Fehler muss in dieser Funktion liegen, denn manuell schaffe ich es schon die Knoten zu erstellen.

Das ganze ist hier rekursiv, also ich weiß nicht ob es iterativ besser wäre.

[Niels]

Hallo,

zuerst einmal würde mich interessieren wie du die Klasse TKnoten aufgebaut hast.

Ein Baum hat ja den Sinn, gewisse Sachen leichter zu finden oder irgendwelche Sachen strukturiert abzuspeichern. Dein Baum besitzt jedoch gar keine Struktur. Zumindest wird das Einfügen nach keiner Struktur geregelt. Naja eigentlich wird auch gar nix eingefügt.
Deine Funktion gibt immer einen leeren Knoten zurück. Um dir die Funktionsweise der Funktion nochmal vor Augen zu führen:

- du schaust, ob schon geadded wurde (keine Ahnung warum, lass es einfach weg, da die Rekursion doch nach "Added := True;" gar nicht fortgesetzt wird)
- nun schaust du ob Knoten = nil ist.
a) wenn er das ist, dann legst du einen leeren Knoten an (und gibst ihn zurück)
b) wenn er etwas enthält, dann guckst du, ob der erste Unterknoten leer ist:
- ist er leer rufst du deine Funktion mit dem leeren erneut auf und a) tritt ein
- ist er nicht leer, wird deine Funktion mit Unterknoten 2 (egal ob er leer ist oder nicht) aufgerufen (dort geht's dann weiter)

Ich geh davon aus, dass eigentlich im Baum das Ende gesucht werden soll und dann der ganze Knoten angehängt wird.

Ok wenn man das nun ändert bleibt trotzdem noch folgendes:
Wenn du mehr als 2 Unterknoten hast werden die restlichen außer acht gelassen. Außerdem wird dein 2. Unterknoten total vollgeschaufelt, während im 1. nur 1 Datensatz steht.

Angenommen, deine Struktur soll so aufgebaut sein, dann würde ich aus der Funktion ne Prozedur machen, die dann so aussieht:

Delphi-Quellcode:

proceudre Hinzufuegen(var Baum: TKnoten; Knoten: TKnoten);
begin
  if Assigned(Baum) then
  begin //hier wird bis zum letzen existierenden Knoten gesprungen
    if not Assigned(Baum.Knoten[1]) then
      Hinzufuegen(Baum.Knoten[1], Knoten)
    else
      Hinzufuegen(Baum.Knoten[2], Knoten);
  end   
  else //sonst wird auf einem freien Zweig ein neuer Knoten erzeugt
  begin
    Baum := TKnoten.Create;
    Baum := Knoten
  end;
end;

PS:

Ich mach sowas meistens mit Records. Das könnte so aussehen.

Delphi-Quellcode:

type
  PBaum = ^TBaum;
  TBaum = record
    links, rechts: PBaum;
    dat: TDatentyp
  end;

mfg Niels

[Niels]

Leider hatte ich deinen 2. Beitrag noch nicht gelesen, aber wenn ein Knoten wiederum beliebig viele Knoten enthält, dann müsste man die Funktion weiter umbauen. Dazu wäre nun aber nötig zu wissen, nach welchem System die Knoten einsortiert werden sollen.

mfg Niels

[mytar]

Danke, Niels für deine Hilfe!

Du hast mich jetzt auf einen Fehler gebracht. Denn die Referenz zum Vaterknoten fehlt jeweils.

Ich werde das ganze überarbeiten und überdenken.

Meld mich dann wieder!

[mytar]

Zitat von Niels:

Delphi-Quellcode:

type 
  PBaum = ^TBaum; 
  TBaum = record 
    links, rechts: PBaum; 
    dat: TDatentyp 
  end;

Ich werds so machen, das ist einfacher!

Danke dir Niels

Für mich ist das hier [Erledigt]!