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

Question

Двоичное дерево http://img9.imageshack.us/img9/9981/binarytree.jpg

Каков наилучший способ сериализации заданного двоичного дерева, и Inturn оценивает уникальный идентификатор для каждого сериализованного двоичного дерева?

Например, мне нужно сериализовать поддерево (2,7, (5,6,11)) и сгенерировать уникальный идентификатор ' x ', представляющий это поддерево, чтобы всякий раз, когда я наткнуться на подобное поддерево (2,7, (5,6,11)), оно будет сериализовано в одно и то же значение ' x ', и, следовательно, я могу сделать вывод, что нашел совпадение. 1010 *

Здесь мы предполагаем, что каждый узел обладает уникальными свойствами. В приведенном выше примере это будут номера, назначенные каждому узлу, и, следовательно, они всегда будут генерировать одинаковые идентификаторы для похожих поддеревьев. Я пытаюсь сделать это в C ++.

Существуют ли уже алгоритмы для выполнения такого последовательного сопоставления деревьев?

Answer 1

Я бы сделал хеш-значение (некоторым образом Рабина-Карпа) на основе идентификаторов узлов и положения в дереве, то есть:

long h = 0
for each node in sub tree:
    h ^= node.id << (node.depth % 30)

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

Answer 2

Хотите ли вы иметь возможность сопоставить любую произвольную часть дерева или поддерево, идущее до какого-либо конечного узла (узлов)? IIUC, вы смотрите на соответствие суффикса.

Вы также можете взглянуть на Компактный направленный ациклический граф слов для идей.

Answer 3

Что не так с обозначением в скобках, которое вы использовали в своем вопросе?

Answer 4

Если вы не ищете высокую эффективность, вы можете использовать очень простой алгоритм поиска в глубину.

"2,7,2,U,6,5,U,11,U,U,U,5,9,4"

Как видите, я добавил команды U ("вверх"), чтобы показать, где будет создан следующий дочерний элемент. Конечно, вы можете сделать это более эффективным, но я верю, что это начало.

Кроме того, вы можете взглянуть на Boost.Graph (BGL) для реализации.