Древовидная структура данных (для использования с VirtualTreeview)

Question

Я пришел к тому, что мне нужно прекратить хранить мои данные в компоненте VCL, и у меня есть «базовая структура данных», как Мистер. Роб Кеннеди предложил.

Прежде всего, этот вопрос о том, «как создать базовую структуру данных». :)

Моя иерархия состоит из 2 уровней узлов.

Прямо сейчас я перебираю свои вещи, перебирая корневые узлы, где я перебираю дочерние узлы корневого узла, чтобы получить то, что мне нужно (Данные). Я хотел бы иметь возможность хранить все свои данные в так называемой базовой структуре данных, чтобы я мог легко изменять записи, используя потоки (полагаю, я могу это сделать?)

Тем не менее, при циклическом просмотре моих записей (прямо сейчас) результаты зависят от Checkstate узла - если я использую базовую структуру данных, как я узнаю, проверен ли мой узел или нет, когда это моя структура данных? цикл через, а не мои узлы?

Допустим, я хотел использовать 2 уровня.

Это будет Родитель:

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

А малыш:

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

Это в основном то, что я делаю сейчас. В комментариях говорится, что это не лучшее решение, поэтому я открыт для предложений. :)

Я надеюсь, вы понимаете мой вопрос (ы). :)

Спасибо!

Answer 1

Структура данных, которую вы запрашиваете, очень проста, она настолько проста, что я бы рекомендовал использовать предоставленную Windows TTreeView: она позволяет хранить текст и идентификатор прямо в узле дерева без дополнительной работы.

---

Несмотря на мою рекомендацию использовать более простое TTreeView, я собираюсь дать свой взгляд на проблему структуры данных.Прежде всего я собираюсь использовать классов , а не записей .В вашем очень коротком примере кода вы смешиваете записи и классы очень непринужденным образом: когда вы делаете копию записи TRoot (при назначении записей создаются полные копии, потому что записи всегда рассматриваются как «значения»), вы 'не делать «глубокую копию» дерева: полная копия TRoot будет содержать тот же Kids:TList, что и оригинал, потому что классы, в отличие от записей, являются ссылками: вы копируете значение ссылки.

Другая проблема, когда у вас есть запись с полем объекта, - это управление жизненным циклом: у записи нет деструктора , поэтому вам потребуется другой механизм для освобождения принадлежащего объекта (Kids:TList).Вы могли бы заменить TList на array of Tkid, но тогда вам нужно быть очень осторожным при передаче записи монстра, потому что вы можете закончить делать глубокие копии огромных записей, когда вы меньше всего этого ожидаете.

На мой взгляд, самая разумная вещь, которую нужно сделать, - это основать структуру данных на классах , а не на записях: экземпляры классов (объекты) передаются как ссылки, так что вы можете перемещать ихвокруг все что хочешь без проблем.Вы также получаете встроенное управление жизненным циклом (деструктор )

Базовый класс будет выглядеть следующим образом.Вы заметите, что его можно использовать как Root или Kid, потому что и Root, и Kid совместно используют данные: оба имеют имя и идентификатор:

TNodeClass = class
public
  Name: string;
  ID: Integer;
end;

Если этот класс используется в качестве RootНужен способ хранить Детей.Я предполагаю, что вы на 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);

При использовании различных объектовузлы в вашем виртуальном дереве могут иметь различные типы объектов, связанных с ними.В нашем примере мы добавляем только узлы типа TNode, но в реальном мире у вас могут быть узлы типов TContact, TContactCategory, TRecentCall, все в одном VT.Вы будете использовать оператор 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, чтобы вы могли проверить, что узел «проверен» в виртуальном дереве.Это будет мостом разделения данных и GUI.

Answer 2

Полагаю, вам лучше всего будет найти существующую библиотеку, содержащую общую реализацию дерева, которую вы затем сможете использовать повторно для удовлетворения своих потребностей.

Чтобы дать вам представление о том, почему, вот код, который я написал, чтобы проиллюстрировать наиболее простую операцию с самой простой из представленных древовидных структур.

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.

Это, безусловно, выполнимо, но вам лучше посоветовать найти стороннюю библиотеку, которая уже реализует эту функциональность.

Answer 3

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

EDIT: Я постараюсь опубликовать пример, как вы могли бы использовать мою структуру данных:

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. Затем вы всегда можете сохранить (и загрузить) базовую структуру в поток или файл. Надеюсь, это поможет.

Answer 4

Если я правильно понимаю, вам нужна структура данных для вашего дерева.Каждый отдельный узел требует записи для хранения своих данных.Но основной иерархией можно управлять несколькими различными способами.Я предполагаю, что все это должно управляться в некоторой базе данных - об этом уже говорилось на этом сайте, поэтому я укажу вам:

Реализация иерархической структуры данных в базе данных

и здесь:

Какой самый эффективный / элегантный способ разбить плоский стол на дерево?

и здесь:

SQL - Как хранить и перемещаться по иерархиям?

Модель вложенного набора:

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

Answer 5

В настоящее время у Delphi есть дженерики.Я только что изобрел очень красивую древовидную структуру данных.Пока не собираюсь выдавать код, не совсем с открытым исходным кодом, может быть, в ближайшем будущем, хотя и другие причины см. Ниже.

Но я дам несколько советов о том, как его воссоздать:

Предполагая, что все ваши узлы могут содержать одну и ту же структуру данных (что, как кажется, имеет место сверху, строку, идентификатор и затем ссылки.

Ингредиенты, которые необходимо создать заново, этоследующее:

1. Обобщения
2. Универсальный тип T
3. Этот тип T должен быть ограничен классом и конструктором следующим образом:

(В вашем случае замените класс на запись, непроверенная, но также может работать)

два поля: массив себя (подсказка), данные: T;

свойство

Не просто свойство, свойство по умолчанию;)

Получатель.

Рекурсивный конструктор с глубиной и потомком.

Некоторые операторы if дляостановите конструкцию. И конечно же SetLength для создания ссылок / узлов и вызова некоторых создает в цикле for, а затем некоторое вычитание чего-то;)

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

Класс выделяет все узлы во время построения как настоящая структура данных ... с добавлением и удалением, и так далее, по крайней мере, пока.

Теперь наступает самый интересный и забавный аспект этого (секретного) дизайна,что-то вроде того, что я хотел, и теперьЛити.Теперь я могу написать код следующим образом:

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.

Я все еще оцениваю использованиеthis.

Одна потенциальная проблема заключается в том, что у Delphi нет реальной техники для автоматического расширения этих массивов, хотя я пока не нашел и не выполнил проверку.

Я хотел бы написать технику, где я могу написатьнекоторый код, который может перейти на любой уровень глубины:

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

Еще не уверен, как это сделать ... опция simpelst"recursion".

real пример:

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 лет, когда я перешагнул за 40, от 39 до 40 лет, я как бы планировал пойти с открытым исходным кодом.Еще 4 месяца до 40 = D

(Я должен сказать, что это первый раз, когда я впечатлен Generics, протестировал его давным-давно, он был супер глючным и, возможно, непригодным для дизайна, но теперь сисправленные и ограниченные ошибки дженериков, это очень впечатляет в последней версии Delphi Toyko 10.2.3 август 2018!методы, которые пишут рекурсивные процедуры для обработки этой структуры данных, могут стать немного проще, возможно, стоит рассмотреть параллельную обработку, Delphi help упоминает об этом для анонимных методов.

Пока, Skybuck.

Answer 6

Если вы используете последние версии Delphi, которые поддерживают Generics, отметьте GenericTree