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

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

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

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

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

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

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

Обход предварительного заказа :

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

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

Обход по порядку :

Сводка: начинается в крайнем левом узле ( 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. Если вы знаете, что вам нужно исследовать все листья перед любыми узлами, вы выбираете пост-заказ, потому что вы не тратите время на проверку корней в поисках листьев.

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

Рекурсивные алгоритмы для предварительного заказа, выполнения и пост-заказа (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
}

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

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

Пост-заказ:: Используется для удаления дерева от листа к корню

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

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

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

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

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

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

x := y + 32

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

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