AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Binärbaum erzeugen und anwenden

Ein Thema von Gargamel · begonnen am 25. Jan 2012 · letzter Beitrag vom 25. Jan 2012
Antwort Antwort
Gargamel

Registriert seit: 19. Mär 2007
171 Beiträge
 
#1

Binärbaum erzeugen und anwenden

  Alt 25. Jan 2012, 11:58
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 )

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.
  Mit Zitat antworten Zitat
Gargamel

Registriert seit: 19. Mär 2007
171 Beiträge
 
#2

AW: Binärbaum erzeugen und anwenden

  Alt 25. Jan 2012, 12:34
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;
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 08:56 Uhr.
Powered by vBulletin® Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf