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

Ответ 1

Когда использовать Стратегию отслеживания заказа, In-Order и Post-Order

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

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

Предпросмотр обхода:

Сводка: начинается с корня (7), заканчивается в самом правом node ( 10)

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

Обход в порядке:

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

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

Постобработка:

Сводка: начинается с самого левого node (0), заканчивается корнем ( 7)

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

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

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

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

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

• Если вы знаете, что дерево имеет неотъемлемую последовательность в узлах, и вы хотите сгладить дерево обратно в исходную последовательность, то следует использовать обход in-order. Дерево будет сплющено так же, как оно было создано. Прохождение по порядку или по порядку может не отменить дерево обратно в последовательность, которая была использована для его создания.

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

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
}

Ответ 2

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

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

Ответ 3

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

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

В порядке:: для получения значений node в неупорядоченном порядке

Post-order:: если вы хотите удалить дерево из листа в корень

Ответ 4

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

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

x := y + 32

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

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

Ответ 5

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

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