Freepascal AVLTree, Binären Baum allgemein verstehen?

[MPeters]

Danke zuerst für Eure Antworten.

@Fiete, Deinen Entwurf schau ich mir jetzt in den nächsten Tagen an.

Ich habe jetzt erst mal folgenden Entwurf für eine Baumstruktur, die aber noch nicht funktioniert wie sie soll. In meinem TMemo wird nichts ausgegeben. Hatte in der FormCreate Methode die Prozedur CreateNodes vergessen, aufzurufen, nun aber bekomme ich eine Schutzverletzung an Adresse $00615729.

Hier der Code:

Zuerst der Baum:

Delphi-Quellcode:

unit ugentree;

interface

uses classes;

type
  TCompareStrFunc = function(s1,s2: String): Integer;
  TCompareIntFunc = function(i1,i2: Integer): Integer;
  TCompareFunc = function(p1,p2: String): Integer;

  TNode = class;

  TNodeData = class(TObject)
    FKey: Integer;
    FKeyStr: String;
    FData: Pointer;
    FNode: TNode;
    constructor Create(aKey: Integer; aKeyStr: String; aData: Pointer; var aNode: TNode);
    property Key: Integer read FKey write FKey;
    property KeyStr: String read FKeyStr write FKeyStr;
    property Data: Pointer read FData write FData;
    property Node: TNode read FNode write FNode;
  end;

  TNodes = class(TList)
  private
    function GetNodes(Index: Integer): TNode;
  public
    function Add(aNode: TNode): Integer;
    property Nodes[Index: Integer]: TNode read GetNodes;
  end;

  TNode = class(TObject)
  private
    FCompare: TCompareFunc;
    FData: TNodeData;
    FParent: TNode;
    FSubnodes: TNodes;

    function GetCount: Integer;
    function GetNodes(Index: Integer): TNode;
    procedure SetData(const Value: TNodeData);
  public
    constructor Create(CompareFunc: TCompareFunc);
    destructor Destroy; override;

    procedure Add(ParentNode: TNode; aData: TNodeData);
    procedure AddSubnode(aNode: TNode; aData: TNodeData);                         //Neuen Sub Knoten hinzufügen

    property Data: TNodeData read FData write SetData;                            //Datenihnalt dieses ersten Konotens oder der Wurzel
    property Nodes[Index: Integer]: TNode read GetNodes;                          //Die Blätter
    property Count: Integer read GetCount;                                        //Anzahl Blätter
    property Parent: TNode read FParent write FParent;
  end;

function CompareInt(a,b: Integer): Integer;
function CompareStr(s,t: String): Integer;

implementation

function CompareInt(a,b: Integer): Integer;
begin
  if a<b then Result := -1 else
  if a=b then Result :=  0 else
  Result := +1;
end;

function CompareStr(s,t: String): Integer;
begin
  if s<t then Result := -1 else
  if s=t then Result :=  0 else
  Result := +1;
end;

{ TNode }

procedure TNode.Add(ParentNode: TNode; aData: TNodeData);
begin

end;

procedure TNode.AddSubnode(aNode: TNode; aData: TNodeData);
begin
  FSubnodes.Add(aNode);
end;

constructor TNode.Create(CompareFunc: TCompareFunc);
var a: Pointer; b: TNode;
begin
  inherited Create;
  //FData := FData.Create(0,'',a,b);
  FSubnodes := TNodes.Create;

  FCompare := @CompareFunc;
end;

destructor TNode.Destroy;
begin
  FSubnodes.Free;
  FData.Free;
  inherited;
end;

function TNode.GetCount: Integer;
begin
  Result := FSubnodes.Count;
end;

function TNode.GetNodes(Index: Integer): TNode;
begin
  if Index < 0 then Result := NIL;
  if Index >= FSubnodes.Count then Result := NIL;

  if (Index < FSubnodes.Count) and (Index >= 0) then
    Result := FSubNodes.Nodes[Index];
end;

procedure TNode.SetData(const Value: TNodeData);
begin
  FData := Value;
end;

{ TNodes }

function TNodes.Add(aNode: TNode): Integer;
begin
  Result := inherited Add(Pointer(aNode));
end;

function TNodes.GetNodes(Index: Integer): TNode;
begin
  Result := TNode(Items[Index]);
end;

{ TNodeData }

constructor TNodeData.Create(aKey: Integer; aKeyStr: String; aData: Pointer;
  var aNode: TNode);
begin
  inherited Create;
  //FNode := TNode.Create(CompareStr);
  FData := aData;
  FKeyStr := aKeyStr;
  FKey := aKey;
end;

end.

Nun die Formular Unit:

Delphi-Quellcode:

unit Utreeform;

interface

uses
  Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,
  Vcl.Controls, Vcl.Forms, Vcl.Dialogs, ugentree, Vcl.StdCtrls;

type
  TForm2 = class(TForm)
    Memo1: TMemo;
    lblComponents: TLabel;
    procedure FormCreate(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

var
  Form2: TForm2;

  Root: TNode;
  myFirstNode: TNode;
  mySecondNode: TNode;
  MyThirdNode: TNode;

implementation

{$R *.dfm}

procedure CreateNodes;
var Data: TNodeData; Node: TNode;
begin
  Node := TNode.Create(CompareStr);
  Data := TNodeData.Create(0,'TButton',nil,Node);
  Data.KeyStr := 'TButton';
  Root.AddSubnode(TNode.Create(CompareStr),Data);

  Node := TNode.Create(CompareStr);
  Data := TNodeData.Create(0,'TEdit',nil,Node);
  Data.KeyStr := 'TEdit';
  Root.AddSubnode(TNode.Create(CompareStr),Data);

  Node := TNode.Create(CompareStr);
  Data := TNodeData.Create(0,'TGrid',nil,Node);
  Data.KeyStr := 'TGrid';
  Root.AddSubnode(TNode.Create(CompareStr),Data);
end;


procedure TForm2.FormCreate(Sender: TObject);
var i: Integer; D: TNodeData;
begin
  CreateNodes;
  for i := 0 to Root.Count-1 do
  begin
    D := Root.Nodes[i].Data;
    Memo1.Lines.Add(D.KeyStr);
  end;
end;

initialization
   Root := TNode.Create(CompareStr);

finalization

end.

Ich will die Knoten an seine Blätter hängen, die als TList realisiert sind um nicht nur Links und Rechts zu haben sondern beliebig viele Unterknoten. Die will ich nun an Root anhängen.

Leider funktioniert das noch nicht und hier komme ich alleine nicht weiter. Was muss ich hier anders machen?