树形数据结构(用于VirtualTreeview)

3

我已经到了需要停止在VCL组件中存储数据并拥有"底层数据结构"的地步,正如Rob Kennedy先生建议的那样。

首先,这个问题是关于如何创建一个"底层数据结构"的。 :)

我的层次结构由2级节点组成。

目前,我通过循环根节点,在其中循环遍历根节点的子节点来获取所需的内容(数据)。我希望能够将所有的数据存储在所谓的"底层数据结构"中,以便我可以轻松使用线程修改条目(我想我能做到吗?)

然而,当遍历我的条目时(现在),结果取决于节点的检查状态 - 如果我使用底层数据结构,当我遍历数据结构而不是节点时,我怎么知道我的节点是否被选中呢?

假设我想使用两个级别。

这将是父级:

TRoot = Record
  RootName : String;
  RootId : Integer;
  Kids : TList; //(of TKid)
End;

同时,这里有一个孩子:

TKid = Record
  KidName : String;
  KidId : Integer;
End;

这基本上就是我现在所做的。评论表明这不是最好的解决方案,因此我愿意听取建议。:)

希望您能理解我的问题。:)

谢谢!


3
@Jeff,就我看来,如果没有读过你之前的问题,你的问题对于任何人来说都很难理解。如果可以的话,请提供链接(或者最后手段)。但更好的做法是,把每个问题都写成独立的问题,这样其他人即使没有阅读之前的问题也能轻松回答,而且对于未来的读者来说更易懂。 - jachguate
1
@Jeff:不要误会,但如果我没记错的话,你是一名初学者程序员——但如果你继续学习,几年后你将能够以更高级的水平掌握编程。然而,在那之前,我认为明智的做法是在有更简单的替代方案时不要尝试过于困难的事情。你真的确定不能使用 TListBox 吗?我的意思是,如果你需要一个更高级的控件来显示你的数据,比如 Virtual TreeView,你应该首先在某些“底层数据结构”中拥有数据。 - Andreas Rejbrand
1
这个问题看起来很有用:https://dev59.com/8UrSa4cB1Zd3GeqPX6LC - David Heffernan
@David - 如果我的解决方案能够按照预期和我所需的工作,那我不觉得需要添加更多的功能,对吧? :) 不,说实话我还没有读过任何东西。 - Jeff
1
@Jeff,即使你得到了一个可行的答案,立即接受答案既不符合你的最佳利益,也不符合社区的最佳利益。除非问题非常简单,否则你应该等待一两天才能接受答案:也许会出现更好的答案!事实上,这种问题从多个答案中受益。例如,今天早上我看到了这个问题,没有时间处理它,当我回来时,我看到了一个建议使用数据库的答案的勾号。我讨厌人们推荐数据库,好像它们是万灵药一样。 - Cosmin Prund
显示剩余10条评论
6个回答

10
您请求的数据结构非常简单,它非常简单,我建议使用Windows提供的TTreeView:它允许在树节点中直接存储文本和ID,无需进行其他操作。
尽管我建议使用更简单的TTreeView,但我将提供我的解决方案。首先,我将使用类而不是记录。在您非常短的代码示例中,您以非常不幸的方式混合了记录和类:当您复制TRoot记录时(分配记录会完全复制,因为记录始终被视为“值”),您并未制作树的“深层复制”:完整的TRoot副本将包含与原始记录相同的Kids:TList,因为类不同于记录,是引用:您正在复制引用的值。
当记录具有对象字段时,另一个问题是生命周期管理:记录没有析构函数,因此您需要另一种机制来释放所拥有的对象(Kids:TList)。您可以将TList替换为array of Tkid,但是这时候在传递大型记录时需要非常小心,因为您可能会在最不希望出现的时候进行巨大记录的深层复制。
在我看来,最谨慎的做法是基于类而不是记录构建数据结构:类实例(对象)作为引用传递,因此您可以尽情地移动它们而没有问题。您还获得了内置的生命周期管理(析构函数)。
基类如下所示。您会注意到它既可以用作根也可以用作Kid,因为Root和Kid共享数据:它们都有一个名称和一个ID:
TNodeClass = class
public
  Name: string;
  ID: Integer;
end;

如果这个类被用作根节点,它需要一种存储孩子的方式。假设你使用的是Delphi 2010或更高版本,那么你可以使用泛型。这个类,包含一个列表,看起来像这样:
type
  TNode = class
  public
    ID: integer;
    Name: string;
    VTNode: PVirtualNode;
    Sub: TObjectList<TNode>;

    constructor Create(aName: string = ''; anID: integer = 0);
    destructor Destroy; override;
  end;

