Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.63/8: Рейтинг темы: голосов - 8, средняя оценка - 4.63
Helldrg
27 / 56 / 6
Регистрация: 10.01.2011
Сообщений: 1,205
1

Структура дерева с одним предком и множеством потомков

30.10.2016, 00:43. Просмотров 1537. Ответов 16
Метки нет (Все метки)

Здравствуйте! Можете подсказать из каких полей состоит такая структура, у которой должен быть один предшественники множество потомков.
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.10.2016, 00:43
Ответы с готовыми решениями:

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

Определение элемента дерева который имеет наименьшее количество непосредственных потомков
Определение элемента дерева который имеет наименьшее количество непосредственных потомков. Каждый...

Определить, является ли одна из вершин дерева предком другой (Графы)
Напишите программу, которая для двух вершин дерева определяет, является ли одна из них предком...

Запрос всех потомков дерева
Всем привет! Имеется древовидная таблица. Задался таким вопросом: как сделать так, чтобы из всей...

Создание генеалогического дерева потомков
Всем доброго времени суток! Звучит задание так: Построить генеалогическое дерево из 4-х...

16
gazlan
3163 / 1922 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
30.10.2016, 00:55 2
Multiway Trees
3
Helldrg
27 / 56 / 6
Регистрация: 10.01.2011
Сообщений: 1,205
30.10.2016, 16:14  [ТС] 3
Я вот понять не могу почему от 3 элементов 4 ветки идет
Я так понимаю это как то с последовательностью записи связано, и почему к потомкам идет связь в центр их массива

Добавлено через 3 часа 17 минут
B - дерево не подходит, там смысл в том, что значения сравниваются и в зависимости от этого расставляются, а у меня значения которые не сравнимы друг с другом
0
gazlan
3163 / 1922 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
30.10.2016, 19:29 4
Цитата Сообщение от Helldrg Посмотреть сообщение
почему от 3 элементов 4 ветки идет
Потому, что "4-way search tree". Эти 4 пути связаны с узлом (Node), а сколько именно в нем элементов - это детали реализации.

BTree - один из вариантов (наиболее часто используемый и хорошо изученный). Другие M-way trees имеют сходное строение.
1
30.10.2016, 19:29
Helldrg
27 / 56 / 6
Регистрация: 10.01.2011
Сообщений: 1,205
30.10.2016, 21:29  [ТС] 5
gazlan
Я уже разобрался, мне такая структура не подходит для хранения каталога файлов
0
gazlan
30.10.2016, 22:05
  #6

Не по теме:

Звучит странно, поскольку дерево каталогов - это именно M-way tree.

