Friday, September 13, 2013

postorder traversal (iterative)

 void iterative_postOrder(Node node) {
        Stack<Node> stack = new Stack<Node>();
        Node delNode = null;
        int maxSize=0,size=0;
        while (true) {
            while (node != null) {
                stack.push(node);
                size++;
                node = node.leftChild;
                if(node==null){
                    if(size > maxSize)
                        size=maxSize;
                }
            }
            if (stack.size() == 0) {
                break;
            }
            if (stack.peek().rightChild == null || delNode == stack.peek().rightChild) {
                delNode = stack.pop();
                size--;
                System.out.print(delNode.data + " , ");
            } else {
                node = stack.peek().rightChild;
            }
//            if (stack.peek().rightChild != null && delNode != stack.peek().rightChild) {
//                node = stack.peek().rightChild;
//            } else {
//                delNode = stack.pop();
//                System.out.print(delNode.data + " , ");
//                if (!stack.isEmpty() && delNode != stack.peek().rightChild) {
//                    node = stack.peek().rightChild;
//                }
//            }
        }
        System.out.print("\n postorder: max stackSize ="+maxSize);
    }

No comments:

Post a Comment