constructor TNode.Create(aName:string; anID: Integer);
begin
  Name := aName;
  ID := anID;

  Sub := TObjectList<TNode>.Create;
end;

destructor TNode.Destroy;
begin
  Sub.Free;
end;

您可能不会立即意识到这一点,但是仅此类就足以实现多级树!以下是一些代码来填充树状结构的数据:

Root := TNode.Create;

// Create the Contacts leaf
Root.Sub.Add(TNode.Create('Contacts', -1));
// Add some contacts
Root.Sub[0].Sub.Add(TNode.Create('Abraham', 1));
Root.Sub[0].Sub.Add(TNode.Create('Lincoln', 2));

// Create the "Recent Calls" leaf
Root.Sub.Add(TNode.Create('Recent Calls', -1));
// Add some recent calls
Root.Sub[1].Sub.Add(TNode.Create('+00 (000) 00.00.00', 3));
Root.Sub[1].Sub.Add(TNode.Create('+00 (001) 12.34.56', 4));

您需要一个递归程序来填充虚拟树视图,使用此类型:
procedure TForm1.AddNodestoTree(ParentNode: PVirtualNode; Node: TNode);
var SubNode: TNode;
    ThisNode: PVirtualNode;

begin
  ThisNode := VT.AddChild(ParentNode, Node); // This call adds a new TVirtualNode to the VT, and saves "Node" as the payload

  Node.VTNode := ThisNode; // Save the PVirtualNode for future reference. This is only an example,
                           // the same TNode might be registered multiple times in the same VT,
                           // so it would be associated with multiple PVirtualNode's.

  for SubNode in Node.Sub do
    AddNodestoTree(ThisNode, SubNode);
end;

// And start processing like this:
VT.NodeDataSize := SizeOf(Pointer); // Make sure we specify the size of the node's payload.
                                    // A variable holding an object reference in Delphi is actually
                                    // a pointer, so the node needs enough space to hold 1 pointer.
AddNodesToTree(nil, Root);

当使用对象时,您的Virtual Tree中的不同节点可能与不同类型的对象相关联。在我们的示例中,我们只添加了TNode类型的节点,但在现实世界中,您可能会在一个VT中拥有TContactTContactCategoryTRecentCall等类型的节点。您将使用is运算符来检查VT节点中对象的实际类型,如下所示:

procedure TForm1.VTGetText(Sender: TBaseVirtualTree; Node: PVirtualNode;
  Column: TColumnIndex; TextType: TVSTTextType; var CellText: string);
var PayloadObject:TObject;
    Node: TNode;
    Contact : TContact;      
    ContactCategory : TContactCategory;
begin
  PayloadObject := TObject(VT.GetNodeData(Node)^); // Extract the payload of the node as a TObject so
                                                   // we can check it's type before proceeding.
  if not Assigned(PayloadObject) then
    CellText := 'Bug: Node payload not assigned'
  else if PayloadObject is TNode then
    begin
      Node := TNode(PayloadObject); // We know it's a TNode, assign it to the proper var so we can easily work with it
      CellText := Node.Name;
    end
  else if PayloadObject is TContact then
    begin
      Contact := TContact(PayloadObject);
      CellText := Contact.FirstName + ' ' + Contact.LastName + ' (' + Contact.PhoneNumber + ')';
    end
  else if PayloadObject is TContactCategory then
    begin
      ContactCategory := TContactCategory(PayloadObject);
      CellText := ContactCategory.CategoryName + ' (' + IntToStr(ContactCategory.Contacts.Count) + ' contacts)';
    end
  else
    CellText := 'Bug: don''t know how to extract CellText from ' + PayloadObject.ClassName;
end;

以下是一个例子,说明为什么要将VirtualNode指针存储到节点实例中:

procedure TForm1.ButtonModifyClick(Sender: TObject);
begin
  Root.Sub[0].Sub[0].Name := 'Someone else'; // I'll modify the node itself
  VT.InvalidateNode(Root.Sub[0].Sub[0].VTNode); // and invalidate the tree; when displayed again, it will
                                                // show the updated text.
end;

