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

Question

Что означает, что два бинарных дерева изоморфны? Я искал в Интернете, и я не могу найти четкое объяснение.

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

Answer 1

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

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

Для вашего конкретного случая это информация в дереве, которая сохраняется. Например, если эта информация представляет собой отсортированные элементы {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

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

Answer 2

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

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

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

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

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

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

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

Answer 3

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

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

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