0
Helldrg
27 / 56 / 6
Регистрация: 10.01.2011
Сообщений: 1,205
30.10.2016, 22:26  [ТС] 7
это дерево строится по значениям минимальные слева максимальные справа, как к каталогам такое применить беспонятия
0
gazlan
3163 / 1922 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
30.10.2016, 22:39 8
Цитата Сообщение от Helldrg Посмотреть сообщение
это дерево...
Дался вам частный случай. Постройте другое, несортированное. OS точно также не сортирует каталоги.
1
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
7638 / 3787 / 518
Регистрация: 04.12.2011
Сообщений: 10,911
Записей в блоге: 5
30.10.2016, 23:22 9
Цитата Сообщение от Helldrg Посмотреть сообщение
Я уже разобрался, мне такая структура не подходит для хранения каталога файлов
Helldrg, n-арные деревья как и бинарное ( частный случай ) подходят для хранения упорядочиваемого набора данных.
Файловая структура это древовидная структура, но она строится искусственно. Если бинарное дерево построенное из одних и тех же данных будет зависеть от порядка их добавления, то дерево каталогов строится под действием внешней грубой силы. Часть строит OS для себя. Часть строит пользователь. Наверное, их вообще нет смысла сравнивать.
Для файловой структуры можно бы выбрать рекурсивный тип наподобие:
C++
1
2
3
4
5
6
7
8
9
template<typename T>
class List_Tree
{
T val;
List_Tree * head;
list<List_Tree *>  list_Trees;
///
///
};
Тип T должен реализовывать все возможные элементы данных узла, - диски/папки/файлы... Корень придётся передавать в конструкторе по дереву, если не делать статическим. Иначе нельзя создать более одного дерева. Удобство списка узлов для каждого узла в том, что нет ограничений. Траверсировать такое дерево интересно.
1
Helldrg
27 / 56 / 6
Регистрация: 10.01.2011
Сообщений: 1,205
31.10.2016, 00:05  [ТС] 10
IGPIGP
Значит val - содержит данные об этом узле, *head - указатель на корневой элемент или на родительский, list_Trees - это потомки?
Что бы отличать на каком уровне находятся элементы нужно в val записывать это уровень?
0
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
7638 / 3787 / 518
Регистрация: 04.12.2011
Сообщений: 10,911
Записей в блоге: 5
31.10.2016, 00:23 11
Цитата Сообщение от Helldrg Посмотреть сообщение
*head - указатель на корневой элемент или на родительский
на корень, - он у дерева один. В принципе можно и двусвязное дерево слепить, но я не пробовал.
Цитата Сообщение от Helldrg Посмотреть сообщение
Что бы отличать на каком уровне находятся элементы нужно в val записывать это уровень?
Тут не понял о чём Вы говорите. На каком уровне (в какой структуре типа диска, логического диска, папки, и далее по папкам...) решает не дерево. Я же о том и хотел сказать. Тут же юзер как захочет так и будет. Это дерево - для него ведь. И ему знать где он и чего закопал. Забудет и будет искать глобальным поиском.
Дерево поиска это совсем другое. Вот оно-то и решает куда, - нужно. То есть если есть двоичное дерево и вы передаёте ему элемент для добавления, то место которое он займёт совершенно однозначно определено.
А файловая система это не система поиска. Это система формального упорядочивания. В ней могут быть совершенно идентичные элементы и даже под-структуры... Хозяин барин же.
1
Helldrg
27 / 56 / 6
Регистрация: 10.01.2011
Сообщений: 1,205
31.10.2016, 00:36  [ТС] 12
IGPIGP
Про уровень я имел ввиду следующее:
Когда пользователь нажимает на корневой узел появляются его дочерние элементы, а дечерние элементы дочерних элементов не появляются, пока пользователь дальше не начнет нажимать на узлы. А как отличить программе какие узлы надо показывать? Я так думаю, нужно дополнительную информацию записывать об узле, например его уровень или же нужно кроме корневого узла родительский сохранять, что бы выборка была примерно такой: если узел имеет этого предка тогда вывести
0
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
7638 / 3787 / 518
Регистрация: 04.12.2011
Сообщений: 10,911
Записей в блоге: 5
31.10.2016, 00:45 13
Цитата Сообщение от Helldrg Посмотреть сообщение
Что бы отличать на каком уровне находятся элементы нужно в val записывать это уровень?
Если это понимать как "чтобы реализовать рекурсивное ветвление (древовидную структуру)" то да. Узлом является List_Tree. Он содержит список указателей на узлы. Список удобен тем, что можно не трогая соседей что-то добавить или удалить. В предложенной схеме нет обратной восходящей ссылки. Но это же знакомая ситуация. У бинарного дерева, узел же не имеет ссылки на родителя. Хотя сделать такое можно, и наверняка такое есть. Тут я знаю мало.

