StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POCreating a Binary Tree for a Knockout Tournament
text
Body
copied!<p>I am trying to create a binary tree for use in a knockout tournament. The tree consists of TNodes with Left and Right pointers.</p> <p>This is the code that I have come up with (below); however, it runs into difficulties with the pointers in the <code>CreateTree</code> section.</p> <p>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.</p> <p>How would I do this?</p> <pre><code>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; </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload