Создание бинарного дерева для турнира на выбывание

Question

Я пытаюсь создать бинарное дерево для использования в турнире на выбывание. Дерево состоит из TNodes с указателями влево и вправо.

Это код, который я придумал (ниже); однако, он сталкивается с трудностями с указателями в разделе 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;

Что хорошо в этом коде, так это то, что мы ни в коем случае не знаем и не заботимся о том, на каком уровне должен находиться какой-либо конкретный узел.

Если число участников не является степенью двойки, то некоторые из участников в конце списка могут получить раунд "до свидания", и им будет назначено сыграть победителей в верхней части списка. , Код выше имеет минимальное количество узлов. В вашем коде может быть несколько «спамовых» узлов, которые не представляют никакого фактического совпадения в турнире.

Объект дерева должен владеть узлами, которые он содержит, поэтому у него должен быть деструктор, такой как:

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;

РЕДАКТИРОВАТЬ: 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;