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

@Helldrg · Регистрация: 10.01.2011

Студворк — интернет-сервис помощи студентам

Здравствуйте! Можете подсказать из каких полей состоит такая структура, у которой должен быть один предшественники множество потомков.

@gazlan · 30.10.2016, 00:55

Multiway Trees

@Helldrg · 30.10.2016, 16:14 **[ТС]**

Я вот понять не могу почему от 3 элементов 4 ветки идет
Я так понимаю это как то с последовательностью записи связано, и почему к потомкам идет связь в центр их массива

Добавлено через 3 часа 17 минут
B - дерево не подходит, там смысл в том, что значения сравниваются и в зависимости от этого расставляются, а у меня значения которые не сравнимы друг с другом

@gazlan · 30.10.2016, 19:29

Сообщение от Helldrg

почему от 3 элементов 4 ветки идет

Потому, что "4-way search tree". Эти 4 пути связаны с узлом (Node), а сколько именно в нем элементов - это детали реализации.

BTree - один из вариантов (наиболее часто используемый и хорошо изученный). Другие M-way trees имеют сходное строение.

@Helldrg · 30.10.2016, 21:29 **[ТС]**

gazlan
Я уже разобрался, мне такая структура не подходит для хранения каталога файлов

@gazlan · 30.10.2016, 22:05

Не по теме:

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

@Helldrg · 30.10.2016, 22:26 **[ТС]**

это дерево строится по значениям минимальные слева максимальные справа, как к каталогам такое применить беспонятия

@gazlan · 30.10.2016, 22:39

Сообщение от Helldrg

это дерево...

Дался вам частный случай. Постройте другое, несортированное. OS точно также не сортирует каталоги.

IGPIGP · 30.10.2016, 23:22

Сообщение от 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 должен реализовывать все возможные элементы данных узла, - диски/папки/файлы... Корень придётся передавать в конструкторе по дереву, если не делать статическим. Иначе нельзя создать более одного дерева. Удобство списка узлов для каждого узла в том, что нет ограничений. Траверсировать такое дерево интересно.

@Helldrg · 31.10.2016, 00:05 **[ТС]**

IGPIGP
Значит val - содержит данные об этом узле, *head - указатель на корневой элемент или на родительский, list_Trees - это потомки?
Что бы отличать на каком уровне находятся элементы нужно в val записывать это уровень?

IGPIGP · 31.10.2016, 00:23

Сообщение от Helldrg

*head - указатель на корневой элемент или на родительский

на корень, - он у дерева один. В принципе можно и двусвязное дерево слепить, но я не пробовал.

Сообщение от Helldrg

Что бы отличать на каком уровне находятся элементы нужно в val записывать это уровень?

Тут не понял о чём Вы говорите. На каком уровне (в какой структуре типа диска, логического диска, папки, и далее по папкам...) решает не дерево. Я же о том и хотел сказать. Тут же юзер как захочет так и будет. Это дерево - для него ведь. И ему знать где он и чего закопал. Забудет и будет искать глобальным поиском.

Дерево поиска это совсем другое. Вот оно-то и решает куда, - нужно. То есть если есть двоичное дерево и вы передаёте ему элемент для добавления, то место которое он займёт совершенно однозначно определено.
А файловая система это не система поиска. Это система формального упорядочивания. В ней могут быть совершенно идентичные элементы и даже под-структуры... Хозяин барин же.

@Helldrg · 31.10.2016, 00:36 **[ТС]**

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

IGPIGP · 31.10.2016, 00:45

Сообщение от Helldrg

Что бы отличать на каком уровне находятся элементы нужно в val записывать это уровень?

Если это понимать как "чтобы реализовать рекурсивное ветвление (древовидную структуру)" то да. Узлом является List_Tree. Он содержит список указателей на узлы. Список удобен тем, что можно не трогая соседей что-то добавить или удалить. В предложенной схеме нет обратной восходящей ссылки. Но это же знакомая ситуация. У бинарного дерева, узел же не имеет ссылки на родителя. Хотя сделать такое можно, и наверняка такое есть. Тут я знаю мало.

Добавлено через 5 минут

Сообщение от Helldrg

А как отличить программе какие узлы надо показывать?

Так как она это делает в любом браузере. Тут графики много. В windows .NET есть класс TreeView (или вроде того). Он рисует граф дерева, если реализовать его узел. Тут же речь о различных представлениях. Они мирно сосуществуют, каждый в своей области окна.

@Helldrg · 31.10.2016, 00:55 **[ТС]**

Сообщение от IGPIGP

А как отличить программе какие узлы надо показывать?

Я имел ввиду: вот у нам есть список узлов из 100 элементов. Для нас без дополнительной информации это просто ряд значений - обычный массив. Но если, как мы выяснили, добавлять дополнительную информацию, например указатель на предка, то из ряда у нас превращается в дерево список узлов. Теперь осталось мне это реализовать. Спасибо большое за помощь!

IGPIGP · 31.10.2016, 01:04

Сообщение от Helldrg

, *head - указатель на корневой элемент или на родительский,

