Алгоритмы на деревьях. Есть ли подсказки, которые помогают указать способ эффективного решения?

Question

Я делаю переписку по основам и алгоритмам CS.

Я хочу убедиться, что я что-то понял правильно.

Когда я читаю подсказки типа bottom-up и top-down и т. Д., Правильно ли я понимаю, что они всегда должны восприниматься следующим образом?
bottom-up -> post-order traversal
top-down -> pre-order traversal
??? -> in-order traversal

Мне неясно, какой тип подсказки подразумевает прохождение по порядку;
Также есть более полный список подсказок о различных подходах, чем этот?
Я имею в виду, возможно, есть другие подсказки, которые указывают на итерацию вместо рекурсии, например?

Я думаю, что если я смогу так или иначе классифицировать, это поможет мне решить алгоритмические проблемы намного легче

Любой вклад высоко ценится.

Answer 1

Снизу вверх и сверху вниз - термины, не связанные напрямую с обходом дерева, а с обработкой информации.

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

Сверху вниз - аналитическая стратегия разложения. Например, вы разбиваете проблему на более мелкие части, которые легче обрабатывать.

Answer 2

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

Поскольку вы запрашиваете дополнительные источники руководства, я бы предложил поискать учебник или онлайн-ресурс, который объясняет принципы. Работать с проблемами - это хорошо, но иногда хорошо, когда мне дают общую картину. Боюсь, я не знаю, что можно предложить.

Answer 3

Поскольку вы запрашиваете ссылки, вам следует перейти в такие места, как wikipedia , geekviewpoint и topcoder .

Для википедии вы можете искать «алгоритмы».Для других ссылок просто перейдите по ним.