PostOrder Traversal с использованием одного стека
Я пытаюсь разобраться в понимании обхода дерева DFS с помощью стека. Я нахожу это довольно интуитивно понятным при преобразовании рекурсивного решения в итеративное для обхода предварительного заказа. Тем не менее, мне трудно понять прохождение пост-заказа по этой ссылке. https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/. Есть ли интуитивный и простой способ думать об этом?
Код предзаказа:
void iterativePreorder(node *root)
{
// Base Case
if (root == NULL)
return;
// Create an empty stack and push root to it
stack<node *> nodeStack;
nodeStack.push(root);
/* Pop all items one by one. Do following for every popped item
a) print it
b) push its right child
c) push its left child
Note that right child is pushed first so that left is processed first */
while (nodeStack.empty() == false)
{
// Pop the top item from stack and print it
struct node *node = nodeStack.top();
printf ("%d ", node->data);
nodeStack.pop();
// Push right and left children of the popped node to stack
if (node->right)
nodeStack.push(node->right);
if (node->left)
nodeStack.push(node->left);
}
}
Решение
С обходом предварительного заказа, код
- отображает данные для текущего узла
- пересекает левое поддерево
- проходит правильное поддерево
С прохождением заказа, код
- пересекает левое поддерево
- проходит правильное поддерево
- отображает данные для текущего узла
Таким образом, разница заключается в том, что данные должны храниться в стеке при выполнении обхода после заказа, чтобы их можно было распечатать последним. Есть несколько способов сделать это. Один из способов — изменить реализацию стека, чтобы различать дочерние указатели и указатели данных.
Когда дочерний указатель выталкивается, действия
- выдвинуть текущий узел в качестве указателя данных
- нажмите правый узел как дочерний указатель
- нажмите левый узел как дочерний указатель
Когда указатель данных извлечен, действие
- отобразить данные для узла
Затем обход начинается нажатием корневого узла в качестве дочернего указателя.
Другие решения
Хотя код сложнее, итеративный порядок размещения может быть более интуитивным, чем другие обходы, потому что другие были реорганизованы, в то время как этот не может быть аналогичным образом реорганизован.
Используйте первое решение здесь:
https://articles.leetcode.com/binary-tree-post-order-traversal/
Интуиция заключается в том, что у рекурсивных функций есть информация, которой нет у итерационных методов, в основном это направление обхода. Когда рекурсивная функция выполняется или откатывается, она знает, откуда она взялась, по какой строке кода она выполняется. То есть, если вы печатаете или обрабатываете текущий узел, вы знаете, что уже посетили детей, потому что они уже были вызваны рекурсивно.
Итеративное решение может отслеживать его, используя указатель «предыдущий», поэтому вы видите проверки «если предыдущий не является ни дочерним элементом текущего узла», то это означает, что вы переходите вниз и вам нужно идти влево. Другие возможности состоят в том, что предыдущий исходил от левого или правого дочернего узла. После того, как все случаи обработаны, у вас есть решение.