Обойти дерево, хранящееся в массиве.

Вопросы программирования и использования среды Lazarus.

Модератор: Модераторы

Обойти дерево, хранящееся в массиве.

Сообщение wofs » 13.01.2018 21:03:50

Доброго дня!
Есть запись:
Код: Выделить всё
    TCategory = packed record
       id: integer;
       parentId: integer;
       name: string;
    end;


есть массив записей:
Код: Выделить всё
ArrayOfCategories = array of TCategory;

В массиве хранится список категорий. Массив отсортирован по возрастанию parentId. "Верхние" ветви имеют parentId=0. Общего корня нет. Глубина и количество "дочек" не регламентировано.
То есть что-то вроде:
Код: Выделить всё
1 | 0 | Бытовая техника
2 | 0 | Детские товары
10 | 1 | Мелкая техника для кухни
20 | 2 | Детский спорт
102 | 10 | Мороженицы
101 | 10 | Сэндвичницы и приборы для выпечки
200 | 20 | Игровые и спортивные комплексы, горки


Стоит задача обойти все дерево и все узлы занести в БД с сохранением иерархии, но id и parentId станут другими.

Понимаю, что надо Брать узел с parentId=0, обегать его дочек, далее дочек тех дочек и т.п. Но с рекурсией у меня совсем беда :( Прошу помощи в реализации задуманного. С БД проблем нет.
Аватара пользователя
wofs
постоялец
 
Сообщения: 379
Зарегистрирован: 05.10.2009 10:16:55
Откуда: Астрахань

Re: Обойти дерево, хранящееся в массиве.

Сообщение olegy123 » 13.01.2018 22:53:04

База данных может просто отображать данные,
А какие данные, в каком виде представления они должны быть - это уже способ реализации вне БД.

wofs писал(а):Стоит задача обойти все дерево и все узлы занести в БД с сохранением иерархии, но id и parentId станут другими.
Что значит "станут другими"?
Нельзя ли перенести данные как есть. И собирать их в иерархию, в дерево или в зависимости - уже от функции или логики представления этих данных.

БД в этом случае будет просто место сохранения.

Добавлено спустя 4 минуты 24 секунды:
wofs писал(а):Понимаю, что надо Брать узел с parentId=0, обегать его дочек, далее дочек тех дочек и т.п. Но с рекурсией у меня совсем беда :( Прошу помощи в реализации задуманного. С БД проблем нет.

Через что должно быть представление? через функцию БД, которая соберет и выведет дерево, либо это будет компонента в виде LCL/VCL?

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

Добавлено спустя 16 минут 15 секунд:
А понятно..
все просто:
create table <tablename>( key integer, parent integer, text varchar()..);
key integer, parent integer - этих данных достаточно для построения дерева.
olegy123
долгожитель
 
Сообщения: 1643
Зарегистрирован: 25.02.2016 12:10:20

Re: Обойти дерево, хранящееся в массиве.

Сообщение vitaly_l » 13.01.2018 23:33:10

wofs писал(а):у меня совсем беда

1) Напишите процедуру someProcedure(const parent:integer);, которая получая Id,
перебирает и выводит все элементы, у которых есть данный parentId.

2) Протестируйте её с parentId = 0, запустив someProcedure( 0 );.

3) Как только убедитесь что она при parent = 0 выводит все корневые элементы, запустите её в рекурсивном режиме, чтобы она при получении нового элемента вызывала сама себя

Код: Выделить всё
someProcedure(const parent:integer);
...
begin
  while countTreeArray > i do begin
    if parentId = parent then   
       someProcedure( id );
    inc(i);
  end;
end;

4) и она переберёт Вам всё дерево.

5) Выводите его в блокнот, прибавляя/удаляя на каждом уровне чёрточку, тогда дерево будет наглядным.
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3333
Зарегистрирован: 31.01.2012 16:41:41

Re: Обойти дерево, хранящееся в массиве.

Сообщение zub » 14.01.2018 01:11:23

Создание и обход дерева из данных имеющихся у ТС, на основе fcl-stl
Код: Выделить всё
program Project1;

uses
  sysutils, strutils,
  gvector, gtree, gmap, gutil;

type
  TID = integer;
  TCategory = record
   id: TID;
   parentId: TID;
   name: string;
  end;

  TCategoryVector=specialize TVector<TCategory>;
  TCategoryTree=specialize TTree<TCategory>;
  TID2CategoryTreeNode=specialize TMap<TID,TCategoryTree.TTreeNodeType,specialize TLess<TID>>;

