//postorder recursion
public static void PostOrder(Node r)
{
if( r != null)
{
PostOrder(r.left);
PostOrder(r.right);
System.out.println("[" + r.data + "]");
}
}
//postorder with iteration
//postorder with loop
public static void PostorderIteration(Node r)
{
Stack<Node> st = new Stack<Node>();
Node tmp = r;
Node cur = r;
while(!st.empty() || cur != null)
{
if( cur != null)
{
st.push(cur);
cur = cur.left;
}
else
{
Node pop = st.pop();
if(pop.left == null && pop.right == null)
System.out.println("p="+pop.data);
else if(pop.right != null && pop.visited == false)
{
cur = pop.right;
pop.visited = true;
st.push(pop);
}
else if(pop.right != null && pop.visited == true)
System.out.println("p="+pop.data);
}
}
}
//Postorder with two stacks
public static void PostorderTwoStacks(Node curr)
{
Stack<Node> st1 = new Stack<Node>();
Stack<Node> st2 = new Stack<Node>();
if(curr != null)
{
st1.push(curr);
while(!st1.empty())
{
Node node = st1.pop();
st2.push(node);
if(node.left != null)
st1.push(node.left);
if(node.right != null)
st1.push(node.right);
}
while(!st2.empty())
{
Node node = st2.pop();
System.out.println("Two Stacks Iteration["+node.data+"]");
}
}
}
class Contact implements Comparable<Contact>
{
String name;
String addr;
int age;
public Contact(String name, String addr, int age)
{
this.name = name;
this.addr = addr;
this.age = age;
}
//Minimum heap
public int compareTo(Contact c)
{
return this.age - c.age;
//Maximum heap
//return -(this.age - c.age);
}
public String toString()
{
return "["+name+"]["+addr+"]["+age+"]";
}
}