Минимальная информация о узле для описания структуры дерева

Question

Мой вопрос в следующем: каков минимальный объем информации, необходимой мне для описания связей между узлами для обеспечения структуры на дереве? Как можно кратко представить эти правила?

У меня есть структура данных дерева (в C++, если это важно для любого пользователя. Std :: vector std :: vector с указателями, возвращающимися к родителям.). Узлы могут быть специализированными. Когда узел является специализированным, он может быть только «действительным», если у него есть определенные родители или может быть действительным только в том случае, если у него есть определенные дети. Система не имеет 100% знаний о всех типах узлов (то есть, пользователь должен строить плагин с новыми узлами, и эти узлы могут иметь новые правила). Хотя все работает хорошо, оно опирается на наши априорные знания о том, как построить дерево. (Новый пользователь может размещать узлы где-то, что не имеет смысла логически, и это то, что мы хотим обнаружить и предотвратить.)

Мы хотим иметь возможность «обеспечить соблюдение» действующей структуры. Разрешить привязку некоторых узлов в любом месте, в то время как другие имеют специальные места и т. Д. Все узлы, конечно же, наследуются от общего базового класса и имеют список всех своих детей и указатель на их родителя. Довольно просто.

Моя первая попытка состояла в том, чтобы просто позволить узлам перечислить их действительные родительские типы. Это, однако, приводит к тому, что некоторые узлы очень беспорядочны и привязаны к родителям, где это просто не имеет смысла. Чтобы решить эту проблему, я добавил список дочерних типов, которые может принять узел. Это хорошо отразилось на спаривании дерева, но при этом стало сложнее управлять, и, учитывая множественные уровни наследования некоторых узлов, трудно маскировать некоторые типы детей, позволяя другим.

На этом этапе я подумал, что стоит задать вопрос. Деревья не являются моей специальностью ... и, конечно же, кто-то знает четко определенный способ построения такого дерева и обеспечения гибкости и значимости отношений. Мысли или идеи?

Другая информация, если это имеет значение: структура имеет тенденцию быть очень широкой (от сотен до тысяч узлов) и неглубокой (глубиной 2-10 уровней). Там, как правило, есть корень между одним и пятью под деревьями ... в котором начинается настоящая работа. Я рад использовать STL, Boost или любую другую библиотеку, которая может помочь здесь. Я не хочу изобретать дерево. Возможность представить отношения между узлами для построения дерева является фокусом вопроса.

Answer 1

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

Простейший способ состоит в том, чтобы иметь одну ссылку для каждого вид отношений. Если вы хотите пройти в двух направлениях (вперед и назад) в отношениях, вам нужно будет иметь две ссылки для каждой связи.

Если вы хотите иметь динамические отношения, я предлагаю, чтобы каждый узел имел map, std::map<relation, link>. Первым элементом, ключом, будет идентификатор перечислимых отношений (или std::string). Значение будет ссылкой на узел. Это позволит вам сказать что-то вроде:

next_node = node_links[NEXT_BY_ALPHABETICAL]; 

Я предлагаю вам рисовать отношения между вашими объектами. Также draw Дерево и отношения между узлами.

Другой вариант - иметь отдельные деревья, по одному для каждой связи. Каждый узел этих деревьев будет содержать указатель на элемент данных.Таким образом, существует только один элемент данных; но может быть один или несколько указателей индексирования (отношения).

Наконец, вы можете рассмотреть возможность использования базы данных, возможно, реляционной базы данных.