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

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

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 - один и тот же физический узел, вы уже знаете, что все эти поддеревья идентичны.

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

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));
}

РЕДАКТИРОВАТЬ В ответ на комментарий ...

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

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

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

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

Таким образом, мы могли бы иметь ...

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) не такая уж строгая граница, но это все еще допустимая верхняя граница, даже если мы немного не уверены, о каком размере идет речь.

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

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

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

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