binären baum speichern und ladenFür ein

[p3ps1]

Für ein kleines Spiel benutze ich einen binären Baum. Wenn in diesem dann irgendwann Daten sind möchte ich ihn natürlich speichern und laden können. Aber wie geht das? Gespeichert wird er soweit ich weiss in einer Liste. Aber wie krieg ich ihn wieder in den Baum?

[sakura]

Zeig uns mal ein wenig, wie Dein Baum definiert ist (Typendeklarationen, etc..)

...:cat:...

[p3ps1]

Delphi-Quellcode:

Type TBintreenode = class(TBase)
                     left,right:TBintreenode;
                     Constructor create(l:TBintreenode;tb:TBase;r:TBintreenode);
                     Procedure insertleft(l:TBintreenode);
                     Procedure insertright(r:TBintreenode);
                     Function leftTree:TBintreenode;
                     Function rightTree:TBintreenode;
                     Function elem:Tbase;
                     Function copy:TBintreenode;
                     Function depth:Integer;
                     Destructor Destroy;Override;
                     Function schluss:Boolean;
                     Function getvalue:TBase;
                     Procedure setvalue(tb:TBase);
                   Private
                     value:Tbase;
                   End;



     Ttree = class(TBase)
               root : TBintreenode;
               constructor create;
               Function empty:Boolean;
               Function copy:Ttree;Virtual;
               Function depth:Integer;
               Destructor destroy;Override;
             End;

[edit=sakura] [delphi]-Tag geschlossen. Mfg, sakura[/edit]

[p3ps1]

Vielleicht erkläre ich mein Problem noch mal etwas genauer.
Man speichert den binären Bum ja in einem array. Und zwar etage für etage.
der folgende Baum



6

5 7

4 2 1 9

soll dann also so im array gespeichert werden: 6,5,7,4,2,1,9
der baum
6

5 7

1 9
sollte so aussehen: 6,5,7, , ,1,9

Und da weiss ich leider nicht wie ich das Programmteschnisch umsetzten soll.
Auf jeden Fall müsste es eine rekursive Procedur sein.

[MacGuyver]

Moin auch!

Ich staune. :shock: Der Binärbaum ist für Indexdateien gedacht. :gruebel: Normalerweise hast du einen Datensatz wofür der Binärbaum als Index geführt wird. Was für Daten speicherst du denn? Wie viele Daten sind es? Kann es sein, daß der BBaum dort völlig fehl am Platze ist :?:

[Tryer]

Binärbäume sind nicht "für Indexdateien gedacht", sondern nur gut dafür geeignet da man sie sehr schnell durchsuchen kann (was ja nunmal Sinn und Zweck einer solchen Datei ist).
In vielen Bereichen der Spieleprogrammierung sind sie auch sehr willkommen, z.B. lässt sich der A*-Algorithmus hervorragend mit einem Binärbaum beschleunigen.

Hier mal ein 'schematisches' Beispiel an dem Du die Sortierung der Items im Array nachvollziehen kannst, darüber sollte es nicht allzu schwer sein sowas selber umzusetzen (aber bitte nicht genauso, da geht die ganze Performance des Bintree-Konzepts wieder flöten ;)):

Delphi-Quellcode:

type
  TBinTreeNode = class;

  TBinTreeArray = array of TBinTreeNode; //erstes Item bei Index 1 !

  TBinTreeNode = class
  private
    FIndex: Integer;
    FArray: TBinTreeArray;
    function GetChild(const Index: Integer): TBinTreeNode;
    procedure SetChild(const Index: Integer; const Value: TBinTreeNode);
    function GetParent: TBinTreeNode;
  public
    constructor Create(Array: TBinTreeArray; Index: Integer);
    property Index: Integer read FIndex;
    property Left: TBinTreeNode Index 0 read GetChild write SetChild;
    property Right: TBinTreeNode Index 1 read GetChild write SetChild;
    property Parent: TBinTreeNode read GetParent;
    (...)
  end;

implementation

{ FIndex: der eigene Platz im Array
  Index: 0/1 für links/rechts }
function TBinTreeNode.GetChild(const Index: Integer): TBinTreeNode;
begin
  Result := FArray[FIndex * 2 + Index];
end;

procedure TBinTreeNode.SetChild(const Index: Integer;
  const Value: TBinTreeNode);
begin
  FArray[FIndex * 2 + Index] := Value;
end;

function TBinTreeNode.GetParent: TBinTreeNode;
begin
  Result := FArray[FIndex div 2];
  { FArray[0] mit nil initialisieren,
    bei Parent=nil ist man dann oben angekommen }
end;
(...)

MfG,
Tryer