你现在拥有了一个简单的树形数据结构的工作示例。你需要“扩展”这个数据结构以适应你的需求:可能性是无限的!为了给你一些想法,可以探索以下方向:

  • 你可以将Name:string转换为虚方法GetText:string;virtual,然后创建TNode的特殊后代来覆盖GetText以提供专门的行为。
  • 创建TNode.AddPath(Path:string; ID:Integer),允许您执行Root.AddPath('Contacts\Abraham', 1); - 也就是说,自动创建所有中间节点到最终节点的方法,以便轻松创建树。
  • PVirtualNode包含到TNode本身中,这样您就可以检查在Virtual Tree中节点是否已“选中”。这将是数据GUI分离的桥梁。

@Cosmin - 我一直在阅读指针(about.com)的相关内容,但我仍然不明白它们的工作原理,当我看到 “如果您将数据移动到单独的数据结构中,您将存储一个指针” 时。此外,记录难道不会占用更少的内存吗? - Jeff
1
@Jeff:与类相比,记录可能会占用更少的字节内存,但记录没有析构函数,并且是按值而不是按引用传递的。我认为我在我的答案中已经解释过了。在我看来,类更适合树形数据结构。或者,您可以使用指针和记录实现自己的树。 - Cosmin Prund
@Cosmin 这就是我试图去做的。 - Jeff
1
@daemon,“TNode”是一个指针,所以“PNode = ^TNode”实际上是一个指向指针的指针,因此它们不都是“只是指针”。一个是指针,一个是双重间接指针。如果您希望有效载荷为“TNode” OR其他内容,则在“VTGetText”中使用它将是错误的类型选择:更好的选择是“PObject = ^TObject”。 - Cosmin Prund
@CosminPrund,感谢您提供这个非常聪明的解决方案。请问您能否编辑您的答案并添加如何释放节点及其对象的方法?我经常遇到内存泄漏问题,但我无法弄清如何使用"OnFreeNode"事件来释放节点... - S.FATEH
显示剩余18条评论

4
我曾在这里问过类似的问题,但没得到有用的答案,所以我决定自己开发一个实现,你可以在这里找到。
编辑: 我将尝试发布示例,展示如何使用我的数据结构:
uses
  svCollections.GenericTrees;

声明你的数据类型:

type
  TMainData = record
    Name: string;
    ID: Integer;
  end;

在代码中的某个位置声明您的主数据树对象:

MyTree: TSVTree<TMainData>;

创建它(不要忘记稍后释放):
MyTree: TSVTree<TMainData>.Create(False);

将您的VirtualStringTree分配给我们的数据结构:
MyTree.VirtualTree := VST;

那么您可以使用一些值来初始化您的数据树:
procedure TForm1.BuildStructure(Count: Integer);
var
  i, j: Integer;
  svNode, svNode2: TSVTreeNode<TMainData>;
  Data: TMainData;
begin
  MyTree.BeginUpdate;
  try
    for i := 0 to Count - 1 do
    begin
      Data.Name := Format('Root %D', [i]);
      Data.ID := i;
      svNode := MyTree.AddChild(nil, Data);
      for j:= 0 to 10 - 1 do
      begin
        Data.Name := Format('Child %D', [j]);
        Data.ID := j;
        svNode2 := MyTree.AddChild(svNode, Data);
      end;
    end;
  finally
    MyTree.EndUpdate;
  end;
end;

并设置VST事件以显示您的数据:

procedure TForm1.vt1InitChildren(Sender: TBaseVirtualTree; Node: PVirtualNode;
  var ChildCount: Cardinal);
var
  svNode: TSVTreeNode<TMainData>;
begin
  svNode := MyTree.GetNode(Sender.GenerateIndex(Node));
  if Assigned(svNode) then
  begin
    ChildCount := svNode.FChildCount;
  end;
end;

procedure TForm1.vt1InitNode(Sender: TBaseVirtualTree; ParentNode,
  Node: PVirtualNode; var InitialStates: TVirtualNodeInitStates);
var
  svNode: TSVTreeNode<TMainData>;
begin
  svNode := MyTree.GetNode(Sender.GenerateIndex(Node));
  if Assigned(svNode) then
  begin
    //if TSVTree<TTestas> is synced with Virtual Treeview and we are building tree by
    // setting RootNodeCount, then we must set svNode.FVirtualNode := Node to
    // have correct node references
    svNode.FVirtualNode := Node;  // Don't Forget!!!!
    if svNode.HasChildren then
    begin
      Include(InitialStates, ivsHasChildren);
    end;
  end;
end;

//display info how you like, I simply get name and ID values
procedure TForm1.vt1GetText(Sender: TBaseVirtualTree; Node: PVirtualNode;
  Column: TColumnIndex; TextType: TVSTTextType; var CellText: string);
