Форум программистов, компьютерный форум CyberForum.ru

Построение сильноветвящегося дерева на основе таблицы отношений - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.63
bodik21
 Аватар для bodik21
16 / 4 / 0
Регистрация: 23.06.2011
Сообщений: 19
20.07.2011, 11:11     Построение сильноветвящегося дерева на основе таблицы отношений #1
Мое задание состоит в том, чтоби построить дерево, имея таблицу отношений родителя к потомку. Эта таблица находиться в базе данных, а дерево необходимо построить на основе treeview. На рисунке ниже изображен пример. Само дерево не имеет ограничений числа потомков и родителям, (сильноветвящиеся дерево). Прошу у Вас помощи построить такое дерево. Может есть какой-то алгоритм или уже где то на форуме есть решение (не смог найти). Буду очень благодарным за решение..
Миниатюры
Построение сильноветвящегося дерева на основе таблицы отношений  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.07.2011, 11:11     Построение сильноветвящегося дерева на основе таблицы отношений
Посмотрите здесь:

Построение бинарного дерева C++
C++ Построение бинарного дерева на основе не бинарного
Построение дерева каталогов C++
Построение бинарного дерева C++
Построение сильноветвящегося дерева потомков человека C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
20.07.2011, 18:26     Построение сильноветвящегося дерева на основе таблицы отношений #2
Необходима небольшая коррекция таблицы, надо добавить в нее [0 родитель 1] и [0 родитель 2].


Отсортировать таблицу отношений по возрастанию атрибута parent.
Пусть каждый узел дерева будет иметь свой уникальный номер как во волжении, буду называть его индексом.
Для первого значения атрибута pfrent выполняем:
-- Создаем корень с индексом, равным этому значению.
Для каждого значения атрибута parent (в том числе и для первого) выполняем:
-- Поиск узла с индексом, равным значению атрибута.
-- Cоздать его потомка с индексом = значению атрибута child, и добавить в список потомков узла.

Можно чуть-чуть по-другому.
Создать массив ссылок на узлы размером n-количество узлов (количество строк в таблице отношений).
Индекс элемента массива представляет собой индекс узла.
Пройти по массиву и создать все узлы.
Для каждой строки из таблицы выполнить:
C++
1
2
3
4
   ArrayOfNodePointers[Table[i].parent]->addChild( ArrayOfNodePointers[Table[i].child] );
   Node *root = ArrayOfNodePointers[0];
   Table.free();
   ArrayOfNodePointers.free(); // высвободить память под массивом, не освобождая узлы!
Дерево готово, указатель на его корень в переменной root.
Надеюсь понятно, но все равно прокомментирую:
Node - узел.
Node::addChild - добавить ребенка в список детей узла.
ArrayOfNodePointers - массив указателей на узлы.
Table - таблица отношений.
Table::operator[i] - оператор произвольного доступа с элементу таблицы.
bodik21
 Аватар для bodik21
16 / 4 / 0
Регистрация: 23.06.2011
Сообщений: 19
21.07.2011, 09:26  [ТС]     Построение сильноветвящегося дерева на основе таблицы отношений #3
Большое Вам спасибо (+1). Сегодня вечером попробую реализовать и выставлю свой вариант. Только еще один вопросик: тип ArrayOfNodePointers - TNode *;; и еще подскажите как лучше прикрутить этот масив к treeview (дерево будет больших размеров), чоб бистрее строилось???
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
23.07.2011, 04:19     Построение сильноветвящегося дерева на основе таблицы отношений #4
вот немного про ArrayOfNodePointers, но только в общих чертах.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Node {
  int index;
  std::list<Node*> childs;
  Node(int in):index(n) {}
  void addChild(Node *n)
  {
    childs.push_back(n);
  }
};
class AONP {
   Node **data;
   AONP(int n)
   {
     data = new Node*[n];
   }
   ~AONP()
   {
     delete data;
   }
   Node *oprator[](int n)
   {
     return data[n];
   }
};
 
AONP ArrayOfNodePointers(100500);
treeview - я так понял это функция для вывода дерева на экран. Адаптировать к массиву особого смысла нет, ибо все равно понадобится прыгать по ссылкам в списке детей каждого узла Node::childs. Лучше сделать как обычно - рекурсией.
bodik21
 Аватар для bodik21
16 / 4 / 0
Регистрация: 23.06.2011
Сообщений: 19
01.08.2011, 14:28  [ТС]     Построение сильноветвящегося дерева на основе таблицы отношений #5
вот мой код построения дерева
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
IBQuery1->SQL->Clear();
 IBQuery1->SQL->Add("select parent_class_id as parent,child_class_id as child from obj_allowed_links order by parent_class_id");
 IBQuery1->Open();
 int node_id,parent_node_id;
 AnsiString text_par,text_ch;
 TTreeNode *node;
 //добавляем узел верхнего уровня - корень дерева (root)
 TreeView2->Items->Clear();
 TreeView2->Items->BeginUpdate();
 TreeView2->Items->Add(NULL, "BASE_CLASS");
 node=TreeView2->Items->Item[0];
 TreeView2->Items->Item[0]->Data=0;
 for(IBQuery1->First();!IBQuery1->Eof;IBQuery1->Next())
  {
   node_id=IBQuery1->FieldByName("child")->AsInteger;
   parent_node_id=IBQuery1->FieldByName("parent")->AsInteger;
   IBQuery2->SQL->Clear();
   IBQuery2->SQL->Add("select code from classes where id=:id");
   IBQuery2->ParamByName("id")->AsInteger=IBQuery1->FieldByName("parent")->AsInteger;
   IBQuery2->Open();
   text_par=IBQuery2->FieldByName("code")->AsString;
   IBQuery2->SQL->Clear();
   IBQuery2->SQL->Add("select code from classes where id=:id");
   IBQuery2->ParamByName("id")->AsInteger=IBQuery1->FieldByName("child")->AsInteger;
   IBQuery2->Open();
 
   text_ch=IBQuery2->FieldByName("code")->AsString;
   ////ищем родительский узел
   for(int i=0; i<TreeView2->Items->Count;i++)
    {
     if(TreeView2->Items->Item[i]->Data==(void*)parent_node_id)
     {
      node=TreeView2->Items->Item[i];
      break;
     }
    }
      // ------------------------
   //добавляем к найденому узлу ребенка
   node=TreeView2->Items->AddChild(node, text_ch);
   //фиксируем id ребенка
   node->Data=(void*)node_id;
  }
 TreeView2->Items->EndUpdate();
Yandex
Объявления
01.08.2011, 14:28     Построение сильноветвящегося дерева на основе таблицы отношений
Ответ Создать тему
Опции темы

Текущее время: 21:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru