PostOrder Traversal с использованием одного стека

Question

Я пытаюсь понять, как обходить дерево 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);
    }
}

Answer 1

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

Используйте первое решение здесь: https://articles.leetcode.com/binary-tree-post-order-traversal/

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

Итеративное решение может отслеживать его с помощью «предыдущего» указателя, поэтому вы видитепроверка «если предыдущий не является ни дочерним элементом текущего узла», то это означает, что вы двигаетесь вниз и вам нужно идти влево.Другие возможности состоят в том, что предыдущий исходил от левого или правого дочернего узла.Как только все дела будут рассмотрены, у вас есть решение.

Answer 2

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

• отображает данные для текущего узла
• пересекает левое поддерево
• пересекает правое поддерево

При обходе после заказа код

• пересекает левое поддерево
• пересекает правое поддерево
• отображает данные для текущего узла

Таким образом, разница заключается в том, что данные должны храниться в стеке при выполнении обхода после заказа, чтобы их можно было распечатать последним.Есть несколько способов сделать это.Один из способов - изменить реализацию стека, чтобы различать дочерние указатели и указатели данных.

Когда дочерний указатель извлечен, действиями являются

• выдвижение текущего узла в качестве указателя данных
• выдвижение правого узла в качестве дочернего указателя
• нажмите левый узел как дочерний указатель

Когда указатель данных извлечен, действие

• отображает данные для узла

Затем обход начинается нажатием корневого узла в качестве дочернего указателя.