а кажется понял, что Вас смутило. Зря я включил корневой узел в нод? Может и так. Можно реализовать охватывающий класс, где хранить корень. Так можно съекономить память. С другой стороны ноды разных деревьев могут определить принадлежат ли они одному дереву только сравнивая узлы. Если им это не придётся делать (лучше наверное так) то и не нужен такой указатель. Тут решите сами. Я могу насоветоветовать. На ночь глядя.

@Helldrg · 31.10.2016, 01:10 **[ТС]**

Сообщение от IGPIGP

Зря я включил корневой узел в нод?

Я думаю он наврятли пригодится как указатель на корень =) Но этот узел буду использовать в качестве указателя на предка. У Корня этот параметр будет равняться NULL. Еще раз спасибо большое! За диалогом обычно прояснение приходит =)

IGPIGP · 31.10.2016, 01:20

Сообщение от Helldrg

Я имел ввиду: вот у нам есть список узлов из 100 элементов. Для нас без дополнительной информации это просто ряд значений - обычный массив. Но если, как мы выяснили, добавлять дополнительную информацию, например указатель на предка, то из ряда у нас превращается в дерево список узлов.

Список узлов это линейная последовательность. Её связность - природное свойство состоящее в принадлежности и порядке следования. Для этого не нужно дополнительной информации. Дереву это тоже не нужно. Оно тоже так устроено, что оно дерево. Самый простой рекурсивный тип это односвязный список. В нем каждый узел содержит ссылку на следующий. Когда узел содержит две таких, это бинарное дерево. Если поддерживается порядок размещения нижестоящих узлов относительно родителя то это дерево поиска. N-ways деревья содержат по n ссылок в каждом узле. Они тоже могут поддерживать порядок размещения и, следовательно, быть поисковыми. А если у узла набор ссылок который может изменять размер, то это дерево, которое может отразить любую древовидную структуру. О нём я пытался сказать. Оно строится как дерево и вся информация у него основная. В случае файловой структуры (если не учитывать физическую фрагментацию и пр. нюансы) то логическая структура дерева реализована не только как представление.

Сообщение от Helldrg

Спасибо большое за помощь!

Рад если помог.

Хотя надеюсь, что люди знающие предмет. Расскажут лучше и правильнее.

Новые блоги и статьи Все статьи Все блоги /
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Рецензия / Мнение/ Перевод https:/ / **********/ gallery/ thinkpad-x220-tablet-porn-gzoEAjs . . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .

@Helldrg 29 / 58 / 6 Регистрация: 10.01.2011 Сообщений: 1,231

	Структура дерева с одним предком и множеством потомков 30.10.2016, 00:43. Показов 4534. Ответов 16 Метки нет (Все метки) Здравствуйте! Можете подсказать из каких полей состоит такая структура, у которой должен быть один предшественники множество потомков. 0

@gazlan 3176 / 1935 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	30.10.2016, 00:55
	Multiway Trees 3

@Helldrg 29 / 58 / 6 Регистрация: 10.01.2011 Сообщений: 1,231
	30.10.2016, 16:14 [ТС]
	Я вот понять не могу почему от 3 элементов 4 ветки идет Я так понимаю это как то с последовательностью записи связано, и почему к потомкам идет связь в центр их массива Добавлено через 3 часа 17 минут B - дерево не подходит, там смысл в том, что значения сравниваются и в зависимости от этого расставляются, а у меня значения которые не сравнимы друг с другом 0

@Helldrg 29 / 58 / 6 Регистрация: 10.01.2011 Сообщений: 1,231
	30.10.2016, 21:29 [ТС]
	gazlan Я уже разобрался, мне такая структура не подходит для хранения каталога файлов 0

@gazlan
	30.10.2016, 22:05
	Не по теме: Звучит странно, поскольку дерево каталогов - это именно M-way tree. 0

@Helldrg 29 / 58 / 6 Регистрация: 10.01.2011 Сообщений: 1,231
	30.10.2016, 22:26 [ТС]
	это дерево строится по значениям минимальные слева максимальные справа, как к каталогам такое применить беспонятия 0

@Helldrg 29 / 58 / 6 Регистрация: 10.01.2011 Сообщений: 1,231
	31.10.2016, 00:05 [ТС]
	IGPIGP Значит val - содержит данные об этом узле, *head - указатель на корневой элемент или на родительский, list_Trees - это потомки? Что бы отличать на каком уровне находятся элементы нужно в val записывать это уровень? 0

@Helldrg 29 / 58 / 6 Регистрация: 10.01.2011 Сообщений: 1,231
	31.10.2016, 00:36 [ТС]
	IGPIGP Про уровень я имел ввиду следующее: Когда пользователь нажимает на корневой узел появляются его дочерние элементы, а дечерние элементы дочерних элементов не появляются, пока пользователь дальше не начнет нажимать на узлы. А как отличить программе какие узлы надо показывать? Я так думаю, нужно дополнительную информацию записывать об узле, например его уровень или же нужно кроме корневого узла родительский сохранять, что бы выборка была примерно такой: если узел имеет этого предка тогда вывести 0