Hallo!
Could someone please help me? I need to program ADS union-find in Delphi. How could I add nodes in a tree, which has this structure:
1. Every item is in a tree.
2. The root of the tree is the representative item of all items in that tree. i.e., the root of the tree represents the whole items.
3. In this up-tree implementation, every node (except the root) has a pointer pointing to its parent.
The root element has a pointer pointing to itself (or nil).
Delphi-Quellcode:
___________
interface :
___________
TNode = class
parent : TNode;
value : integer;
constructor Create(i : integer);
end;
TTree = class
root : TNode;
constructor Create(i : integer);
procedure add(item : integer);
end;
TUnionFind = class
root : TTree;
parent : TUnionFind;
size : integer;
name : String;
constructor Create(s : string);
end;
function Union(X, Y : TUnionFind) : TUnionFind;
_________________
implementation :
_________________
function Find_Set(X : TUnionFind) : TUnionFind;
begin
while (X <> X.parent) do
X := X.parent;
Result := X;
end;
function Union(X, Y : TUnionFind) : TUnionFind;
var
A, B : TUnionFind;
begin
A := Find_Set(X);
B := Find_Set(Y);
if (A.size <= B.size) then
begin
if (A.size = B.size) then
inc(B.size);
A.parent := b;
Result := A;
end else
begin
B.parent := A;
Result := B;
end;
end;
Danke schoen
[edit=SirThornberry]Delphi-Tags korrigiert - Mfg, SirThornberry[/edit]