关于二叉树的遍历:递归方式和非递归方式
首先来定义树的节点:
package test2018925.findTree;
public class Node {
public int value;
public Node left;
public Node right;
public Node(int data){
this.value=data;
}
}
然后来写我们遍历方法:
package test2018925.test;
import java.util.Stack;
import test2018925.findTree.Node;
public class Main {
// 递归先序遍历
public void preOrderRecur(Node head) {
if (head == null) {
return;
}
System.out.println(head.value);
preOrderRecur(head.left);
preOrderRecur(head.right);
}
// 递归中序遍历
public void inOrderRecur(Node head) {
if (head == null) {
return;
}
preOrderRecur(head.left);
System.out.println(head.value);
preOrderRecur(head.right);
}
// 递归后序遍历
public void postOrderRecur(Node head) {
if (head == null) {
return;
}
preOrderRecur(head.left);
preOrderRecur(head.right);
System.out.println(head.value);
}
// 树的非递归前序遍历
public void preOrderUnCur(Node head) {
if (head != null) {
Stack<Node> stack = new Stack<Node>();
stack.push(head);
while (!stack.isEmpty()) {
head = stack.pop();// 指针每次指向栈顶,每次取出栈顶,
System.out.println(head.value);
// 下边先放右在放左,然后回到while循环,取出栈顶的左(不过会在放入该左子树的右子树和左子树)和栈顶的右子树
if (head.right != null) {
stack.push(head.right);
}
if (head.left != null) {
stack.push(head.left);
}
}
}
}
// 树的非递归中序遍历,先把左边的左边的左边....全部放入压入栈,直到没得左子树,就取出来,取出该节点后,再取出该节点的右子树
public void inOrderUnCur(Node head) {
if (head != null) {
Stack<Node> stack2 = new Stack<Node>();
while (!stack2.isEmpty() || head != null) {
if (head != null) {
stack2.push(head);// 最开始指针指向头
head = head.left;// 然后指针指向左
} else {// 当左子树为null的时候开始进入下边,先取出该节点,然后指针指向右边
head = stack2.pop();
System.out.println(head.value);
head = head.right;
}
}
}
}
// 树的非递归后序遍历
public void postOrderUnCur(Node head) {
if (head != null) {
Stack<Node> s1 = new Stack<Node>();
Stack<Node> s2 = new Stack<Node>();
s1.push(head);
while (!s1.isEmpty()) {
head = s1.pop();// 取出栈顶元素,放入下边一行的栈2中
s2.push(head);// 先把栈1中的头放入到栈2中,所以头在栈2的栈底
if (head.left != null) {
s1.push(head.left);// 在把左边放入栈1,后把右边放入栈,同时,因为我们指针始终指向我们栈顶的,所以,我们我们后边会先把右边放入栈2,在把左边放入栈2.所以后边栈2取出顺序是左右中
}
if (head.right != null) {
s1.push(head.right);
}
}
while (!s2.isEmpty()) {
System.out.println(s2.pop().value + " ");
}
}
}
}