Сравнение двух древовидных структур

Я с трудом пытаюсь описать это в правильных терминах, поэтому я просто приведу как можно больше подробностей, и, надеюсь, кто-то знает, что я пытаюсь сделать = -)

Я пытаюсь сравнить два дерева узлов, чтобы определить, насколько они похожи / различны по структуре. На приведенных ниже схемах оба примера имеют одинаковое количество детей, внуков и т. Д. В примере 1 у Root есть ребенок с двумя детьми, а в примере два - с root.

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

Кто-нибудь случайно узнал об этом? Или даже какой технический термин для чего это?

Изменить: Кроме того, это в C #, и я использую списки для хранения этих объектов и их детей.

Пример 1

введите описание изображения здесь

Пример 2

введите описание изображения здесь

algorithm data-structure Mungoid
источник

Чего вы на самом деле пытаетесь достичь? Это немного похоже на проблему XY .

msell

Лучший способ описать это для сравнения «молекулярных» структур, которые пользователь создает по одной молекуле за раз. Пример 1 мог бы быть структурой, созданной пользователем, а пример 2 мог бы быть частью списка предопределенных структур, чтобы помочь определить, создал ли пользователь правильную структуру. Изоморфизм корневых деревьев - это, по-видимому, то, что я искал = -)

Мунгоид

Ответы:

То, что вы ищете, это изоморфизм корневых деревьев , который является специализированной версией изоморфизма графов , за исключением деревьев и корневой узел является фиксированным.

Объяснение, данное в этом назначении, использует два свойства:

Имеют одинаковое количество уровней (расстояние между корневыми и листовыми узлами)
Каждый уровень имеет одинаковое количество узлов

Используя эти два свойства, продвигайтесь вверх от листьев к корню, помечая каждый узел количеством детей в лексикографическом порядке. Например, ваш корень в примере 1 будет помечен (0, 0, (0, 1)) - у него три ребенка, у первого / второго 0 детей, а у третьего 2 ребенка, имеющих 0 и 1 ребенка соответственно. Наконец, вы просто сравниваете корневые метки, чтобы увидеть, совпадают ли деревья.

Я не занимался этим предметом, и я только прочитал эту статью несколько минут назад, поэтому я не могу ручаться за ее правильность; надеюсь, это поможет в любом случае.

congusbongus
источник

Удивительно, это именно то, что я ищу! Я должен попробовать. Благодарность!

Мунгоид

Я думаю, что это работает, только если у вас есть корневой узел, но в этом случае это может иметь место: D +1

Рой Т.

Если корневой узел не указан, вы все равно можете использовать эту технику, но попробуйте каждый корень. При сравнении двух деревьев это означает повторение до n раз.

congusbongus

Да, это работает как шарм.

Потребовалось

Спасибо за это, похоже, что-то, что я тоже мог бы использовать, я люблю алгоритм, чтобы найти центр дерева. Очень умно.

oodavid

Проблема, чтобы увидеть, являются ли два графика логически одинаковыми, называется Graph Isomorphishm, поэтому вы можете захотеть начать с этого.

Обратите внимание, что общая проблема изоморфизма графов есть в NP, однако для этого особого случая может быть ярлык, я не уверен, так как кажется логичным, что для того, чтобы узнать различия, нужно проверить, равны ли они.

Рой Т.
источник

Да, это то, что мне нужно. Никогда бы не понял, как это называется. Спасибо = -)

Мунгоид