提示:由于本人没有精力做那么多流程图，建议你看的时候自己在纸上画一画，模拟一下顺序，不然很难理解。
1.先序遍历
思路：
（1）用一个栈保存二叉树的节点，从根节点开始。
（2）先压入根节点，打印，然后找右孩子，存在就压入栈，不存在就压入左孩子。
（3）栈非空，且既没有右孩子也没有左孩子的时候，弹出栈顶元素并打印，继续第2步。
由于操作的顺序是：先让父结点出栈并打印，然后压右，再压左。出栈顺序就正好相反，先弹左，后弹右，实现了先序遍历。
public static void preOrderUnRecur(Node head) {
System.out.print("先序遍历: ");
if (head != null) {
Stack<Node> stack = new Stack<>();
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);
}
}
System.out.println();
}
2.中序遍历：
思路：
（1）当前节点先把自己的左边界（所有的左孩子节点）都压到栈里。
（2）由于一直重复head = head.left，肯定会有一个时刻，head.left为空，当节点为空的时候，开始弹栈。
具体操作是：从栈中拿出栈顶元素并打印，然后当前节点向右孩子移动。
（3）重复前两步，当栈为空且节点也为空时，循环结束。
public static void inOrderUnRecur(Node head) {
System.out.print("中序遍历: ");
if (head != null) {
Stack<Node> stack = new Stack<>();
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;
}
}
}
System.out.println();
}
3.后序遍历：
- 方法1 （使用两个栈）
后序遍历的顺序是 左→右→中，要想压到栈里再按这个顺序弹出打印的话，压栈的时候顺序就应该是 中→右→左。那么，怎么实现呢？
我们前面写第一个先序遍历的时候，顺序是中左右。稍微修改一下先序遍历的代码，让那个栈弹出并打印中节点之后，先压入右孩子，再压入左孩子。这样出栈顺序就变成了中右左。
继续修改，弹栈时候栈顶元素不打印，而是压入另一个辅助栈，原来那个栈的出栈打印顺序（中右左）就变成了辅助栈的压栈顺序。那么在辅助栈弹栈打印的时候，不就是左右中了吗？
这个解释起来比较晦涩，自己拿张纸画一下流程，模拟出栈顺序，你就会很明白。
public static void posOrderUnRecur1(Node head) {
System.out.print("后序遍历: ");
if (head != null) {
Stack<Node> s1 = new Stack<>();
Stack<Node> s2 = new Stack<>();
s1.push(head);
while (!s1.isEmpty()) {
head = s1.pop();
s2.push(head);
if (head.left != null)
s1.push(head.left);
if (head.right != null)
s1.push(head.right);
}
while (!s2.isEmpty()) {
System.out.print(s2.pop().value + " ");
}
}
System.out.println();
}
- 方法2
纯粹炫技的做法，只用了一个栈，能看得懂就看，看不懂也没有关系。
public static void posOrderUnRecur2(Node h) {
System.out.print("后序遍历: ");
if (h != null) {
Stack<Node> stack = new Stack<>();
stack.push(h);
Node c;
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();
}
完整的代码（包含了递归方式）：
import java.util.Stack;
public class PreInPosTraversal {
public static class Node {
public int value;
public Node left;
public Node right;
public 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 posOrderRecur(Node head) {
if (head == null) return;
posOrderRecur(head.left);
posOrderRecur(head.right);
System.out.print(head.value + " ");
}
public static void preOrderUnRecur(Node head) {
System.out.print("先序遍历: ");
if (head != null) {
Stack<Node> stack = new Stack<>();
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);
}
}
System.out.println();
}
public static void inOrderUnRecur(Node head) {
System.out.print("中序遍历: ");
if (head != null) {
Stack<Node> stack = new Stack<>();
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;
}
}
}
System.out.println();
}
public static void posOrderUnRecur1(Node head) {
System.out.print("后序遍历: ");
if (head != null) {
Stack<Node> s1 = new Stack<>();
Stack<Node> s2 = new Stack<>();
s1.push(head);
while (!s1.isEmpty()) {
head = s1.pop();
s2.push(head);
if (head.left != null)
s1.push(head.left);
if (head.right != null)
s1.push(head.right);
}
while (!s2.isEmpty()) {
System.out.print(s2.pop().value + " ");
}
}
System.out.println();
}
public static void posOrderUnRecur2(Node h) {
System.out.print("后序遍历: ");
if (h != null) {
Stack<Node> stack = new Stack<>();
stack.push(h);
Node c;
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();
}
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);
// recursive
System.out.println("==============递归==============");
System.out.print("先序遍历: ");
preOrderRecur(head);
System.out.println();
System.out.print("中序遍历: ");
inOrderRecur(head);
System.out.println();
System.out.print("后序遍历: ");
posOrderRecur(head);
System.out.println();
// unRecursive
System.out.println("============非递归=============");
preOrderUnRecur(head);
inOrderUnRecur(head);
posOrderUnRecur1(head);
posOrderUnRecur2(head);
}
}
网友评论