Определите, равны ли два бинарных дерева

Ответ 1

Это второстепенная проблема, но я бы адаптировал более раннее решение следующим образом:

eq(t1, t2) =
  t1.data=t2.data && eq(t1.left, t2.left) && eq(t1.right, t2.right)

Причина в том, что несоответствия, скорее всего, будут общими, и лучше обнаружить (и прекратить сравнение) раньше - до повторного поиска. Конечно, я предполагаю короткое замыкание && оператора здесь.

Я также укажу, что это замаскирует некоторые проблемы с правильной обработкой структурно разных деревьев и заканчивая рекурсией. В принципе, для t1.left и т.д. Должны быть некоторые нулевые проверки. Если одно дерево имеет null.left, а другое - нет, вы обнаружили структурную разницу. Если у обоих есть null.left, нет никакой разницы, но вы достигли листа - не рекурсивно. Только если оба значения .left не равны нулю, вы рекурсивно проверяете поддерево. То же самое относится, конечно, к .right.

Вы можете включить проверки, например. (t1.left == t2.left), но это имеет смысл только в том случае, если поддеревья могут быть физически разделены (те же узлы структуры данных) для двух деревьев. Эта проверка будет еще одним способом избежать повторения, где это не нужно - если t1.left и t2.left - это то же физическое node, вы уже знаете, что все целые поддеревья идентичны.

Реализация C может быть...

bool tree_compare (const node* t1, const node* t2)
{
  // Same node check - also handles both NULL case
  if (t1 == t2)  return true;

  // Gone past leaf on one side check
  if ((t1 == NULL) || (t2 == NULL))  return false;

  // Do data checks and recursion of tree
  return ((t1->data == t2->data) && tree_compare (t1->left,  t2->left )
                                 && tree_compare (t1->right, t2->right));
}

EDIT В ответ на комментарий...

Время работы для полного сравнения деревьев с использованием этого наиболее просто указано как O (n), где n является видом размера дерева. Если вы готовы принять более сложную привязку, вы можете получить меньшую, такую ​​как O (минимум (n1, n2)), где n1 и n2 - размеры деревьев.

Объяснение в основном состоит в том, что рекурсивный вызов выполняется (не более) один раз для каждого node в левом дереве и только один раз (не более) для каждого node в правом дереве. Поскольку сама функция (исключая рекурсии) задает не более постоянной работы (нет циклов), работа, включающая в себя все рекурсивные вызовы, может быть равна только размеру меньшего времени дерева, которое является константой.

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

Одним из способов формирования привязки тигра является рассмотрение наборов путей к узлам в обоих деревьях. Каждый шаг - либо L (левое поддерево), либо R (правое поддерево). Таким образом, root задается пустым путем. Правым ребром левого дочернего элемента корня является "LR". Определите функцию "пути (T)" (математически - не часть программы), чтобы представить набор допустимых путей в дерево - один путь для каждого node.

Итак, мы могли бы...

paths(t1) = { "", "L", "LR", "R", "RL" }
paths(t2) = { "", "L", "LL", "R", "RR" }

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

Для структур дерева выше мы делаем рекурсии для следующих путей...

paths(t1) intersection paths(t2) = { "", "L", "R" }

Таким образом, наша работа в этом случае ограничена не более чем в три раза максимальной стоимостью нерекурсивной работы в функции tree_compare.

Обычно это ненужное количество деталей, но, очевидно, пересечение наборов путей не превосходит числа узлов в самом маленьком исходном дереве. И относится ли n к O (n) к числу узлов в одном исходном дереве или к сумме узлов в обоих, это явно не меньше, чем минимум или наше пересечение. Поэтому O (n) не является такой жесткой границей, но она все еще является правильной верхней границей, даже если мы немного туманны, о каком размере мы говорим.

Ответ 2

Переполнение стека Modulo, что-то вроде

eq(t1, t2) =
    eq(t1.left, t2.left) && t1.data=t2.data && eq(t1.right, t2.right)

(Это обобщает предикат равенства для всех древовидных типов алгебраических данных - для любой части структурированных данных проверяйте, равна ли каждая из его частей каждой из других частей).

Ответ 3

Мы также можем выполнить любой из двух обходов (предварительный, пост-порядок или в порядке), а затем сравнить результаты обоих деревьев. Если они одинаковы, мы можем быть уверены в их эквивалентности.

Ответ 4

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

Ответ 5

Поскольку доказанный факт: возможно воссоздать двоичное дерево, если у нас есть следующее:

• Последовательность узлов, встречающихся в обходном порядке.
• Последовательность узлов, встречающихся при обходе заказа или послепорядка

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

Каждый обход - это операция O (n). Обходы выполняются 4 раза в общей сложности и сравниваются результаты одного и того же типа обхода. O (n) * 4 + 2 = > O (n) Следовательно, полный порядок сложности времени будет O (n)

Ответ 6

Я бы написал его следующим образом. Следующий код будет работать на большинстве функциональных языков и даже на python, если ваши типы данных хешируются (например, не словари или списки):

• топологическое равенство (такое же по структуре, т.е. Tree(1,Tree(2,3))==Tree(Tree(2,3),1)):

  tree1==tree2 означает set(tree1.children)==set(tree2.children)

• упорядоченное равенство:

  tree1==tree2 означает tree1.children==tree2.children

(Tree.children - упорядоченный список детей)

Вам не нужно обрабатывать базовые случаи (листья), потому что для них уже определено равенство.