后续遍历跟先序遍历比较像,这里是定义了两个栈,把打印的先放在打印栈stack2里
package com.algorithm.practice.tree.traversal;
import java.util.Stack;
public class PosOrderPrint {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static void posOrderPrint(Node head){
System.out.print("postnatal-order: ");
if (head!=null){
Stack<Node> stack1=new Stack<>();
Stack<Node> stack2=new Stack<>();
stack1.push(head);
while (!stack1.isEmpty()){
head = stack1.pop();
stack2.push(head);
if (head.left!=null){
stack1.push(head.left);
}
if (head.right!=null){
stack1.push(head.right);
}
}
while (!stack2.isEmpty())
{
System.out.print(stack2.pop().value+" ");
}
}
}
public static void main(String[] args){
Node head = new Node(5);
head.left = new Node(3);
head.right = new Node(8);
head.left.left = new Node(2);
head.left.right = new Node(4);
head.left.left.left = new Node(1);
head.right.left = new Node(7);
head.right.left.left = new Node(6);
head.right.right = new Node(10);
head.right.right.left = new Node(9);
head.right.right.right = new Node(11);
posOrderPrint(head);
System.out.println();
}
}
public static void posOrderUnRecur2(Node h) {
System.out.print("pos-order: ");
if (h != null) {
Stack<Node> stack = new Stack<Node>();
stack.push(h);
Node c = null;
while (!stack.isEmpty()) {
c = stack.peek();
if (c.left != null && h != c.left && h != c.right) {
stack.push(c.left);
} else if (c.right != null && h != c.right) {
stack.push(c.right);
} else {
System.out.print(stack.pop().value + " ");
h = c;
}
}
}
System.out.println();
}