var
  svNode: TSVTreeNode<TMainData>;
begin
  svNode := MyTree.GetNode(Sender.GenerateIndex(Node));
  if Assigned(svNode) then
  begin
    CellText := Format('%S ID:%D',[svNode.FValue.Name, svNode.FValue.ID]);
  end;
end;

在这一点上,您仅使用“我的树(MyTree)”数据结构,并且对其进行的所有更改都将反映在分配给您的 VST 中。 然后,您始终可以将底层结构保存(和加载)到流或文件中。希望这有所帮助。

我不知道在哪里可以下载它? :) - Jeff
我刚刚测试了使用VT存储数据和使用你的SVTree添加1000个根节点,每个根节点有1000个子节点之间的差异。结果发现,SVTree比VT多使用了约100兆字节的内存,并且VT的速度大约是SVTree的两倍。这是因为我们在VT中使用指针而不是整个记录吗? - Jeff
在构建数据结构时,由于需要额外创建TSVTreeNode对象,因此会有一些额外的内存使用。不知道你是如何测试的,但构建我的数据结构会稍微慢一些,因为它需要生成唯一节点哈希以便能够在VT事件后检索到它。我发现在合理的测试中表现良好,但如果您需要添加数百万个具有巨大层次结构的节点,则可能需要考虑其他方法。 - Linas
你的程序非常好用,而且我猜测它也是线程安全的?我可能会使用大约20,000个节点,但内存使用已经成为一个问题:P - Jeff

4

我相信你最好找到一个已有的通用树实现库,然后重用它来满足你的需求。

为了让你明白为什么这样做是最好的,这里有一些代码,我写了一个最简单的树结构的最简单操作。

type
  TNode = class
    Parent: TNode;
    NextSibling: TNode;
    FirstChild: TNode;
  end;

  TTree = class
    Root: TNode;
    function AddNode(Parent: TNode): TNode;
  end;

function TTree.AddNode(Parent: TNode);
var
  Node: TNode;
begin
  Result := TNode.Create;

  Result.Parent := Parent;
  Result.NextSibling := nil;
  Result.FirstChild := nil;

  //this may be the first node in the tree
  if not Assigned(Root) then begin
    Assert(not Assigned(Parent));
    Root := Result;
    exit;
  end;

  //this may be the first child of this parent
  if Assigned(Parent) and not Assigned(Parent.FirstChild) then begin
    Parent.FirstChild := Result;
  end;

  //find the previous sibling and assign its next sibling to the new node
  if Assigned(Parent) then begin
    Node := Parent.FirstChild;
  end else begin
    Node := Root;
  end;
  if Assigned(Node) then begin
    while Assigned(Node.NextSibling) do begin
      Node := Node.NextSibling;
    end;
    Node.NextSibling := Result;
  end;
end;

注意:我没有测试过这段代码,因此无法保证其正确性。我认为它可能存在缺陷。

这只是向树中添加一个新节点。它不能很好地控制节点在树中的位置。它只是将一个新节点简单地添加为指定父节点的最后一个兄弟节点。

如果您想采取这种方法,您可能需要处理以下问题:

  • 在指定兄弟节点之后插入。实际上,这是上述操作的一种相当简单的变体。
  • 删除节点。这有点复杂。
  • 移动树中现有的节点。
  • 遍历树。
  • 将树连接到您的 VST。

这肯定是可行的,但您最好找到一个第三方库,已经实现了该功能。


2
如果我理解正确,您需要一种数据结构来表示树形结构。每个节点都需要一个记录来保存其数据。但是底层的层次结构可以用几种不同的方式管理。我猜这些都要在某种数据库中进行管理 - 这已经在本网站上讨论过了,所以我会指向以下链接:
实现数据库中的分层数据结构
最有效/优雅的将平面表解析为树形结构的方法是什么?
SQL-如何存储和导航层次结构?
嵌套集模型:

http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/


4
这个问题与数据库或平面文件无关。 - Ken White
有点模糊——但他可以看到将树形结构存储在(某些表/矩阵/数组等)中的原则,以及这些链接。 - Simon

0

如果您正在使用支持泛型的最新版本的Delphi,请查看GenericTree


-1

Delphi现在有泛型。我刚刚发明了一种非常好的树形数据结构。暂时不会公开代码,因为我不是一个开源的人,也许在不久的将来会公开,还有其他原因,请见下文。

但我会给出一些关于如何重新创建它的提示:

