Binärbaum erzeugen und anwenden

[Gargamel]

Hi

Ich habe mich bis jetzt nie mit Binärbäumen auseinandergesetzt, wollte das jetzt aber nachholen. Dazu habe ich etwas Code geschrieben und möchte von Euch wissen, ob ich das Prinzip auch richtig verstanden habe.
(auf Copy&Paste habe ich aus gutem Grund verzichtet :thumb:)

Und das ist der Quelltext:

Delphi-Quellcode:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Label1: TLabel;
    Button1: TButton;
    Label2: TLabel;
    Label3: TLabel;
    procedure Button1Click(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

  PNode = ^TNode;
  TNode = record
    name:string;
    ChildNode1,ChildNode2:PNode;
    ParentNode:PNode;
  end;


var
  Form1: TForm1;

  Node1,ChildNode1,ChildNode2:PNode;
  SubChild1,SubChild2:PNode;


implementation

{$R *.dfm}

procedure createBinaryTree();
var Name:string;
Begin
  // Zeiger erzeugen
  new(Node1);
  new(ChildNode1);
  new(ChildNode2);
  new(SubChild1);
  new(SubChild2);

  // den Knoten zu Überprüfungszwecken einen Namen geben
  Node1.name:='Wurzel';
  ChildNode1.name:='ChildNode1';
  ChildNode2.name:='ChildNode2';
  SubChild1.name:='SubChild1';
  SubChild2.name:='SubChild2';

  // Node1 ist die Wurzel... daran hängen die Kinderknoten ChildNode1 und ChildNode2
  Node1.ParentNode:=nil;
  Node1.ChildNode1:=ChildNode1;
  Node1.ChildNode2:=ChildNode2;

  ChildNode1.ParentNode:=Node1;
  ChildNode2.ParentNode:=Node1;

  // SubChild1 ist der Kinderknoten von ChildNode1
  ChildNode1.ChildNode1:=SubChild1;
  SubChild1.ParentNode:=ChildNode1;

  // SubChild2 ist der Kinderknoten von SubChild1
  SubChild1.ChildNode1:=SubChild2;
  SubChild2.ParentNode:=SubChild1;

  // Name des Wurzelknotens ermitteln
  Name:=ChildNode1.ParentNode.name;
  Form1.Label1.Caption:=Name;
End;

procedure destroyBinaryTree();
Begin
  // Speicherbereich der Zeiger wieder freigeben
  Dispose(Node1);
  Dispose(ChildNode1);
  Dispose(ChildNode2);
  Dispose(SubChild1);
  Dispose(SubChild2);
End;

function getRootNode(Child:PNode):PNode;
Begin
  // den Baum solange nach oben durchlaufen, bis die Wurzel erreicht wurde
  while Child.ParentNode<>nil do
    Child:=Child.ParentNode;

  result:=Child;
End;

function getParentNode(Child:PNode):PNode;
Begin
  // den Elternknoten eines gegebenen Knotens ermittelb
  if Child.ParentNode<>nil then
    Begin
      result:=Child.ParentNode;
      exit;
    End;

  result:=nil;
End;

procedure TForm1.Button1Click(Sender: TObject);
var parent:PNode;
begin
  createBinaryTree();
  Label2.Caption:=getRootNode(SubChild2).name;

  parent:=getParentNode(SubChild1);
  if parent<>nil
    then
      Label3.Caption:=parent.name
    else
      Label3.Caption:='Dieser Knoten hat keinen Elternknoten';


  destroyBinaryTree();
end;

end.

[Gargamel]

Kleiner Zusatz:

Um den Nachbarknoten herauszufinden, sofern vorhanden, müßte der Code dann so aussehen:

Delphi-Quellcode:

function isRootNode(Node:PNode):boolean;
Begin
  if Node.ParentNode=nil then
  Begin
    result:=true; exit;
  End;
  result:=false;
End;

function getNeighborNode(node:PNode):PNode;
var parent:PNode;
Begin
  // die Wurzel hat keinen Nachbarknoten
  if isRootNode(node) then
  Begin
    result:=nil; exit;
  End;

  // Zeiger miteinander vergleichen
  parent:=node.ParentNode;
  if node=parent.ChildNode1 then
  Begin
    result:=parent.ChildNode2; exit;
  End else
    if node=parent.ChildNode2 then
    Begin
      result:=parent.ChildNode1; exit;
    End;

  result:=nil;
End;