var
  CategoryArray:TCategoryVector;
  CategoryTree:TCategoryTree;
  ID2CategoryNode:TID2CategoryTreeNode;

//Собираем и возвращаем TCategory
function CreateCategory(id,parentId: TID; name: string):TCategory;
begin
   result.id:=id;
   result.parentId:=parentId;
   result.name:=name;
end;

//Заполняем дерево
procedure UpdateTree(CT:TCategoryTree;ID2Node:TID2CategoryTreeNode;CA:TCategoryVector);
var
  Category:TCategory;
  Node,CreatedNode:TCategoryTree.TTreeNodeType;
begin
  //перебираем исходные данные
  for Category in CA do
  begin
    //пробуем найти ветку с нужным parentId
    if ID2Node.TryGetValue(Category.parentId,Node) then
    begin
      //ветка нашлась, создаем в ней дочернюю ветку
      CreatedNode:=TCategoryTree.TTreeNodeType.Create;
      CreatedNode.data:=Category;
      Node.Children.pushback(CreatedNode);
      //пополняем мап созданой веткой
      ID2CategoryNode.insert(Category.id,CreatedNode);
    end
    else
    begin
      //такого parentId еще нет в дереве
    end
  end;
end;

//процедура отрисовки дерева в консоли
procedure WriteTree(CT:TCategoryTree);

  //процедура отрисовки ветки дерева в консоли с отступом, вызывает сама себя рекурсивно
  procedure WriteTreeNode(CTN:TCategoryTree.TTreeNodeType;indent:integer);
  var
    CV:TCategoryTree.TTreeNodeType;
  begin
    for CV in CTN.children do
    begin
      writeln(format('%s(%d|%d|''%s'')',[dupestring(' ',indent),cv.data.id,cv.data.parentid,cv.data.name]));
      WriteTreeNode(CV,indent+2);
    end;
  end;
begin
  //надо с чегото начинать
  WriteTreeNode(CT.root,0);
end;

begin
  //создаем и заполняем исходный массив
  CategoryArray:=TCategoryVector.Create;
  CategoryArray.PushBack(CreateCategory(1,0,'Household appliances'));
  CategoryArray.PushBack(CreateCategory(2,0,'Childen''s goods'));
  CategoryArray.PushBack(CreateCategory(10,1,'Small kitchen appliances'));
  CategoryArray.PushBack(CreateCategory(20, 2,'Children''s sports'));
  CategoryArray.PushBack(CreateCategory(102,10,'Ice cream makers'));
  CategoryArray.PushBack(CreateCategory(101,10,'Sandwich makers and baking equipment'));
  CategoryArray.PushBack(CreateCategory(200,20,'Playing and sports complexes, slides'));

  //создаем дерево
  CategoryTree:=TCategoryTree.Create;
  //создаем вспомогательный мап для перевода ида в ветку дерева
  ID2CategoryNode:=TID2CategoryTreeNode.Create;

  //создаем корешок дерева с ид=0
  CategoryTree.Root:=CategoryTree.TTreeNodeType.Create;
  //вставляем его в мап
  ID2CategoryNode.insert(0,CategoryTree.Root);

  //заполняем дерево
  UpdateTree(CategoryTree,ID2CategoryNode,CategoryArray);
  //выводим дерево
  WriteTree(CategoryTree);
  //ждем чтобы успетьь налюбоваться на дерево
  readln;

  //грохаем всех по одному
  CategoryArray.Destroy;
  ID2CategoryNode.Destroy;
  CategoryTree.Destroy;
end.
zub
долгожитель
 
Сообщения: 2884
Зарегистрирован: 14.11.2005 23:51:26

Re: Обойти дерево, хранящееся в массиве.

Сообщение wofs » 14.01.2018 12:44:31

Спасибо! Все получилось, вот код:
Код: Выделить всё
// ищем категорию верхнего уровня и, если находим - запускаем перебор дочек

  for i:=0 to High(CategoriesArr) do
     if CategoriesArr[i].parentId = 0 then
     begin
        log(CategoriesArr[i].name);
        someProcedure('',CategoriesArr,CategoriesArr[i].id);
     end;   


