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

@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

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

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

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

Новые блоги и статьи Все статьи Все блоги /
My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .
Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача №1: при указании работ (справочник РаботыПоРемонтуСпецтехники),. . .

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

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

@gazlan 3178 / 1937 / 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