假设你的所有节点都可以包含相同的数据结构(从上面看似乎是这样的,一个字符串,一个ID,然后是链接)。

要重新创建它,你需要以下材料:

  1. 泛型
  2. 一个泛型类型T
  3. 这个类型T需要被限制为类和构造函数,如下所示:

<T : class, constructor> (在你的情况下,用记录替换类,未经测试,但可能也有效)

  • 包含两个字段:node 数组的 self(提示提示)、data:T;

  • 一个属性

  • 不仅是任何属性,而是默认属性;)

  • 一个 getter。

  • 一个带有深度和子项的递归构造函数。

  • 一些 if 语句用于停止构造。

  • 当然还有 SetLength 来创建链接/节点,并在 for 循环中调用某些 create 然后减去一些东西;)

  • 如果给你们足够的提示,能否重新创建它将会很有趣和有趣,否则我可能会申请专利,开玩笑,不会为此花钱,但可能会扩展该类以提供其他功能。

    该类在构造过程中分配所有节点,就像真正的数据结构一样...至少现在没有添加和删除等操作。

    现在来谈谈这个(秘密)设计中最有趣和有趣的方面,这是我想要但现在成为现实的东西。现在我可以编写以下代码:

    TGroup 只是一个示例,可以是任何东西,只要它是我的类。 在这种情况下,它只是带有 mString 的类。

    var
      mGroupTree : TTree<TGroup>;
    
    procedure Main;
    var
      Depth : integer;
      Childs : integer;
    begin
    
      Depth := 2;
      Childs := 3;
    
      mGroupTree := TTree<TGroup>.Create( Depth, Childs );
    
      mGroupTree.Data.mString := 'Basket'; // notice how nice this root is ! ;)
    
      mGroupTree[0].Data.mString := 'Apples';
      mGroupTree[1].Data.mString := 'Oranges';
      mGroupTree[2].Data.mString := 'Bananas';
    
      mGroupTree[0][0].Data.mString := 'Bad apple';
      mGroupTree[0][1].Data.mString := 'Average apple';
      mGroupTree[0][2].Data.mString := 'Good apple';
    
      mGroupTree[1][0].Data.mString := 'Tiny orange';
      mGroupTree[1][1].Data.mString := 'Medium orange';
      mGroupTree[1][2].Data.mString := 'Big orange';
    
      mGroupTree[2][0].Data.mString := 'Straight banana';
      mGroupTree[2][1].Data.mString := 'Curved banana';
      mGroupTree[2][2].Data.mString := 'Crooked banana';
    

    现在你可能会从这个实际测试代码中注意到的是,由于这个属性,它允许像我很少见到的"数组扩展",这种属性自我引用排序...

    所以[] []是深度2。 [][][]将是深度3。

    我仍在评估使用这个的可能性。

    一个潜在的问题是Delphi没有真正的技术来自动扩展这些数组,尽管我还没有找到任何满意的方法。

    我想要一种可以编写一些代码并可以到达任何深度级别的技术:

    [0][0][0][0][0]

    还不确定如何做到这一点...最简单的选项是"递归"。

    真实例子:

    procedure DisplayString( Depth : string; ParaTree : TTree<TGroup>);
    var
      vIndex : integer;
    begin
      if ParaTree <> nil then
      begin
    //    if ParaTree.Data.mString <> '' then
        begin
          writeln( ParaTree.Data.mString );
    
          Depth := Depth + ' ';
          for vIndex := 0 to ParaTree.Childs-1 do
          begin
            DisplayString( Depth, ParaTree[vIndex] );
          end;
        end;
      end;
    end;
    

    挺有趣的,不是吗。

    仍在探索它在“实际应用”中的有用性,以及我是否想使用递归 ;)

    也许有一天我会开源我的所有代码。我快40岁了,当我从39岁到40岁时,我计划开源。距离40岁还有4个月 =D

    (我必须说这是我第一次对泛型印象深刻,很久以前测试过,那时候超级有bug,设计上可能无法使用,但现在随着错误修复和约束泛型,最新的Delphi Toyko 10.2.3版本2018年8月非常令人印象深刻!;) :))

    我只是浅尝辄止最新的Delphi技术所能做到的,也许使用匿名方法编写递归例程来处理此数据结构可能会变得更容易,同时也可能考虑并行处理,Delphi帮助中提到了这一点。

    再见, Skybuck。


    网页内容由stack overflow 提供, 点击上面的
    可以查看英文原文,
    原文链接