Судя по комментариям, вам надо найти полное совподение поддерева: Так что поддерево вершины имеет ровно столько же точно также расставленных вершин, как и второе дерево.
Умное и быстрое решение, к сожалению, будет сложно написать без std::unordered_map. Такое решение будет работать за O(n). Самостоятельно хеш таблицу писать будет сложно. Но если без хеш таблицы, то решение будет работать также медленно, как и тупое рекурсивное прикладывание, поэтому приведу тут все решение.
Основная идея - надо классифицировать все вершины по форме их поддеревьев. Назначить каждой форме номер. Потом остается только найти вершины с тем же номером, что и корень второго дерева.
Для нумерации форм надо рекурсивно получить номера для двух детей и потом проверить, а встречали ли вы раньше вершину с двумя такими детьми. Если да - то вы знаете ее номер. Если нет - то назначьте новый номер. Вот тут и нужена хеш таблица, она же unordered_map.
Пустые вершины всегда имеют какой-то номер, допустим, 0.
Это решение, кстати, легко адаптируется на изоморфизм - если вам можно менять местами детей. Тогда пары надо отсортировать перед проверкой. Также оно адаптируется на небинарные деревья. Тут у вас будут не пары чисел, а набор чисел.
void Match(Tree *stack, Tree *needle) {
std::unordered_map<std::pair<int, int>, int> shapes;
int needle_shape = ClassifyShape(needle, shapes, -1);
ClassifyShape(stack, shapes, needle_shape);
}
int ClassifyShape(Tree *tree, std::unordered_map<std::pair<int, int>, int> &shape, int find_shape) {
if(!tree) return 0;
int l = ClassifyShape(tree->left);
int r = ClassifyShape(tree->right);
auto pat = make_pair(l, r);
auto it = shapes.find(pat);
int this_shape = -1;
if (it == shapes.end()) {
this_shape = shapes.size();
shapes[pat] = this_shape;
} else {
this_shape = it->second;
}
if (this_shape == find_shape) {
std::cout << "Found match at node " << tree->value << std::endl;
}
return this_shape;
}
В нивном решении надо заменить unordered_map shapes на массив пар чисел (или массив структур или два массива чисел). Циклом в нем проищите текущую пару l, r, если не нашли, то допишите в конец.
Тут можно даже без vector обойтись, потому что вы знаете, сколько максимум будет пар чисел в этом массиве - сколько суммарно вершин деревьях.
Но, возможно вашему преподу такое будет слишком заумно. Тогда вам нужна аккуратная рекурсивная функция сравнения:
bool Compare(Tree* a, Tree *b) {
if (a->left && !b->left) return false;
if (a->right && !b->right) return false;
return (!a->left || Compare(a->left, b->left)) && (!a->right || Compare(a->right, b->right));
}
Тут все просто. Если у корней разная конфигурация детей, то деревья точно не совпали. А дальше надо чтобы рекурсивно совпали поддеревья в левых и правых детях.
А дальше вам надо рекурсивно пройтись по первому дереву и вызвать вот эту Compare для текущей вершины и корня второго дерева. Если совпало - то выводите текущую вершину.
