Что означает, что для двух бинарных деревьев изоморфны?

Ответ 1

Изоморфный происходит от греческой "той же формы" (например, изобара - это точки с одинаковым давлением воздуха, а полигон означает "многосторонний" ), поэтому ваше понимание правильное. Но не делайте ошибки при принятии формы в этом случае - это физическая форма (например, дерево имеет один корень, один слева node и один правый node, см. Ниже, например). Математики имеют свой язык, который только иногда имеет отношение к английскому: -)

Это не просто бинарные деревья. В математике две структуры изоморфны, если их свойства сохраняются независимо от их выражения (вы можете иметь функцию, которая переводит A в B, а другую из B в без потери информации).

В вашем конкретном случае это информация в сохраненном дереве. Например, если эта информация является отсортированным элементом {1,2,3}, то дерево не обязательно должно быть одной и той же физической формой - следующие два будут изоморфными:

  2      1
 / \      \
1   3      2
            \
             3

Сортированный связанный список (или отсортированный массив, если на то пошло) также изоморфен тем, что в этом случае никакая информация не будет потеряна при преобразованиях между ними.

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

  2      1           2   3                   +---+  +---+  +---+
 / \      \         /     \      +-------+   | 3 |->| 1 |->| 2 |
1   3      2       1       2     | 1,3,2 |   +---+  +---+  +---+
            \     /         \    +-------+
             3   3           1

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

Ответ 2

Следующие условия должны удовлетворять двум деревьям, чтобы быть изоморфными:
1. Два дерева изоморфны тогда и только тогда, когда они сохраняют одинаковое количество уровней и одинаковое число вершин на каждом уровне.

2. Два дерева изоморфны тогда и только тогда, когда они имеют одинаковый спектр степени.

3. Два дерева изоморфны тогда и только тогда, когда они имеют одинаковую степень спектра на каждом уровне.

4. Общее количество конечного потомка вершины и номер уровня вершины являются изоморфным инвариантом дерева дерева.

IN Простые слова:
Два дерева изоморфны, если одно дерево можно получить из другого, выполнив любое количество переводов, заменяя левые дочерние и правые дочерние числа числа node.

Пример изоморфных деревьев:

Ref: 1. http://www14.in.tum.de/konferenzen/Jass03/presentations/eterevsky.pdf 2. http://www.geeksforgeeks.org/tree-isomorphism-problem/

Ответ 3

Я думаю, что ваше понимание в значительной степени правильное. Если вы игнорируете значения и просто смотрите на структуру, то для каждого node в первом дереве должен быть соответствующий node в другом дереве и наоборот.

Естественно, что оба дерева будут иметь одинаковое количество узлов. Кроме того, вы можете написать (супер-наивный) алгоритм, чтобы подтвердить этот изоморфизм, пытаясь использовать все возможные функции отображения и гарантируя, что для каждого node в первом дереве, которое сопоставляется с node в другом, соответствующее сопоставление происходит с родителем и двумя детьми. Для этого есть, очевидно, эффективные алгоритмы.

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