Подскажите алгоритм поиска одинакового пути в двух деревьях

Question

Есть два дерева. Каждый узел дерева содержит некоторое значение, которое мы можем сравнивать со значением из другого узла другого дерева. Если значения равны - значит узлы равны.

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

Нужно определить, можно ли в этих двух деревьях построить одинаковые пути? То есть такие пути, значения из узлов вдоль которых совпадают. Оба пути должны проходить от вершины до узла содержащего 0 детей. Количество узлов вдоль путей конечно тоже должно быть равным.

Пример:

  a           a        a
 /|\         /|\      / \
b c d       1 d z    x   y
| | |\      | |      |
e f g h     x g      s

У первых двух деревьев есть общий путь "adg". У третьего дерева нет общих путей с первыми двумя деревьями.

Существует ли какой-то общепринятый готовый алгоритм для решения такой задачи? Если существует, то как он может называться и где про него можно почитать?

Answer 1

Если дерево является деревом поиска (узлы перечисляются в определённом порядке), то поиск совпадающего пути похож на алгоритм слияния (merge). Для деревьев A и B:

while i < A.childcount and j < B.childcount 
if A.child[i].value < B.child[j].value
   i++
else if A.child[i].value > B.child[j].value
   j++ 
else
   add A.child[i].value to path
   A = A.child[i]  //продвигаемся на уровень вниз
   B = B.child[j]

Для неупорядоченных деревьев придётся перебирать всех потомков узла.

БЛОГ НА HUSL

Подскажите алгоритм поиска одинакового пути в двух деревьях

Ответы (1 шт):