Когда следует использовать стратегии обхода дерева бинарного поиска по предзаказу, порядку и порядку

Question

Недавно я осознал, что, используя в своей жизни множество BST, я даже не задумывался об использовании чего-либо, кроме обхода Inorder (хотя я знаю и знаю, как легко адаптировать программу для использования до / после заказаОбход).

Осознав это, я вытащил некоторые из моих старых учебников по структурам данных и попытался найти обоснование полезности обходов до и после заказа - хотя они мало что сказали.

Какие примеры того, когда практически использовать предварительный заказ / почтовый заказ?Когда это имеет больше смысла, чем в заказе?

Answer 1

Когда следует использовать стратегию предзаказа, порядка и пост-порядка обхода

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

Корень дерева - 7 , самый левый узел - 0 , самый правый узел - 10 .

Предварительный заказ :

Краткое описание: начинается с корня ( 7 ), заканчивается у правого краяузел ( 10 )

Последовательность обхода: 7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10

Inпорядок обхода :

Сводка: начинается в крайнем левом узле ( 0 ), заканчивается в крайнем правом узле ( 10 )

последовательность обхода: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

обход после заказа :

Резюме: Начинается с самого левого узла ( 0 ), заканчивается корнем ( 7 )

Последовательность обхода: 0, 2, 4, 6, 5,3, 1, 8, 10, 9, 7

Когда использовать Предзаказ, Заказ или Пост-заказ?

Стратегия обхода, которую выбирает программист, зависит от конкретных потребностейалгоритм разрабатывается.Цель - скорость, поэтому выберите стратегию, которая обеспечит вам самые быстрые узлы.

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

2. Если вы знаете, что вам нужно исследовать все листья перед любыми узлами, вы выбираете post-order , потому что вы не тратите время на поиск корней в поискеуходит.

3. Если вы знаете, что у дерева есть внутренняя последовательность в узлах, и вы хотите сгладить дерево обратно в исходную последовательность, чем по порядку *Следует использовать 1071 * обход.Дерево будет сплющено так же, как оно было создано.Обход при предварительном заказе или после заказа может не развернуть дерево обратно в последовательность, которая использовалась для его создания.

Рекурсивные алгоритмы для предварительного заказа, заказа и пост-заказазаказ (C ++):

struct Node{
    int data;
    Node *left, *right;
};
void preOrderPrint(Node *root)
{
  print(root->name);                                  //record root
  if (root->left != NULL) preOrderPrint(root->left);  //traverse left if exists
  if (root->right != NULL) preOrderPrint(root->right);//traverse right if exists
}

void inOrderPrint(Node *root)
{
  if (root.left != NULL) inOrderPrint(root->left);   //traverse left if exists
  print(root->name);                                 //record root
  if (root.right != NULL) inOrderPrint(root->right); //traverse right if exists
}

void postOrderPrint(Node *root)
{
  if (root->left != NULL) postOrderPrint(root->left);  //traverse left if exists
  if (root->right != NULL) postOrderPrint(root->right);//traverse right if exists
  print(root->name);                                   //record root
}

Answer 2

Если бы я хотел просто распечатать иерархический формат дерева в линейном формате, я бы, вероятно, использовал обход по предварительному заказу.Например:

- ROOT
    - A
         - B
         - C
    - D
         - E
         - F
             - G

Answer 3

Предзаказ / Заказ / Постзаказ Использование: Простые слова

Предварительный заказ: Используется для создания копии дерева Пример: если вы хотите создать реплику дерева и вам нужны значения узлов в массиве, и когда вы вставляете эти значения от индекса 0 до конца в новом дереве, вы получаете реплику

В порядке: : Получить значения узла в неубывающем порядке

Пост-заказ: : Когда вы хотите удалить дерево из листа в корень

Answer 4

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

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

Answer 5

Есть множество мест, где вы видите, что эта разница играет реальную роль.

Один замечательный момент, на который я укажу, - это генерация кода для компилятора Рассмотрим утверждение:

x := y + 32

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

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