Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.68/25: Рейтинг темы: голосов - 25, средняя оценка - 4.68
 Аватар для bodik21
16 / 4 / 0
Регистрация: 23.06.2011
Сообщений: 19

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

20.07.2011, 11:11. Показов 5308. Ответов 4
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Мое задание состоит в том, чтоби построить дерево, имея таблицу отношений родителя к потомку. Эта таблица находиться в базе данных, а дерево необходимо построить на основе treeview. На рисунке ниже изображен пример. Само дерево не имеет ограничений числа потомков и родителям, (сильноветвящиеся дерево). Прошу у Вас помощи построить такое дерево. Может есть какой-то алгоритм или уже где то на форуме есть решение (не смог найти). Буду очень благодарным за решение..
Миниатюры
Построение сильноветвящегося дерева на основе таблицы отношений  
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
20.07.2011, 11:11
Ответы с готовыми решениями:

Построение сильноветвящегося дерева потомков человека
Всех приветствую. Сам текст задания: Нужно построить дерево потомков человека. Дерево является сильноветвящимся. Каждый узел содержит...

Вывод сильноветвящегося дерева на консоль
Как вывести дерево степени 5 на консоль, если дерево представлено с помощью списка сыновей? struct tree{ int key;//здесь ключ...

TreeView: построение дерева на основе данных из БД Access
Такова проблема. Есть 3 таблицы в БД. 1-компания, 2 - отдел, 3-пользователь в 1-компания столбцы - id_firma, name_firma в 2 - отдел...

4
 Аватар для Aye Aye
373 / 287 / 97
Регистрация: 17.12.2009
Сообщений: 567
20.07.2011, 18:26
Необходима небольшая коррекция таблицы, надо добавить в нее [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] - оператор произвольного доступа с элементу таблицы.
1
 Аватар для bodik21
16 / 4 / 0
Регистрация: 23.06.2011
Сообщений: 19
21.07.2011, 09:26  [ТС]
Большое Вам спасибо (+1). Сегодня вечером попробую реализовать и выставлю свой вариант. Только еще один вопросик: тип ArrayOfNodePointers - TNode *;; и еще подскажите как лучше прикрутить этот масив к treeview (дерево будет больших размеров), чоб бистрее строилось???
0
 Аватар для Aye Aye
373 / 287 / 97
Регистрация: 17.12.2009
Сообщений: 567
23.07.2011, 04:19
вот немного про 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. Лучше сделать как обычно - рекурсией.
0
 Аватар для bodik21
16 / 4 / 0
Регистрация: 23.06.2011
Сообщений: 19
01.08.2011, 14:28  [ТС]
вот мой код построения дерева
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();
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
01.08.2011, 14:28
Помогаю со студенческими работами здесь

Представить цепную реакцию в виде сильноветвящегося дерева
2) Тема: Сильноветвящиеся деревья Представить цепную реакцию в виде сильноветвящегося дерева.

TreeView: построение дерева на основе данных из БД Oracle 11g xe
Добрый вечер.Столкнулся с такой проблемой.У меня есть три таблицы Partners P_ID ALIAS REGION INDIVIDUALS ID_FL P_ID ...

Построение иерарх. дерева на основе существующей БД. Как ускорить вывод данных.
Есть БД в которой заложен вывод данных в иерархическом виде (1С) т.е. там есть ID и ParentID (вхождение в ветвь). Мне нужно вывести...

Парсинг файлов формата IFC и построение дерева TreeView на основе полученных данных
Всем здрасти! У меня ужасное положение. Мне нужно сдавать проект. Проект парсит файлы формата IFC и строит тривьюху по распарсенным...

Построение сводной таблицы на основе данных из 2-х листов
Добрый день! Нарисовалась задачка: необходимо построить сводную таблицу по примерам. Помогите, кто чем может.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer
8Observer8 08.02.2026
Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств
8Observer8 07.02.2026
Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm
8Observer8 30.01.2026
Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru