logo标签列表

二叉树的后序遍历（不使用递归）

binary-treetraversalnon-recursive
70

如何不使用递归算法遍历二叉树的后序遍历？

这里有一个很好的描述：http://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/ - user793623
30个回答
0

这里我正在粘贴不同版本的 c# (.net) 以供参考： (对于中序迭代遍历，您可以参考：帮助我理解如何在不使用递归的情况下进行中序遍历)

  1. 维基百科（http://en.wikipedia.org/wiki/Post-order%5Ftraversal#Implementations）（优雅）
  2. 单栈的另一种版本 （＃1和＃2：基本上利用了后序遍历中右子节点在访问实际节点之前被访问的事实 - 因此，我们只需依赖检查堆栈顶部的右子节点是否确实是最后一个已访问的后序遍历节点 - 我已在下面的代码片段中添加了注释以获取详细信息）
  3. 使用两个堆栈版本（参考：http://www.geeksforgeeks.org/iterative-postorder-traversal/） （更容易：基本上，后序遍历的反转不过是先序遍历，只需简单地将右节点先访问，然后再访问左节点即可）
  4. 使用访问标志（简单）
  5. 单元测试

~

public string PostOrderIterative_WikiVersion()
        {
            List<int> nodes = new List<int>();
            if (null != this._root)
            {
                BinaryTreeNode lastPostOrderTraversalNode = null;
                BinaryTreeNode iterativeNode = this._root;
                Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
                while ((stack.Count > 0)//stack is not empty
                    || (iterativeNode != null))
                {
                    if (iterativeNode != null)
                    {
                        stack.Push(iterativeNode);
                        iterativeNode = iterativeNode.Left;
                    }
                    else
                    {
                        var stackTop = stack.Peek();
                        if((stackTop.Right != null)
                            && (stackTop.Right != lastPostOrderTraversalNode))
                        {
                            //i.e. last traversal node is not right element, so right sub tree is not
                            //yet, traversed. so we need to start iterating over right tree 
                            //(note left tree is by default traversed by above case)
                            iterativeNode = stackTop.Right;
                        }
                        else
                        {
                            //if either the iterative node is child node (right and left are null)
                            //or, stackTop's right element is nothing but the last traversal node
                            //(i.e; the element can be popped as the right sub tree have been traversed)
                            var top = stack.Pop();
                            Debug.Assert(top == stackTop);
                            nodes.Add(top.Element);
                            lastPostOrderTraversalNode = top;
                        }
                    }
                }
            }
            return this.ListToString(nodes);
        }

这是使用一个栈的后序遍历（我的版本）

public string PostOrderIterative()
        {
            List<int> nodes = new List<int>();
            if (null != this._root)
            {
                BinaryTreeNode lastPostOrderTraversalNode = null;
                BinaryTreeNode iterativeNode = null;
                Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
                stack.Push(this._root);
                while(stack.Count > 0)
                {
                    iterativeNode = stack.Pop();
                    if ((iterativeNode.Left == null)
                        && (iterativeNode.Right == null))
                    {
                        nodes.Add(iterativeNode.Element);
                        lastPostOrderTraversalNode = iterativeNode;
                        //make sure the stack is not empty as we need to peek at the top
                        //for ex, a tree with just root node doesn't have to enter loop
                        //and also node Peek() will throw invalidoperationexception
                        //if it is performed if the stack is empty
                        //so, it handles both of them.
                        while(stack.Count > 0) 
                        {
                            var stackTop = stack.Peek();
                            bool removeTop = false;
                            if ((stackTop.Right != null) &&
                                //i.e. last post order traversal node is nothing but right node of 
                                //stacktop. so, all the elements in the right subtree have been visted
                                //So, we can pop the top element
                                (stackTop.Right == lastPostOrderTraversalNode))
                            {
                                //in other words, we can pop the top if whole right subtree is
                                //traversed. i.e. last traversal node should be the right node
                                //as the right node will be traverse once all the subtrees of
                                //right node has been traversed
                                removeTop = true;
                            }
                            else if(
                                //right subtree is null
                                (stackTop.Right == null) 
                                && (stackTop.Left != null) 
                                //last traversal node is nothing but the root of left sub tree node
                                && (stackTop.Left == lastPostOrderTraversalNode))
                            {
                                //in other words, we can pop the top of stack if right subtree is null,
                                //and whole left subtree has been traversed
                                removeTop = true;
                            }
                            else
                            {
                                break;
                            }
                            if(removeTop)
                            {
                                var top = stack.Pop();
                                Debug.Assert(stackTop == top);
                                lastPostOrderTraversalNode = top;
                                nodes.Add(top.Element);
                            }
                        }
                    }
                    else 
                    {
                        stack.Push(iterativeNode);
                        if(iterativeNode.Right != null)
                        {
                            stack.Push(iterativeNode.Right);
                        }
                        if(iterativeNode.Left != null)
                        {
                            stack.Push(iterativeNode.Left);
                        }
                    }
                }
            }
            return this.ListToString(nodes);
        }

使用两个栈
public string PostOrderIterative_TwoStacksVersion()
        {
            List<int> nodes = new List<int>();
            if (null != this._root)
            {
                Stack<BinaryTreeNode> postOrderStack = new Stack<BinaryTreeNode>();
                Stack<BinaryTreeNode> rightLeftPreOrderStack = new Stack<BinaryTreeNode>();
                rightLeftPreOrderStack.Push(this._root);
                while(rightLeftPreOrderStack.Count > 0)
                {
                    var top = rightLeftPreOrderStack.Pop();
                    postOrderStack.Push(top);
                    if(top.Left != null)
                    {
                        rightLeftPreOrderStack.Push(top.Left);
                    }
                    if(top.Right != null)
                    {
                        rightLeftPreOrderStack.Push(top.Right);
                    }
                }
                while(postOrderStack.Count > 0)
                {
                    var top = postOrderStack.Pop();
                    nodes.Add(top.Element);
                }
            }
            return this.ListToString(nodes);
        }

在C# (.net)中使用访问标志：

public string PostOrderIterative()
        {
            List<int> nodes = new List<int>();
            if (null != this._root)
            {
                BinaryTreeNode iterativeNode = null;
                Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
                stack.Push(this._root);
                while(stack.Count > 0)
                {
                    iterativeNode = stack.Pop();
                    if(iterativeNode.visted)
                    {
                        //reset the flag, for further traversals
                        iterativeNode.visted = false;
                        nodes.Add(iterativeNode.Element);
                    }
                    else
                    {
                        iterativeNode.visted = true;
                        stack.Push(iterativeNode);
                        if(iterativeNode.Right != null)
                        {
                            stack.Push(iterativeNode.Right);
                        }
                        if(iterativeNode.Left != null)
                        {
                            stack.Push(iterativeNode.Left);
                        }
                    }
                }
            }
            return this.ListToString(nodes);
        }

定义：

class BinaryTreeNode
    {
        public int Element;
        public BinaryTreeNode Left;
        public BinaryTreeNode Right;
        public bool visted;
    }

string ListToString(List<int> list)
        {
            string s = string.Join(", ", list);
            return s;
        }

单元测试

[TestMethod]
        public void PostOrderTests()
        {
            int[] a = { 13, 2, 18, 1, 5, 17, 20, 3, 6, 16, 21, 4, 14, 15, 25, 22, 24 };
            BinarySearchTree bst = new BinarySearchTree();
            foreach (int e in a)
            {
                string s1 = bst.PostOrderRecursive();
                string s2 = bst.PostOrderIterativeWithVistedFlag();
                string s3 = bst.PostOrderIterative();
                string s4 = bst.PostOrderIterative_WikiVersion();
                string s5 = bst.PostOrderIterative_TwoStacksVersion();
                Assert.AreEqual(s1, s2);
                Assert.AreEqual(s2, s3);
                Assert.AreEqual(s3, s4);
                Assert.AreEqual(s4, s5);
                bst.Add(e);
                bst.Delete(e);
                bst.Add(e);
                s1 = bst.PostOrderRecursive();
                s2 = bst.PostOrderIterativeWithVistedFlag();
                s3 = bst.PostOrderIterative();
                s4 = bst.PostOrderIterative_WikiVersion();
                s5 = bst.PostOrderIterative_TwoStacksVersion();
                Assert.AreEqual(s1, s2);
                Assert.AreEqual(s2, s3);
                Assert.AreEqual(s3, s4);
                Assert.AreEqual(s4, s5);
            }
            Debug.WriteLine(string.Format("PostOrderIterative: {0}", bst.PostOrderIterative()));
            Debug.WriteLine(string.Format("PostOrderIterative_WikiVersion: {0}", bst.PostOrderIterative_WikiVersion()));
            Debug.WriteLine(string.Format("PostOrderIterative_TwoStacksVersion: {0}", bst.PostOrderIterative_TwoStacksVersion()));
            Debug.WriteLine(string.Format("PostOrderIterativeWithVistedFlag: {0}", bst.PostOrderIterativeWithVistedFlag()));
            Debug.WriteLine(string.Format("PostOrderRecursive: {0}", bst.PostOrderRecursive()));
        }
0
请查看这个完整的Java实现。只需复制代码并粘贴到您的编译器中，它就可以正常工作。
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class Node
{
    Node left;
    String data;
    Node right;

    Node(Node left, String data, Node right)
    {
        this.left = left;
        this.right = right;
        this.data = data;
    }

    public String getData()
    {
        return data;
    }
}

class Tree
{
    Node node;

    //insert
    public void insert(String data)
    {
        if(node == null)
            node = new Node(null,data,null);
        else
        {
            Queue<Node> q = new LinkedList<Node>();
            q.add(node);

            while(q.peek() != null)
            {
                Node temp = q.remove();
                if(temp.left == null)
                {
                    temp.left = new Node(null,data,null);
                    break;
                }
                else
                {
                    q.add(temp.left);
                }

                if(temp.right == null)
                {
                    temp.right = new Node(null,data,null);
                    break;
                }
                else
                {
                    q.add(temp.right);
                }
            }
        }
    }

    public void postorder(Node node)
    {
        if(node == null)
            return;
        postorder(node.left);
        postorder(node.right);
        System.out.print(node.getData()+" --> ");
    }

    public void iterative(Node node)
    {
        Stack<Node> s = new Stack<Node>();
        while(true)
        {
            while(node != null)
            {
                s.push(node);
                node = node.left;
            }



            if(s.peek().right == null)
            {
                node = s.pop();
                System.out.print(node.getData()+" --> ");
                if(node == s.peek().right)
                {
                    System.out.print(s.peek().getData()+" --> ");
                    s.pop();
                }
            }

            if(s.isEmpty())
                break;

            if(s.peek() != null)
            {
                node = s.peek().right;
            }
            else
            {
                node = null;
            }
        }
    }
}

class Main
{
    public static void main(String[] args) 
    {
        Tree t = new Tree();
        t.insert("A");
        t.insert("B");
        t.insert("C");
        t.insert("D");
        t.insert("E");

        t.postorder(t.node);
        System.out.println();

        t.iterative(t.node);
        System.out.println();
    }
}
你的代码有一个漏洞：尝试使用“abcdefghi”，它会一直循环。 - Flethuseo
为了修复这个 bug，我将 'if (node == s.peek().right)' 改成了 ---> 'while (!s.isEmpty() && node == s.peek().right)'。 - Flethuseo
0

所以你可以使用一个栈来进行后序遍历。

private void PostOrderTraversal(Node pos) {
    Stack<Node> stack = new Stack<Node>();
    do {
        if (pos==null && (pos=stack.peek().right)==null) {
            for (visit(stack.peek()); stack.pop()==(stack.isEmpty()?null:stack.peek().right); visit(stack.peek())) {}
        } else if(pos!=null) {
            stack.push(pos);
            pos=pos.left;
        }
    } while (!stack.isEmpty());
}
0
void postorder_stack(Node * root){
    stack ms;
    ms.top = -1;
    if(root == NULL) return ;

    Node * temp ;
    push(&ms,root);
    Node * prev = NULL;
    while(!is_empty(ms)){
        temp = peek(ms);
        /* case 1. We are nmoving down the tree. */
        if(prev == NULL || prev->left == temp || prev->right == temp){
             if(temp->left)
                  push(&ms,temp->left);
             else if(temp->right)
                  push(&ms,temp->right);
             else {
                /* If node is leaf node */
                   printf("%d ", temp->value);
                   pop(&ms);
             }
         }
         /* case 2. We are moving up the tree from left child */
         if(temp->left == prev){
              if(temp->right)
                   push(&ms,temp->right);
              else
                   printf("%d ", temp->value);
         }

        /* case 3. We are moving up the tree from right child */
         if(temp->right == prev){
              printf("%d ", temp->value);
              pop(&ms);
         }
         prev = temp;
      }

}
0

最简单的解决方案，可能看起来不是最好的答案，但很容易理解。我相信如果你已经理解了这个解决方案，那么你可以修改它以得到最佳的解决方案。

// 使用两个栈

public List<Integer> postorderTraversal(TreeNode root){

 Stack<TreeNode> st=new Stack<>();
 Stack<TreeNode> st2=new Stack<>();
 ArrayList<Integer> al = new ArrayList<Integer>(); 

    if(root==null)
        return al;

 st.push(root);  //push the root to 1st stack

 while(!st.isEmpty())
 {
     TreeNode curr=st.pop();

     st2.push(curr);

     if(curr.left!=null)
        st.push(curr.left);
     if(curr.right!=null)
         st.push(curr.right);

 }

while(!st2.isEmpty())
    al.add(st2.pop().val);

//this ArrayList contains the postorder traversal

  return al;  
}
0
这是一个我需要用Python为一般树编写的短版本（行走者只有3行）。当然，也适用于更受限制的二叉树。树是节点和子节点列表的元组。它只有一个堆栈。显示了示例用法。
def postorder(tree):
    def do_something(x):  # Your function here
        print(x),
    def walk_helper(root_node, calls_to_perform):
        calls_to_perform.append(partial(do_something, root_node[0]))
        for child in root_node[1]:
            calls_to_perform.append(partial(walk_helper, child, calls_to_perform))
    calls_to_perform = []
    calls_to_perform.append(partial(walk_helper, tree, calls_to_perform))
    while calls_to_perform:
        calls_to_perform.pop()()
postorder(('a', [('b', [('c', []), ('d', [])])]))

a

b

c

d

0
在后序遍历中，先访问一个节点的左子节点，然后是右子节点，最后是该节点本身。此树遍历方法类似于图的深度优先搜索（DFS）遍历。
时间复杂度：O(n)
空间复杂度：O(n)
以下是Python中后序遍历的迭代实现：
class Node:
    def __init__(self, data=None, left=None, right=None):
        self.data  = data
        self.left  = left
        self.right = right

def post_order(node):
    if node is None:
        return []
    stack = []
    nodes = []
    last_node_visited = None
    while stack or node:
        if node:
            stack.append(node)
            node = node.left
        else:
            peek_node = stack[-1]
            if peek_node.right and last_node_visited != peek_node.right:
                node = peek_node.right
            else:
                nodes.append(peek_node.data)
                last_node_visited = stack.pop()
    return nodes

def main():
    '''
    Construct the below binary tree:

            15
           /  \
          /    \
         /      \
        10      20
       /  \    /  \
      8   12  16  25

    '''
    root = Node(15)
    root.left  = Node(10)
    root.right = Node(20)
    root.left.left  = Node(8)
    root.left.right = Node(12)
    root.right.left  = Node(16)
    root.right.right = Node(25)
    print(post_order(root))


if __name__ == '__main__':
    main()
0

这是我为后序遍历迭代器想出来的：

    class PostOrderIterator
    implements Iterator<T> {

        private Stack<Node<T>> stack;
        private Node<T> prev;

        PostOrderIterator(Node<T> root) {
            this.stack = new Stack<>();
            recurse(root);
            this.prev = this.stack.peek();
        }

        private void recurse(Node<T> node) {
            if(node == null) {
                return;
            }

            while(node != null) {
                stack.push(node);
                node = node.left;
            }
            recurse(stack.peek().right);
        }

        @Override
        public boolean hasNext() {
            return !stack.isEmpty();
        }

        @Override
        public T next() {
            if(stack.peek().right != this.prev) {
                recurse(stack.peek().right);
            }

            Node<T> next = stack.pop();
            this.prev = next;
            return next.value;
        }
    }

基本上，主要思路是你应该考虑初始化过程如何将第一个要打印的项放在堆栈顶部，而其余的堆栈则按递归所触及的节点跟随。剩下的事情就会变得容易许多。
此外，从设计角度来看，PostOrderIterator 是通过某些树类的工厂方法公开的内部类，作为 Iterator<T> 来使用。
0

两种不使用递归执行后序遍历的方法：

1. 使用一个已访问节点的哈希集和一个用于回溯的栈：

private void postOrderWithoutRecursion(TreeNode root) {
    if (root == null || root.left == null && root.right == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    Set<TreeNode> visited = new HashSet<>();
    while (!stack.empty() || root != null) {
        if (root != null) {
            stack.push(root);
            visited.add(root);
            root = root.left;
        } else {
            root = stack.peek();
            if (root.right == null || visited.contains(root.right)) {
                System.out.print(root.val+" ");
                stack.pop();
                root = null;
            } else {
                root = root.right;
            }

        }
    }
}

时间复杂度：O(n) 空间复杂度：O(2n)
2. 使用树的修改方法：
private void postOrderWithoutRecursionAlteringTree(TreeNode root) {
    if (root == null || root.left == null && root.right == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    while (!stack.empty() || root != null) {
        if (root != null) {
            stack.push(root);
            root = root.left;
        } else {
            root = stack.peek();
            if (root.right == null) {
                System.out.print(root.val+" ");
                stack.pop();
                root = null;
            } else {
                TreeNode temp = root.right;
                root.right = null;
                root = temp;
            }
        }
    }
}

时间复杂度：O(n) 空间复杂度：O(n)
TreeNode 类：
public class TreeNode {
    public int val;

    public TreeNode left;

    public TreeNode right;

    public TreeNode(int x) {
        val = x;
    }
}
0

Python中的简单直观解决方案。

        while stack:
            node = stack.pop()
            if node:
                if isinstance(node,TreeNode):
                    stack.append(node.val)
                    stack.append(node.right)
                    stack.append(node.left)
                else:
                    post.append(node)
        return post
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接