Код: Выделить всё
procedure someProcedure(delimiter:string ; aCategoriesArr:ArrayOfCategories; const aCategory:integer);
var
   i: integer;
begin
    delimiter:= delimiter+'-';
    i:=0;
    while Length(aCategoriesArr)>i do
    begin
       if aCategoriesArr[i].parentId = aCategory then
       begin
         log(delimiter+' '+aCategoriesArr[i].name);
         someProcedure(delimiter,aCategoriesArr, aCategoriesArr[i].id );
       end;
       Inc(i);
    end;
end;   

И результат:
Бытовая техника
- Мелкая техника для кухни
-- Мороженицы
-- Сэндвичницы и приборы для выпечки
Детские товары
- Детский спорт
-- Игровые и спортивные комплексы, горки


zub писал(а):Создание и обход дерева из данных имеющихся у ТС, на основе fcl-stl

Отдельное спасибо за пример использования векторов - очень позначательно!

Добавлено спустя 2 минуты 8 секунд:
olegy123 писал(а):Что значит "станут другими"?
Нельзя ли перенести данные как есть.

Увы, нельзя - в БД свои иденты категорий (в силу некоторых причин).
Аватара пользователя
wofs
постоялец
 
Сообщения: 379
Зарегистрирован: 05.10.2009 10:16:55
Откуда: Астрахань

Re: Обойти дерево, хранящееся в массиве.

Сообщение vitaly_l » 14.01.2018 12:54:51

wofs писал(а):Спасибо! Все получилось, вот код:
КОД: ВЫДЕЛИТЬ ВСЁ
// ищем категорию верхнего уровня и, если находим - запускаем перебор дочек

  for i:=0 to High(CategoriesArr) do
     if CategoriesArr[i].parentId = 0 then
     begin
        log(CategoriesArr[i].name);
        someProcedure('',CategoriesArr,CategoriesArr[i].id);
     end;   


Вышеприведённый кусок Вашего кода - лишний груз мамонта.
От груза мамонта - нужно избавится.
Заменив лишний код на вот такой простой запрос:

Код: Выделить всё

someProcedure('',CategoriesArr,0);



.
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3333
Зарегистрирован: 31.01.2012 16:41:41

Re: Обойти дерево, хранящееся в массиве.

Сообщение wofs » 14.01.2018 13:00:07

vitaly_l писал(а):Вышеприведённый кусок Вашего кода - лишний груз мамонта.

Вы правы, зачем дважды перебирать дерево. Спасибо!

Добавлено спустя 9 минут 9 секунд:
Добавил эмуляцию работы с БД.
Код: Выделить всё
// вызов процедуры
  iParent:= 0;
  someProcedure(iParent,'',CategoriesArr,0); 


Код: Выделить всё
procedure someProcedure(idInBase:Integer; delimiter:string; aCategoriesArr:ArrayOfCategories; const aCategory:integer);
var
   i, iParent: integer;
begin
    iParent:= idInBase;
    delimiter:= delimiter+'-';
    i:=0;
    while Length(aCategoriesArr)>i do
    begin
       if aCategoriesArr[i].parentId = aCategory then
       begin
         idInBase:= AddToBase(iParent,delimiter+' '+aCategoriesArr[i].name);
         someProcedure(idInBase,delimiter,aCategoriesArr, aCategoriesArr[i].id);
       end;
       Inc(i);
    end;
end; 


AddToBase - эмулятор функции работы с БД
Код: Выделить всё
function TForm1.AddToBase(iParent: integer; AText: string): integer;
begin
  Result:= m1.Lines.Add(IntToStr(m1.Lines.Count)+'> '+'newParentID='+IntTOStr(iParent)+' '+ aText);
end;     

Результат:
13> newParentID=0 - Бытовая техника
14> newParentID=13 -- Мелкая техника для кухни
15> newParentID=14 --- Мороженицы
16> newParentID=14 --- Сэндвичницы и приборы для выпечки
17> newParentID=0 - Детские товары
18> newParentID=17 -- Детский спорт
19> newParentID=18 --- Игровые и спортивные комплексы, горки


Считаю задачу поставленную задачу полностью решенной. Всем спасибо!
Аватара пользователя
wofs
постоялец
 
Сообщения: 379
Зарегистрирован: 05.10.2009 10:16:55
Откуда: Астрахань


Вернуться в Lazarus

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 5

Рейтинг@Mail.ru