Что означает то, чтобы два двоичных дерева были изоморфны?
Два подхода:
- Создать конечную точку «обертки», которая является просто прокси для самого конечного изображения (например, внутренне
readfile(), см. Это: https: // stackoverflow.com/a/1353867/1364793) - Храните изображения в статической, доступной через Интернет папке (или даже рассматривайте S3 как хранилище для статических ресурсов). Затем ваша основная конечная точка просто возвращает общедоступные URL-адреса.
2 ответа
Изоморфный происходит от греческого «той же формы» (как изобара это точки с одинаковым давлением воздуха, а многоугольник означает «много односторонний "), так что ваше понимание верно. Но не делайте ошибку, предполагая, что форма в этом случае является физической формой (как дерево имеет один корень, один левый узел и один правый узел; см., Например, ниже). У математиков есть свой собственный язык, который только иногда имеет преходящее отношение к английскому: -)
Это не просто двоичные деревья. В математике две структуры изоморфны, если их свойства сохраняются независимо от их выражения (у вас может быть функция, которая переводит 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
Конечно, несортированное дерево может рассматриваться как пустая трата в зависимости от ваших потребностей, но это не имеет отношения к данному конкретному обсуждению.
Я думаю, что ваше понимание в значительной степени верно. Если вы игнорируете значения и просто посмотрите на структуру, то для каждого узла в первом дереве должен быть соответствующий узел в другом дереве, и наоборот.
Естественно, что оба дерева будут иметь одинаковое количество узлов. Кроме того, вы можете написать (наивный) алгоритм для подтверждения этого изоморфизма, пытаясь выполнить все возможные функции отображения и убедившись, что для каждого узла в первом дереве, которое отображается на узел в другом, соответствующее отображение происходит с родитель и с двумя детьми. Очевидно, существуют эффективные алгоритмы для проверки этого.
Вы можете сначала прочитать о изоморфизме графа ; деревья - это особый (и их легче решить) случай, поскольку у них нет циклов.