как увидеть, если 2 бинарных дерева похожи?

Question

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

Пример

     A               A
  |     |         |     |
  B     C         C     B
 | |   | |       | |   | |
 D E   F G       G D   E F

Левое двоичное дерево похоже на правое (очевидно, существует множество вариантов!)

Вот мой psuedocode, который у меня есть:

if( tree1 == NULL && tree2 == NULL ) return TRUE;

if( tree1 == NULL || tree2 == NULL ) return FALSE;

if( tree1->label != tree2->label ) return FALSE;

return (   TRUE
        && (  (   similarTrees(tree1->left, tree2->left)
               && similarTrees(tree1->right, tree2->right))
            || (   similarTrees(tree1->left, tree2->right)
                && similarTrees(tree1->right, tree2->left))  ));

Мое рассуждение состояло в том, что, поскольку два левых поддерева могут быть равны, а два правых поддерева могут быть равны ИЛИ левый и правый от одного и правый и левый от другого могут быть равны, то эта логическая рекурсия должна работать ... однако это не так.

SimilarTree - рекурсивная функция

Спасибо за вашу помощь!

Answer 1

Код и пример не совпадают.

Код предполагает, что деревья равны, если каждое поддерево содержит одинаковую корневую метку и одинаковые дочерние элементы, хотя и в произвольном порядке.

пример, с другой стороны, не относится к этому.Например, в левом дереве потомками C являются F и G, тогда как в правом G и D.

Чтобы написать код, чтобы проверить, схожи ли они,Сначала вы должны четко определить, что значит быть похожим.Например, если на обоих деревьях есть метка.Должен ли он существовать на одном уровне?Может ли это произойти более одного раза?

Answer 2

Взгляните на ширину первого обхода .

1. Вы можете получить элементы на одном уровне.

2. затем сравните уровни, имеют ли они одинаковые элементы, отсортировав полученные списки.

Answer 3

вы можете решить, являются ли они одной структурой для первого шага, и использовать мой шаг для второго шага

для уровня дерева, вы можете собирать данные с того же уровня в один и тот же набор (или сортироватьlist)

Очевидно, что если набор всех уровней дерева равен уровню другого дерева, и они имеют одинаковую структуру, эти два дерева похожи