为淘汰赛创建二叉树 [英] Creating a Binary Tree for a Knockout Tournament

查看:92
本文介绍了为淘汰赛创建二叉树的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我正在尝试创建用于淘汰赛的二叉树.该树由带有左右指针的TNode组成.

I am trying to create a binary tree for use in a knockout tournament. The tree consists of TNodes with Left and Right pointers.

这是我想出的代码(如下);但是,使用CreateTree部分中的指针会遇到困难.

This is the code that I have come up with (below); however, it runs into difficulties with the pointers in the CreateTree section.

一旦这创建了一个足够大的空树,我需要将Memo1.List上的名称添加到树的底部,以便将它们配对以进行匹配.

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.

我该怎么做?

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;

推荐答案

通过从叶子上构建树来考虑完全不同地构建树.如果您有一个节点队列,则可以将两个节点放在最前面,将它们与新节点连接在一起,然后将该新节点添加到队列的末尾.重复进行,直到节点用完为止,您将获得一个锦标赛括号,其中的回合数与尝试从根目录构建树所获得的回合数相同.

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.

这里的代码构建树用备忘录中的名称填充叶子.

Here's code that builds the tree and fills the leaves with names from the memo.

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;

该代码的优点在于,我们一点也不知道或关心任何特定节点需要处于什么级别.

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.

如果竞争者的数量不是2的幂,那么位于列表末尾的某些竞争者可能会进行再见"回合,并且将安排他们与列表顶部的优胜者进行比赛.上面的代码具有最少数量的节点.您的代码中可能有许多垃圾邮件"节点,这些节点不代表锦标赛中的任何实际比赛.

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.

树对象应该拥有它包含的节点,因此它应该有一个析构函数,如下所示:

The tree object should own the nodes it contains, so it should have a destructor, like this:

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;

您会注意到我也更改了树的构造函数的调用方式.如果树为空,则不需要任何节点.如果树不为空,则在创建树时将为其提供节点.

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.

constructor TTree.Create(ARoot: PNode = nil);
begin
  inherited;
  Root := ARoot;
end;

如果您有机会复制一棵树,那么您还需要复制其所有节点.如果不这样做,那么当您释放一棵树时,副本的根节点指针将突然变得无效.

If you have occasion to copy 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.

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;

这篇关于为淘汰赛创建二叉树的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