Ответ 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
}