Freepascal AVLTree, Binären Baum allgemein verstehen?

[Gausi]

Delphi-Quellcode:

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

Warum erzeugst du an der markierten Stelle einen neuen Knoten? Das führt doch dazu, dass du an Root einen Knoten einfügst, der ein Data-Objekt enthält, das auf einen Knoten Node verweist, der nach Ablauf der Prozedur CreateNodes gar nicht mehr da ist.

So sollte es funktionieren:

Root.AddSubnode(Node, Data);

[MPeters]

@Gausi: Danke, aber leider funktioniert auch das nicht.

Auch mit dieser Änderung funkt der Code nicht

Delphi-Quellcode:

function TForm2.CreateNodes: TNode;
var
  Data: TNodeData; Node: TNode;
begin

  Node := TNode.Create(CompareStr);
  Data := TNodeData.Create(0,'TButton',nil);
  //Data.KeyStr := 'TButton';

  Root.AddSubnode(TNode.Create(CompareStr),Data);

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

  Root.AddSubnode(TNode.Create(CompareStr),Data);

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

  Root.AddSubnode(TNode.Create(CompareStr),Data);
  Result := Root;
end;


procedure TForm2.FormCreate(Sender: TObject);
var i: Integer; D: TNodeData; N: TNode;
begin
  N:=CreateNodes();


  for i := 0 to N.Count-1 do
  begin
    D := N.Nodes[i].Data;
    Memo1.Lines.Add(D.KeyStr);
  end;

end;

Hier noch der geänderte Constructor für TNodeData. Node wird nun innerhalb des Konstruktors nicht mehr erzeugt.

Delphi-Quellcode:

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

Ich erhalte eine Schutzverletzung, der Debugger bleibt auf

Memo1.Lines.Add(D.KeyStr);

in der Methode FormCreate stehen.

Warum? Was mache ich da noch falsch? Ich will doch die Knoten als Subknoten an Root anhängen. Alles Andere folgt später, wenn das hier klappt.

Der Code ist mit Ausnahme der Codeausschnitte hier gleich dem im Eingangsbeitrag geblieben, die Änderungen sind nun hier in diesem Beitrag.

[Gausi]

Wenn ich das richtig sehe, wird jetzt an keiner Stelle mehr die Eigenschaft Data der Nodes gesetzt. D.h. du erzeugst zwar Objekte vom Typ TNodeData und TNode, die Nodes wissen aber nichts von NodData. Wenn du dann auf Nodes[i].Data zugreifst, dann knallt es halt ...

[MPeters]

Ich habe das Problem jetzt so hier gelöst.

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;

    constructor Create(aKey: Integer; aKeyStr: String);
    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;
    FCaption: String;
    FParent: TNode;
    FSubnodes: TNodes;

    function GetCount: Integer;
    function GetNodes(Index: Integer): TNode;
  public
    constructor Create(aParent: TNode; CompareFunc: TCompareFunc; aCaption: String);
    destructor Destroy; override;

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

    property Caption: String read FCaption write FCaption;
    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; aNode: TNode);
begin
  ParentNode.Nodes[ParentNode.FSubNodes.Count-1].AddSubNode(ParentNode,aNode);
end;

procedure TNode.AddSubnode(aParentNode: TNode; ANode: TNode);
begin
  aNode.Parent := aParentNode;
  FSubNodes.Add(aNode);
end;

constructor TNode.Create(aParent: TNode; CompareFunc: TCompareFunc; aCaption: String);
var a: Pointer; b: TNode;
begin
  inherited Create;
  FParent := aParent;
  FCaption := aCaption;
  FSubnodes := TNodes.Create;  //Zeiger auf Subnodes als Liste realisiert
  FCompare := @CompareFunc;
end;

destructor TNode.Destroy;
begin
  FSubnodes.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;


{ 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);
begin
  inherited Create;

  FKeyStr := aKeyStr;
  FKey := aKey;
end;

end.

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 }
    function CreateNodes: TNode;
  end;

var
  Form2: TForm2;

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

implementation

{$R *.dfm}

function TForm2.CreateNodes: TNode;
var
  Data: TNodeData; Node: TNode;
begin
  Root.AddSubNode(nil,TNode.Create(Root,CompareStr,'TButton'));

  Root.AddSubnode(nil,TNode.Create(Root,CompareStr,'TEdit'));


  //Data.KeyStr := 'TEdit';

  Root.AddSubnode(nil,TNode.Create(Root,CompareStr,'TGrid'));

  //Node := TNode.Create(CompareStr);

  //Data.KeyStr := 'TGrid';

  Root.AddSubnode(nil,TNode.Create(Root,CompareStr,'TComboBox'));

  Node := TNode.Create(Root,CompareStr,'Zusätzlich');
  Node.AddSubNode(Root,TNode.Create(Root,CompareStr,'TPanel'));
  Node.AddSubnode(Root,TNode.Create(Root,CompareStr,'TTree'));
  Node.AddSubnode(Root,TNode.Create(Root,CompareStr,'TListbox'));
  Result := Node;
end;


procedure TForm2.FormCreate(Sender: TObject);
var i: Integer; D: TNodeData; N: TNode;
begin
  N:=CreateNodes();

  Memo1.Lines.Add(N.Caption);              //Zusätzlich
  //Memo1.Lines.Add(N.Parent.Caption);     //Standard
  //Ausgabe muss später rekursiv erfolgen
  for i := 0 to N.Count-1 do
  begin
    Memo1.Lines.Add(N.Nodes[i].Caption);  //auch hier rekursiv,
                                          //N.Nodes enthält das zuletzt formulierte,
                                          //N.Parent.Nodes das vorherige
  end;

  Memo1.Lines.Add(N.Parent.Caption);
  for i := 0 to N.Parent.Count-1 do
  begin
    Memo1.Lines.Add(N.Parent.Nodes[i].Caption);
  end;

end;

initialization
   Root := TNode.Create(nil,CompareStr,'Standard');

finalization

end.

Funktioniert so erst mal, Danke an Euch alle!

Jetzt guck ich mir Fietes Quellcode noch mal genauer an.

[freimatz]

Gehts eigentlich allgemein um binäre Bäume oder um AVL-Bäume?

[Gausi]

So, wie ich den Verlauf des Threads verstehe, geht es weder um Binärbäume im Allgemeinen, noch um AVL-Bäume. Hier werden Bäume mit beliebigem Knotengrad gebraucht.