Восстановление деревьев по "отпечатку пальца"

Question

Я провел свое исследование SO и Google и не нашел никого, кто занимался этим раньше, или, по крайней мере, никого, кто писал об этом.

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

Например, у меня есть "универсальное" дерево (простите мои плохие иллюстрации), представляющее мою вселенную возможностей:

                корень
        /  /  /  |  \  \ ... \
       ООООООО (Уровень 1)
      /|\/|\...................\ (Уровень 2)

и т.п.

У меня также есть дерево A, корневое поддерево моей вселенной

        корень
      / /|\ \
     O O O O O
    /

И т.п.

Есть ли способ "дактилоскопировать" дерево, чтобы по этим отпечаткам и универсальному дереву я мог восстановить А?

Я думаю о чем-то вроде хэша, сжатия или, возможно, функциональной / декларативной конструкции? Анализ Big-O (во времени или пространстве) является плюсом.

Например, вложенное выражение типа: {{(Root)},{(1),(2),(3)},{(2,3),(1),(4,5)}...} Представление фактических узлов, присутствующих на каждом уровне в дереве, вероятно, допустимо, но может ли это быть сделано более эффективно?

Answer 1

Я хотел бы использовать список списков, где каждый элемент в списке указывает, сколько у вас детей:

[[2][1,2][0,0,0]]

Это дерево с двумя узлами на первом уровне, и левый дочерний узел имеет один дочерний узел, а правый дочерний узел имеет 2 своих собственных.

Запустите этот вывод через алгоритм сжатия без потерь по вашему выбору.

Вы также можете использовать обход дерева по глубине или любой другой тип обхода. Из того, что вам легче всего восстановить.