Добавлено через 5 минут
Цитата Сообщение от Helldrg Посмотреть сообщение
А как отличить программе какие узлы надо показывать?
Так как она это делает в любом браузере. Тут графики много. В windows .NET есть класс TreeView (или вроде того). Он рисует граф дерева, если реализовать его узел. Тут же речь о различных представлениях. Они мирно сосуществуют, каждый в своей области окна.
1
Helldrg
27 / 56 / 6
Регистрация: 10.01.2011
Сообщений: 1,205
31.10.2016, 00:55  [ТС] 14
Цитата Сообщение от IGPIGP Посмотреть сообщение
А как отличить программе какие узлы надо показывать?
Я имел ввиду: вот у нам есть список узлов из 100 элементов. Для нас без дополнительной информации это просто ряд значений - обычный массив. Но если, как мы выяснили, добавлять дополнительную информацию, например указатель на предка, то из ряда у нас превращается в дерево список узлов. Теперь осталось мне это реализовать. Спасибо большое за помощь!
0
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
7638 / 3787 / 518
Регистрация: 04.12.2011
Сообщений: 10,911
Записей в блоге: 5
31.10.2016, 01:04 15
Цитата Сообщение от Helldrg Посмотреть сообщение
, *head - указатель на корневой элемент или на родительский,
а кажется понял, что Вас смутило. Зря я включил корневой узел в нод? Может и так. Можно реализовать охватывающий класс, где хранить корень. Так можно съекономить память. С другой стороны ноды разных деревьев могут определить принадлежат ли они одному дереву только сравнивая узлы. Если им это не придётся делать (лучше наверное так) то и не нужен такой указатель. Тут решите сами. Я могу насоветоветовать. На ночь глядя.
1
Helldrg
27 / 56 / 6
Регистрация: 10.01.2011
Сообщений: 1,205
31.10.2016, 01:10  [ТС] 16
Цитата Сообщение от IGPIGP Посмотреть сообщение
Зря я включил корневой узел в нод?
Я думаю он наврятли пригодится как указатель на корень =) Но этот узел буду использовать в качестве указателя на предка. У Корня этот параметр будет равняться NULL. Еще раз спасибо большое! За диалогом обычно прояснение приходит =)
1
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
7638 / 3787 / 518
Регистрация: 04.12.2011
Сообщений: 10,911
Записей в блоге: 5
31.10.2016, 01:20 17
Цитата Сообщение от Helldrg Посмотреть сообщение
Я имел ввиду: вот у нам есть список узлов из 100 элементов. Для нас без дополнительной информации это просто ряд значений - обычный массив. Но если, как мы выяснили, добавлять дополнительную информацию, например указатель на предка, то из ряда у нас превращается в дерево список узлов.
Список узлов это линейная последовательность. Её связность - природное свойство состоящее в принадлежности и порядке следования. Для этого не нужно дополнительной информации. Дереву это тоже не нужно. Оно тоже так устроено, что оно дерево. Самый простой рекурсивный тип это односвязный список. В нем каждый узел содержит ссылку на следующий. Когда узел содержит две таких, это бинарное дерево. Если поддерживается порядок размещения нижестоящих узлов относительно родителя то это дерево поиска. N-ways деревья содержат по n ссылок в каждом узле. Они тоже могут поддерживать порядок размещения и, следовательно, быть поисковыми. А если у узла набор ссылок который может изменять размер, то это дерево, которое может отразить любую древовидную структуру. О нём я пытался сказать. Оно строится как дерево и вся информация у него основная. В случае файловой структуры (если не учитывать физическую фрагментацию и пр. нюансы) то логическая структура дерева реализована не только как представление.
Цитата Сообщение от Helldrg Посмотреть сообщение
Спасибо большое за помощь!
Рад если помог.
Хотя надеюсь, что люди знающие предмет. Расскажут лучше и правильнее.
1
31.10.2016, 01:20
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.10.2016, 01:20

Одноместные предикаты заданы над одним и тем же множеством
Пусть P(x) и Q(x) - такие одноместные предикаты, заданные над одним и тем же множеством M, что...

Структура таблицы с множеством колонок
Не совсем вопрос, а больше теоретический разбор. Есть таблица с множеством колонок, что-то типа...

Посчитать количество вершин дерева, которые имеют менее четырёх потомков
Дано S-выражение, представляющее дерево вида «(РебенокЛевый Родитель РебенокПравый)». Определить...


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

Или воспользуйтесь поиском по форуму:
17
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.