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