In the VCL contains a TLIST class, almost all functions of
Code instance:
Procedure test ();
VAR
Yutree: TYUTREE;
TYUNODE;
Begin
// Step 1: Create a tree, add the first node 0
Yutree: = TYUTREE.CREATE;
Node: = yutree.add (nil); // nil, indicating an increase in root node
Node.Data: = POINTER (0);
// Step 2: Add sub-node 1 at node 0 1
Node: = yutree.addchild (node); Node pointing node 0
Node.Data: = POINTER (1);
// Step 3: Add sub-node 2 at node 1 2
= Yutree.addchild (node);
Node.Data: = POINTER (2);
// Step 4: Switch to the Father Node 1 of Node 2 1
Node: = node.getparent;
// Step 5: Add sub-node 3 under node 1 and as the first sub-node
Node: = yutree.addchildfirst (node);
Node.Data: = POINTER (3);
// Step 6: Switch to the Father Node 1 of Node 3 1
Node: = node.getparent;
// Step 7: Increase the node 4 Node 4, as the last sub-node
= Yutree.addchild (node);
Node.Data: = POINTER (4);
// Step 8: Increase the brothers of the node 4 5, as the first brother node
= Yutree.addfirst (node);
Node.Data: = POINTER (5);
// t Step 9: Switch to the next brothers of the node 5 3
Node: = node.getnextbrother;
// Step 10: Insert a brother node 6 under the node 3 6
= Yutree.add (node);
Node.Data: = POINTER (6);
// Step 11: Delete Node 6
Node.delete; // or yutree.delete (node);
/ / Other usage
// Node 2.Getnextbrother () = NonPoint 4 Return to the next brother
// Non-Node 2.GetPrevbrother () = Node 3 Return to the previous brother
// Node 1.GetFirstChild () = Node 5; return to the first sub-node of this node
// Node 1. GetlastChild () = Nonpode 4 Returns the last sub-node of this node
// Node 1.GetNext = Node 5
// Node 1.Getprev = Node 0
// Nonp 5.Getfirstbrother () = Node 5 Returns the first brother of this node
// Nonp 5.Getlastbrother () = NonPoint 4 Returns the last brother
//Yutree.firstnode = Node 0
//Yutree.clear (); empty all nodes
END;
Description: This is represented by a binary tree in a program, and FDOWNLEFT, FDOWNRIGHT represents the left pointer of the binary tree, respectively, and the right pointer. The original code is as follows:
//------Start----------------------------
Unit uYutree;
Interface
Type
TyunodeAttachMode = (YNAADD, YNAADDFirst, Ynaaddchild, YnaAaddChildfirst, Ynainsert);
TYUTREE = Class;
TYUNODE = Class (TOBJECT)
Private
In addition to root, fupleft, fupright, in addition to ROOT, only one is empty
Fupleft: Tyunode; //self.fupleft.fdownleft = Self (the node pointing to the pointer is the result of the node)
FUPRIGHT: TYUNODE; //self.fupright.fdownright = Self (The node pointing to this pointer is the last brother of this node)
FDOWNLEFT: TYUNODE; // The left pointer of the binary tree, the child of the table tree
FDOWNRIGHT: TYUNODE; // The right pointer of the binary tree indicates the next brother of the tree.
FOWNER: TYUTREE;
// Status information
FDELETING: Boolean;
Fisrootofdeleted: Boolean;
Function Getlevel (): Integer;
Function getParent (): TYUNODE;
Procedure cutfromtree ();
protected
Constructor Create (Aowner: Tyutree);
public
// Property Data: Pointer Read FData Write FDATA;
DATA: POINTER;
// The following four functions are basic functions, do not call other functions, complete the specified function independently
Function getNextbrother (): Tyunode;
Function getPrevbrother (): Tyunode;
Function getFirstchild (): Tyunode;
Function getLastchild (): Tyunode;
Function GetNext: Tyunode;
Function getPrev: Tyunode;
Function getFirstbrother (): Tyunode;
Function getLastbrother (): Tyunode;
Procedure Moveto (Destination: Tyunode; Mode: TyunodeAttachmode);
Procedure delete ();
Property Level: Integer Read Getlevel;
Property Parent: Tyunode Read GetParent;
DEStructor destroy (); OVERRIDE;
END;
TYUTREE = Class (TOBJECT)
Private
FFirstnode: Tyunode;
public
Function Add (Brother: Tyunode): TYUNODE
Function AddFirst (Brother: Tyunode): Tyunode;
Function AddChild (Parent: Tyunode): Tyunode;
Function addChildFirst (Parent: Tyunode): Tyunode;
Function Insert (Brother: Tyunode): Tyunode; Procedure Clear ();
Procedure delete (Node: Tyunode);
Property Firstnode: Tyunode Read FfirstNode;
Constructor crete ();
DEStructor destroy (); OVERRIDE;
END;
IMPLEMENTATION
Uses sysutils, math;
{TYUNODE}
Constructor Tyunode.create (Aowner: Tyutree);
Begin
IF not assigned (aowner) THEN
Raise Exception.create ('aowner is nil in typeode.create');
FOWNER: = aowner;
FUPLEFT: = NIL;
FUPRIGHT: = NIL;
FDOWNLEFT: = NIL;
FDOWNRIGHT: = NIL;
FDELETING: = false;
Fisrootofdeled: = false;
END;
Destructor Tyunode.destroy;
VAR
Subnode, WillDeletenode: Tyunode;
Begin
FDELETING: = true;
If Fisrootofdeleted Then // Maintenance Pointer
Cutfromtree;
Subnode: = getFirstChild;
While Subnode <> NIL DO
Begin
WillDeletenode: = Subnode;
Subnode: = Subnode.getNextbrother;
Willdeletenode.free;
END;
inherited;
END;
Function Tyunode.GetfirstChild: Tyunode;
Begin
Result: = fdownleft;
END;
Function Tyunode.Getfirstbrother: Tyunode;
Begin
Result: = Self;
While Result.GetPrevbrother <> NIL DO
Result: = Result.getPrevbrother;
END;
Function Tyunode.getlastbrother: TYUNODE;
Begin
Result: = Self;
While Result.getNextbrother <> NIL DO
Result: = Result.getNextbrother;
END;
Function Tyunode.getlastChild: Tyunode;
Begin
Result: = fdownleft;
IF results = nil dam
While Result.fdownRight <> NIL DO
Result: = Result.fdownRight;
END;
Function Tyunode.getlevel: Integer;
VAR
TYUNODE;
Begin
= Self;
RESULT: = -1;
Repeat
Node: = node.parent;
Inc (Result);
Until Node = NIL;
END;
Function Tyunode.getNext: Tyunode;
VAR
TYUNODE;
Begin // 1. View the first sub-node
Result: = getFirstChild;
// 2. If the first step is not successful, check the next brother
if Result = nil dam
Result: = getNextbrother;
// 3. If the second step is unsuccessful, check the next brother of the father's node
// Exit the conditions, successfully found (Result <> nil) or until the root point is still found (Node = NIL)
= Self.parent;
While (result = nil) and (node <> nil) do
Begin
Result: = node.getNextbrother;
Node: = node.parent;
END;
END;
Function Tyunode.getNextbrother: Tyunode;
Begin
RESULT: = fdownright;
END;
Function Tyunode.getParent: TYUNODE;
Begin
Result: = getfirstbrother.fupleft;
END;
Function Tyunode.getPREV: Tyunode;
VAR
TYUNODE;
Begin
// 1. Get a brother
= GetPrevbrother;
// If there is no brother, return to the parent node
IF node = nil dam
Begin
Result: = Self.Parent;
EXIT;
END;
/ / Otherwise, return prevbrother.getLastchild.getlastChild .........
Result: = node;
While Node <> NIL DO
Begin
Result: = node;
Node: = node.getlastchild;
END;
END;
Function Tyunode.getPrevbrother: Tyunode;
Begin
Result: = fupright;
END;
Procedure Tyunode.moveto (Destination: Tyunode; Mode: TyunodeAttachmode);
VAR
Destparent, Addnode: Tyunode;
Begin
IF destination = nil dam
Begin
Delete;
EXIT;
END;
IF Destination.fowner <> fowner then
Raise Exception.createfmt ('Yunode [@% d] move to another tree in typeode.moveto', [integer (@seelf)]);
Destparent: = destination.parent;
While destParent <> NIL DO
Begin
IF destParent = Self the
Raise Exception.createfmt ('Destination IS Yunode [@% d]' 's subnode in typeode.moveto', [Integer (@seelf)]);
Destparent: = destparent.parent;
END;
Cutfromtree;
Case Mode of
YNAADD: addnode: = fowner.add (destination);
YNAAdDfirst: addnode: = fowner.addfirst (destination); ynaaddchild: addnode: = fowner.addchild (destination);
YNAADDCHILDFIRST: AddNode: = fowner.addchildfirst (destination);
YNAINSERT: AddNode: = Fowner.insert (Destination);
END;
Fupleft: = addnode.fupleft;
FUPRIGHT: = addnode.fupright;
FDOWNRIGHT: = addNode.fdownRight;
If FUPLEFT <> NIL1 FUPLEFT.FDOWNLEFT: = Self;
IF FUPRIGHT <> NIL THEN FUPRIGHT.FDOWNRIGHT: = Self;
If FDONRIGHT <> NIL TEN FDOWNRIGHT.FUPRIGHT: = Self;
AddNode.Free;
END;
Procedure Tyunode.delete;
Begin
IF not fdeleting then
Begin
Fisrootofdeled: = true;
FREE;
END;
END;
Procedure Tyunode.cutfromtree;
Begin
IF self = fowner.ffirstnode then
Begin
FOWNER.ffirstnode: = getNextbrother;
If FOWNER.ffirstnode <> nil dam
FOWNER.ffirstnode.fupright: = NIL;
EXIT;
END;
If FDOWNRIGHT <> nil dam // has a next brother
If FUPRIGHT <> nil dam // has a brother
Begin
FUPRIGHT.FDOWNRIGHT: = fdownright;
FDOWNRIGHT.FUPRIGHT: = fupright;
end
Else // direct point to the father
Begin
FUPLEFT.FDOWNLEFT: = FDOWNRIGHT;
FDOWNRIGHT.FUPRIGHT: = NIL;
FDOWNRIGHT.FUPLEFT: = fupleft;
end
Else
If FUPRIGHT <> nil dam // has a brother
FUPRIGHT.FDOWNRIGHT: = NIL
Else // direct point to the father
FUPLEFT.FDOWNLEFT: = NIL;
END;
{TYUTREE}
Function Tyutree.Add (Brother: Tyunode): TYUNODE
VAR
TYUNODE;
Begin
IF brother = nil dam
IF ffirstnode = nil then
Begin
Result: = TYUNODE.CREATE (Self);
FfirstNode: = Result;
EXIT;
end
Else
Brother: = ffirstnode;
= Brother.getlastbrother;
Result: = TYUNODE.CREATE (Self);
Node.fdownright: = Result; Result.Fupright: = node;
END;
Function Tyutree.Addchild (Parent: Tyunode): Tyunode;
VAR
TYUNODE;
Begin
IF pent = nil then
Begin
Result: = add (nil);
EXIT;
END;
Node: = parent.getlastchild;
Result: = TYUNODE.CREATE (Self);
IF node = nil dam
Begin
Parent.fdownleft: = result;
Result.Fupleft: = Parent;
end
Else
Begin
Node.fdownright: = Result;
Result.fupright: = node;
END;
END;
Function Tyutree.AddchildFirst (Parent: Tyunode): Tyunode;
VAR
TYUNODE;
Begin
IF pent = nil then
Begin
Result: = add (nil);
EXIT;
END;
Node: = parent.getfirstchild;
Result: = TYUNODE.CREATE (Self);
IF node <> nil kil
Begin
Node.Fupleft: = NIL;
Node.fupright: = Result;
END;
Result.Fupleft: = Parent;
Result.fdownright: = node;
Parent.fdownleft: = result;
END;
Function Tyutree.AddFirst (Brother: Tyunode): Tyunode;
VAR
Node, Parent: TYUNODE;
Begin
IF brother = nil dam
Begin
Result: = add (nil);
EXIT;
END;
= Brother.getfirstbrother;
Parent: = node.parent;
Result: = TYUNODE.CREATE (Self);
Node.Fupleft: = NIL;
Node.fupright: = Result;
Result.Fupleft: = Parent;
Result.fdownright: = node;
IF pent <> nil kil
Parent.fdownleft: = result
Else
FfirstNode: = Result;
END;
PROCEDURE TYUTREE.CLEAR;
Begin
While FfirstNode <> NIL DO
FfirstNode.delete;
END;
Constructor Tyutree.create;
Begin
FfirstNode: = NIL;
END;
Procedure Tyutree.delete (Node: Tyunode);
Begin
Node.delete;
END;
DESTRUCTOR TYUTREE.DESTROY;
Begin
Clear;
inherited;
END;
Function Tyutree.Insert (Brother: Tyunode): Tyunode;
VAR
Prev, Next: Tyunode; Begin
IF brother = nil dam
Begin
Result: = add (nil);
EXIT;
END;
If brother.getnextbrother = nil dam
Result: = add (brother)
Else
Begin
Prev: = Brother;
Next: = Brother.getNextbrother;
Result: = TYUNODE.CREATE (Self);
Prev.fdownRight: = Result;
Next.fupright: = Result;
Result.fupright: = prev;
Result.fdownright: = next;
END;
END;
End.
//------end----------------------------
