Это может быть очень наивно, но мне было интересно, это контекст бинарных деревьев (простые, отсортированные и сбалансированные) всех типов обхода:
- предварительный заказ в глубину
- в порядке глубины
- первый заказ на глубину
- в ширину
Какова реальная полезность до и после заказа? Я имею в виду, есть ли какой-то тип и / или конфигурация бинарного дерева, в котором обход до и / или после заказа даст (некоторые) преимущество (преимущества) над двумя другими?
AFAICS, существуют определенные типы и конфигурации бинарных деревьев, для которых порядок и ширина могут дать определенное преимущество:
для сбалансированного двоичного дерева любой обход в глубину будет использовать меньше места для хранения памяти по сравнению с шириной вначале (например, для сбалансированного двоичного дерева из 6 или 7 узлов высота равна 2, поэтому при любом обходе в глубину необходимо хранить максимум 2 узла в любой момент времени, в то время как последний уровень имеет 3 или 4 узла, поэтому обход в ширину должен хранить до 3 или 4 узлов в некоторой точке). В этом случае использование обхода по порядку использует наименьшее количество памяти и посещает узлы в их естественном порядке.
для несбалансированного двоичного дерева, если оно близко к сценарию вставки в наихудшем случае, при обходе его в ширину потребовалось бы меньше памяти по сравнению с любым обходом в глубину. Так что в этом случае ширина в первую очередь дает преимущество. Обратный путь по порядку имеет еще одно преимущество - посещение значений в их естественном порядке.
Однако я не могу придумать ситуацию, в которой пре и посттраверсальный переход давали бы преимущество перед двумя другими.
источник
С деревьями нужно делать разные вещи, такие как перевод между структурой данных и некоторым последовательным представлением, например, в файле или на языке.
Например, предположим, что у вас есть дерево разбора, например:
Вы могли бы сериализовать его как
* + A B C
в порядке префикса илиA B + C *
в порядке постфикса. Если вы вообще работаете с языковыми процессорами, такие вещи должны быть второстепенными.источник
A + B * C
, что гораздо проще понять обычным пользователям, чем любой префикс порядка постфикса.Смысл использования разных алгоритмов для работы с бинарными деревьями состоит не в том, чтобы работать с деревьями. На этом абстрактном уровне один порядок в значительной степени так же хорош, как и любой другой, поскольку вы извлекаете только абстрактные символы из процедуры.
Но деревья обычно используются для представления интересных вещей, и это может иметь большое значение в результате. Например, если узлы представляют состояния поиска в полном поиске по большому домену (может быть, даже бесконечному домену), сначала по убыванию против обработки сначала не только определяется, в каком порядке будут найдены результаты, он может даже определить , будете ли вы когда-либо найти какие-либо решения на всех . Эту точку легче всего увидеть с бесконечными доменами: если вы неосторожно спускаетесь, вы можете упустить из виду решение, которое лежит довольно высоко в дереве, просто потому, что вы сделали неправильный поворот. Но на практике, поскольку память и диски также конечны, это относится даже к доменам, которые просто очень велики, а не бесконечны.
источник