Предварительный заказ, порядок и обход дерева заказов

Question

Меня смущают порядок, обратный и последующий обходы, а именно этот, Предварительный заказ: ABAB, Почтовый заказ: BABA, В заказе: AABB.

Я понимаю, что корень - это первый и последний элемент Pre и Post, но я не понимаю, как завершить построение двоичного дерева.

Answer 1

Ваше сообщение расплывчато и не имеет особого смысла, но я объясню, предварительно, после размещения заказа и построения двоичного дерева для вас.

Одна из причин, по которой ваш вопрос не имеет смысла, заключается в том, что вы не установили порядок для элементов, которые вы описываете при упорядочении. ABAB BABA и AABB абсолютно ничего не значат без дерева, чтобы правильно показать, куда идет каждый элемент (и каждый элемент письмо? почему они дублируют)

Другая причина, по которой ваш вопрос не имеет смысла, заключается в том, что вы, кажется, думаете, что pre, pos и order имеют какое-то отношение к созданию бинарного дерева, а они нет.

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

Представьте себе следующее двоичное дерево (одинаковое для всех примеров)

     A
   B   C
  D E F G

Обход предзаказа - это тип алгоритма обхода дерева, в котором вы всегда сначала выбираете самый левый путь. Когда вы не можете идти дальше, вы выбираете следующий левый путь и делаете то же самое рекурсивно на следующем узле. В приведенном выше примере дерева обход предзаказа начинался бы с корня, (A) идти налево (A,B) снова идти налево (D) не мог идти налево, а затем шел направо (E), и в конце концов вы бы в итоге получим следующую последовательность обходов: A B D E C F G

Порядок обхода аналогичен обходу предзаказа, но вместо того, чтобы отображаться на каждом шаге, порядок обхода идет до самого левого края, который он может пройти, затем отображает, и, если он не может идти достаточно глубоко, он возвращается обратно, отображает (следовательно, в "порядке") и снова рекурсивно пытается повторить то же самое вправо, пока это не будет сделано. В примере с деревом мы сначала напечатали бы D, вернулись бы к B, и напечатали B, затем E, затем снова к A и так далее, так что окончательный результат будет D B E A F G C, Обратите внимание, что пример Wikipedias может иметь больше смысла, поскольку он более сложный.

В последующем порядке мы печатаем снизу вверх, мы находим самый глубокий узел в левом поддереве и рекурсивно печатаем самые глубокие узлы там, пока не закончим, переходим к правому поддереву и, наконец, печатаем корень, например: D E B F G C A, Опять же, этот пример имеет больше смысла в Википедии, поскольку у них более сложное дерево.

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

Этот пост также хорошо объясняет обходные пути, если этого недостаточно, он также объясняет, почему вам нужны разные типы упорядочения для построения дерева из последовательности узлов с правильными связями (если вы изначально пытались скопировать двоичное дерево состав)