为淘汰赛创建二叉树

Question

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

这是我想出的代码（如下）；但是，它在使用 CreateTree 部分中的指针时遇到了困难。

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

我该怎么做？

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;

Answer 1

考虑通过从叶子构建树来完全不同地构建树。如果您有一个节点队列，则可以从前面取出两个节点，将它们与一个新节点连接在一起，然后将该新节点添加到队列的末尾。重复此操作，直到用完节点，您将获得一个锦标赛分组，其轮数与尝试从根部构建树所获得的轮数相同。

下面的代码构建了树并用备忘录中的名称填充叶子。

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;

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

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;

Answer 2

我实际上已经成功地重写了我的原始代码以使其单独工作。它似乎在此时此刻发挥作用。
这是我现在正在使用的程序。谢谢罗布，我将把你的作为答案，因为它看起来对我来说会更好，我会仔细查看它以了解我能学到的东西，但为了避免不必要地使用其他代码，我现在将使用我自己的代码。

    Procedure TForm1.CreateTree;
Var  iRounds, iCurrentRound, iCurrentNode, iTraverseToNode:integer;
        sBinary:String;
        ThisNode, NewNode, NextNode: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
        begin
                for iCurrentRound:=1 to iRounds do
                begin
                        for iCurrentNode:=0 to power(2,iCurrentRound)-1 do
                        begin
                                NextNode:=MyTree.GetRoot;
                                ThisNode:=NextNode;
                                New(NewNode);
                                NewNode.Data:='';
                                NewNode.Left:=Nil;
                                NewNode.Right:=Nil;
                                sBinary:=DenToBinStr(iCurrentNode);
                                if sBinary = '' then
                                        sBinary:='0';
                                While length(sBinary)>iCurrentNode+1 do
                                begin
                                        sBinary:='0'+sBinary;
                                end;
                                for iTraverseToNode:=1 to length(sBinary)-1 do
                                While NextNode <> nil do
                                begin
                                        if sBinary[iTraverseToNode] = '0' then
                                        begin
                                                ThisNode:=NextNode;
                                                NextNode:=NextNode.Left;
                                        end
                                        else if sBinary[iTraverseToNode] = '1' then
                                        begin
                                                ThisNode:=NextNode;
                                                NextNode:=NextNode.Right;
                                        end
                                end;
                                if sBinary[iCurrentNode+1] = '0' then
                                        ThisNode^.Left:=NewNode
                                else if sBinary[iCurrentNode+1] = '1' then
                                        ThisNode^.Right:=NewNode
                                else
                                        Showmessage('TooFar');
                                        break;
                        end;
                end;
        end;
end;

编辑：2010年3月3日
我找到了一种更好、更简单的递归方法。

    Procedure RecursiveTree(r:integer; ThisNode: TNodePtr);
Var NewNode:TNodePtr;
begin
        If (NOT assigned(ThisNode.Left)) and (r<>0) then
        begin
                New(NewNode);
                NewNode.Left:=Nil;
                NewNode.Right:=Nil;
                NewNode.Data:='';
                ThisNode.Left:=NewNode;
                RecursiveTree(r-1,ThisNode.Left);
        end;
        If (NOT assigned(ThisNode.Right)) and (r<>0) then
        begin
                New(NewNode);
                NewNode.Left:=Nil;
                NewNode.Right:=Nil;
                NewNode.Data:='';
                ThisNode.Right:=NewNode;
                RecursiveTree(r-1,ThisNode.Right);
        end;
end;