非递归后序遍历

Question

我在一些网站上看到了以下后序遍历算法......它似乎是正确的。我只是想验证这个算法是否正确工作——这个算法对于没有递归的后序遍历是否正确？

void postOrderTraversal(Tree *root)
{
    node * previous = null;
    node * s = null;
    push(root);
    while( stack is not empty )
    {
        s = pop();

        if(s->right == null and s->left == null)
        {
            previous = s;
            process s;
        }
        else
        {
            if(s->right == previous or s->left == previous)
            {
                previous = s;
                process s;
            }
            else
            {
                push( s );
                if(s->right) { push(s->right); }
                if(s->left)  { push(s->left);  }
            }
        }
    }
}

Answer 1

尝试编写前序、中序和后序二进制遍历方法的迭代版本。然后，您将看到将相应的递归版本转换为迭代版本的模式或方法。

关键点是遵守一些基本规则：

- 使用节点选择（例如，在重复循环之前，currentNode=currentNode->Left，等等）来进行立即节点遍历。

- 使用堆栈来记住需要访问或稍后重新访问的节点。

- 如果需要“重新访问”节点，则检测/保留状态，以便您可以指示是否需要在下一次迭代中“处理”下一个节点，或者在可以访问该节点之前是否应该访问多个子节点之一已处理。

如果你遵守这些规则，你就能轻松完成任务。

这是迭代后序遍历的示例。忽略 BinarySearchTree - 它适用于任何二叉树。

    public static IEnumerator<BinarySearchTreeNode<T>> GetPostOrderTraverseEnumerator(BinarySearchTreeNode<T> root)
    {
        if (root == null)
        {
            throw new ArgumentNullException("root");
        }

        Stack<BinarySearchTreeNode<T>> stack = new Stack<BinarySearchTreeNode<T>>();

        BinarySearchTreeNode<T> currentNode = root;

        // If the following flag is false, we need to visit the child nodes first
        // before we process the node.
        bool processNode = false;

        while (true)
        {
            // See if we need to visit child nodes first
            if (processNode != true)
            {
                if (currentNode.Left != null)
                {
                    // Remember to visit the current node later
                    stack.Push(currentNode);

                    if (currentNode.Right != null)
                    {
                        // Remember to visit the right child node later
                        stack.Push(currentNode.Right);
                    }

                    // Visit the left child
                    currentNode = currentNode.Left;
                    continue;
                }
                else if (currentNode.Right != null)
                {
                    // Remember to visit the current node later
                    stack.Push(currentNode);

                    // Visit the right child
                    currentNode = currentNode.Right;
                    continue;
                }
            }

            // Process current node
            yield return currentNode;

            // See if we are done.
            if (stack.Count == 0)
            {
                break;
            }

            // Get next node to visit from the stack
            BinarySearchTreeNode<T> previousNode = currentNode;
            currentNode = stack.Pop();

            // See if the next node should be processed or not
            // This can be determined by the fact that either of the current node's child nodes
            // has just been processed now.
            processNode = (previousNode == currentNode.Left || previousNode == currentNode.Right);
        }
    }

Answer 2

否 这里 prev 不应以 null 开头
例如：对于具有节点 5 2 1 3 7 6 8 0 的 bst
它不会考虑零，因为在 1 时，它的右侧为空，这次前一个也将为空，因此它不会考虑其左侧孩子，即 0
写入 previous=任何值但不为空

Answer 3

这是工作代码

Stack s=new Stack();
    while(true){
       if(root!=null){
           s.push(root);
           root=root.left;
       }
       else{
            if(s.top().right==NULL){
               root=s.top();
               s.pop();
               System.out.println(root.data);
               if(root==s.top().right){
                    System.out.println(s.top().data);
                    s.pop();
               }
            }
       if(!s.empty())
          root=s.top().right;
       else 
          root=NULL;

       }
    }