2

我正在尝试创建用于淘汰赛的二叉树。该树由具有左右指针的 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;
4

2 回答 2

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;
于 2010-02-22T09:28:44.643 回答
0

我实际上已经设法重写了我的原始代码以使其单独工作。它似乎在此时起作用。这是我现在使用的程序。谢谢Rob，我会把你的设置为答案，因为它看起来对我来说会更好，我会查看它以了解我能做什么，但为了避免不必要地使用其他代码，我现在将使用我自己的.

    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;

编辑：03/03/2010 我发现了一种更好更简单的递归方式。

    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;
于 2010-02-22T11:42:19.477 回答