StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Think about building the tree differently altogether by building it from the leaves. If you have a queue of nodes, you can take two nodes off the front, join them together with a new node, and add that new node to the end of the queue. Repeat until you run out of nodes, and you'll have a tournament bracket with the same number of rounds you'd get from trying to build the tree from the root.</p> <p>Here's code that builds the tree <em>and</em> fills the leaves with names from the memo.</p> <pre><code>var Nodes: TQueue; Node: PNode; s: string; begin Nodes := TQueue.Create; try // Build initial queue of leaf nodes for s in Memo1.Lines do begin New(Node); Node.Data := s; Node.Left := nil; Node.Right := nil; Nodes.Push(Node); end; // Link all the nodes while Nodes.Count > 1 do begin New(Node); Node.Left := Nodes.Pop; Node.Right := Nodes.Pop; Nodes.Push(Node); end; Assert((Nodes.Count = 1) or (Memo1.Lines.Count = 0)); if Nodes.Empty then Tree := TTree.Create else Tree := TTree.Create(Nodes.Pop); finally Nodes.Free; end; end; </code></pre> <p>What's nice about that code is that at no point do we know or care what level any particular node needs to be at.</p> <p>If the number of competitors is not a power of two, then some of the competitors at the end of the list may get a "bye" round, and they'll be scheduled to play the winners at the top of the list. The code above has a minimal number of nodes. Your code may have a number of "spam" nodes that don't represent any actual match in the tournament.</p> <p>The tree object should own the nodes it contains, so it should have a destructor, like this:</p> <pre><code>destructor TTree.Destroy; procedure FreeSubnodes(Node: PNode); begin if Assigned(Node.Left) then FreeSubnodes(Node.Left); if Assigned(Node.Right) then FreeSubnodes(Node.Right); Dispose(Node); end; begin FreeSubnodes(Root); inherited; end; </code></pre> <p>You'll notice I changed how the tree's constructor is called, too. If the tree is empty, it doesn't need to have any nodes. If the tree isn't empty, then we'll supply it with its nodes when we create it.</p> <pre><code>constructor TTree.Create(ARoot: PNode = nil); begin inherited; Root := ARoot; end; </code></pre> <p>If you have occasion to <em>copy</em> a tree, then you'll need to copy all its nodes, too. If you don't, then when you free one tree, the copy's root-node pointer will suddenly become invalid.</p> <pre><code>constructor TTree.Copy(Other: TTree); function CopyNode(Node: PNode): PNode; begin if Assigned(Node) then begin New(Result); Result.Data := Node.Data; Result.Left := CopyNode(Node.Left); Result.Right := CopyNode(Node.Right); end else Result := nil; end; begin inherited; Root := CopyNode(Other.Root); 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