I am trying to create a binary tree for use in a knockout tournament. The tree consists of TNodes with Left and Right pointers.
This is the code that I have come up with (below); however, it runs into difficulties with the pointers in the CreateTree section.
Once this creates an empty tree of large enough size, I need to add the names on the Memo1.List to the bottoms of the tree so I can pair them up for matches.
How would I do this?
Type
TNodePtr = ^TNode;
TNode = Record
Data:String;
Left:TNodePtr;
Right:TNodePtr;
end;
Type
TTree = Class
Private
Root:TNodePtr;
Public
Function GetRoot:TNodePtr;
Constructor Create;
end;
var
MyTree:TTree;
function TTree.GetRoot: TNodePtr;
begin
Result:=Root;
end;
Constructor TTree.Create;
Var NewNode:TNodePtr;
Begin
New(NewNode);
NewNode^.Data:='Spam';
NewNode^.Left:=Nil;
NewNode^.Right:=Nil;
End;
Function Power(Base:integer;Exponent:integer):Integer; //Used for only positive powers in this program so does not need to handle negatives.
begin
If Base = 0 then
Power := 0
else If Exponent = 0 then
Power := 1
else //If Exponent > 0 then
Power:=Base*Power(Base, Exponent-1);
end;
Function DenToBinStr(Value:Integer):String;
Var iBinaryBit:integer;
sBinaryString:String;
Begin
While Value <> 0 do
begin
iBinaryBit:=Value mod 2;
sBinaryString:=sBinaryString+IntToStr(iBinaryBit);
Value:=Value div 2;
end;
Result:=sBinaryString;
end;
Procedure TForm1.CreateTree;
Var iRounds, iCurrentRound, iTreeLocation, iNodeCount, iMoreString, iAddedStringLength, iStringTree:Integer;
sBinary:String;
NewNode, ThisNode:TNodePtr;
begin
iRounds:=0;
While Power(2,iRounds) < Memo1.Lines.Count do {Calculates numbers of rounds by using whole powers of 2}
iRounds:=iRounds+1;
If iRounds > 0 then {Make sure there IS a round}
begin
For iCurrentRound:=1 to iRounds do {Select the round we are currently adding nodes to}
begin
iTreeLocation:=Power(2,iCurrentRound); {Works out the number of nodes on a line}
For iNodeCount:= 0 to iTreeLocation do {Selects the node we are currently working on}
begin
ThisNode:=MyTree.GetRoot;
sBinary:=DenToBinStr(iNodeCount); {Gets the tree traversal to that node from the root}
If Length(sBinary) < iCurrentRound then {Makes sure that the tree traversal is long enough, Fills spare spaces with Left because 0 decimal = 0 binary (we need 00 for 2nd round)}
begin
iMoreString:= iCurrentRound-Length(sBinary);
for iAddedStringLength := 0 to iMoreString do
sBinary:='0'+sBinary;
end;
iStringTree:=0; {Init iStringTree, iStringTree is the position along the binary string (alt the position down the tree)}
While iStringTree <= iCurrentRound-1 do {While we are not at the location to add nodes to, move our variable node down the tree}
begin
If sBinary[iStringTree]='0' then
ThisNode:=ThisNode^.Left
else If sBinary[iStringTree]='1' then
ThisNode:=ThisNode^.Right;
iStringTree:=iStringTree+1;
end;
New(NewNode); {Create a new node once we are in position}
NewNode^.Data:='Spam';
NewNode^.Left:=Nil;
NewNode^.Right:=Nil;
If sBinary[iCurrentRound]='0' then
ThisNode^.Left:=NewNode
else If sBinary[iCurrentRound]='1' then
ThisNode^.Right:=NewNode;
ThisNode.Data:='Spam';
Showmessage(ThisNode.Data);
end;
end;
end;
{1.2Add on byes}
{1.2.1Calculate No Of Byes and turn into count. Change each count into binary
equivalent then flip the bits}
//iByes:= Memo1.Lines.Count - Power(2,iRounds);
{1.2.2Add node where 0 is left and 1 is right}
{2THEN FILL TREE using If node.left and node.right does not exist then write
next name from list[q] q++}
{3THEN DISPLAY TREE}
end;