考虑通过从叶子构建树来完全不同地构建树。如果您有一个节点队列,则可以从前面取出两个节点,将它们与一个新节点连接在一起,然后将该新节点添加到队列的末尾。重复此操作,直到用完节点,您将获得一个锦标赛分组,其轮数与尝试从根部构建树所获得的轮数相同。
这是构建树的代码and用备忘录中的名字填充叶子。
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;
该代码的好处在于,我们在任何时候都不知道或关心任何特定节点需要处于什么级别。
如果参赛者的数量不是2的幂,那么名单末尾的一些参赛者可能会获得“轮空”回合,他们将被安排与名单顶部的获胜者进行比赛。上面的代码具有最少数量的节点。您的代码可能有许多“垃圾邮件”节点,这些节点并不代表锦标赛中的任何实际比赛。
树对象应该拥有它所包含的节点,因此它应该有一个析构函数,如下所示:
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;
您会注意到我也更改了树的构造函数的调用方式。如果树是空的,则不需要任何节点。如果树不为空,那么我们将在创建它时为其提供节点。
constructor TTree.Create(ARoot: PNode = nil);
begin
inherited;
Root := ARoot;
end;
如果你有机会copy一棵树,那么您还需要复制它的所有节点。如果不这样做,那么当您释放一棵树时,副本的根节点指针将突然变得无效。
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;