Wie bastelt man nen baum (pascal)

Computer: Software & Programmierung Programmierung allgemein
#1

hallo,

mal ne frage, wie kann man in pascal einen baum erstellen und ihn wie eine verzeichnisstruktur „durchkämmen“
wenn ein knoten zb so definiert ist ?

PNode = ^TNode
TNode = record
zero,one : PNode;
data : Byte;
count : LongInt;
IsAtEnd : Boolean;
end;

thanx dennis

#2

Das ist ganz einfach.
Der Verständlichkeit halber würde ich aber den Knoten erstmal einfacher definieren:

PNode = ^TNode
TNode = record
_next: PNode;
_data: Byte;
end;

Eine einfache Liste anlegen:

var First,Node: PNode;

New(First);
Node := First;
Node^.Next:=nil;
Node^.Data:=…

for i = 1 to Anzahl-1 do begin
__New(Node.Next);
__Node := Node.next;
__Node^.Next:=nil;
__Node^.Data:=…
end;

Über den Zeiger First findest du immer den Anfang der Liste. Wenn du dann z.B. den Knoten suchst, bei welchem Data = x ist, kannst du das so machen:

Node := First;
while (NodeNIL) and (Node.Datax) do Node := Node.next;
Gefunden := (NodeNIL);

Für eine vorwärts- und rückwärts verkettete Liste benötigt dein TNode-Record noch ein Feld prev:stuck_out_tongue:Node. Die Erstellung sieht dann so aus:

var First,Node: PNode;

New(First);
Node := First;
Node^.Next:=nil;
Node^.Prev:=nil;
Node^.Data:=…

for i = 1 to Anzahl-1 do begin
__New(Node^.Next);
__Node^.next^.prev := Node; {neu!}
__Node := Node.next;
__Node^.Next:=nil;
__Node^.Data:=…
end;

Wenn du die Kette zu einem Ring schließen möchtest:

Node^.next:=First;
First^.prev:=Node;

Wenn du einen Knoten an Pos. n einfügen möchtest:

Var Insert:stuck_out_tongue:Node;

Node := First;
for i:=1 to n do Node:=Node^.next;
New(Insert);
Insert^.next:=Node;
Insert^.prev:=Node.prev;
Node^.prev^.next := Insert;
Node^.prev := Insert;

Löschen geht so:

Node := First;
for i:=1 to n do Node:=Node^.next;
node^.prev^.next := node^.next;
node^.next^.prev := node^.prev;
dispose(Node);

Gut. Einen Baum, sagen wir einen binären Baum würdest du so bauen können:

PNode = ^TNode
TNode = record
_left, right: PNode;
_data: Byte;
end;

const maxLevel = 10;
var Level: Integer;

Procedure AddNode(NewNode:stuck_out_tongue:Node);
begin
__New(NewNode);
__NewNode.Left := nil;
__NewNode.right := nil;
__NewNode.Data := …
__inc(Level)
__if Level

#3

ich meinte allerdings einen verschieden verzweigten „baum“ immer ein ast 0 und ein 1 !
zb ein verzeichnisbaum, indem jedes verzeichnis bis zu 2 verzeichnisse haben kann.
so ungefähr kann man sich das vorstellen.
aber ergal, ich hab jetz ne idee wie ichs machen kann !!! DANKE !!! :smile:

dennis