import java.util.Stack;
public class prepos {
public static void main(String[] args) {}
public static class Node {
public int value;
public Node left;
public Node right;
Node(int data) { this.value = data; }
}
//方法一:递归
//先序遍历
public static void preOrderRecur(Node head) {
if (head == null) {
return;
}
System.out.print(head.value);
preOrderRecur(head.left);
preOrderRecur(head.right);
}
//中序遍历
public static void inOrderRecur(Node head) {
if (head == null) {
return;
}
inOrderRecur(head.left);
System.out.print(head.value);
inOrderRecur(head.right);
}
//后序遍历
public static void postOrderRecur(Node head) {
if (head == null) {
return;
}
postOrderRecur(head.left);
postOrderRecur(head.right);
System.out.println(head.value);
}
//方法二:使用栈
//先序遍历
public static void pretOrderunRecur(Node head) {
if (head != null) {
Stack<Node> stack = new Stack<Node>();
stack.add(head);
while (!stack.isEmpty()) {
head = stack.pop();
System.out.print(head.value);
if (head.right != null) {
stack.push(head.right);
}
if (head.left != null) {
stack.push(head.left);
}
}
}
}
//中序遍历
public static void inOrderunRecur(Node head) {
if (head != null) {
Stack<Node> stack = new Stack<Node>();
while (!stack.isEmpty() || head != null) {
if (head != null) {
stack.push(head);
head = head.left;
} else {
head = stack.pop();
System.out.print(head.value);
head = head.right;
}
}
}
}
//后序遍历
public static void postOrderUnRecur(Node head) {
if (head != null) {
Stack<Node> stack1 = new Stack<Node>();
Stack<Node> stack2 = new Stack<Node>();
stack1.push(head);
while (!stack1.isEmpty()) {
head = s1.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 postOrderRecur2(Node h) {
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;
}
}
}
}
}