二叉树的递归与非递归遍历
/**
* @ClassName: tree
* @Description: TODO
* @Author: Joker
* @Date: 2020/3/12
*/
class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int data) {
this.val = data;
}
}
public class TreeBinary {
//暴力构建一颗二叉树
public static void main(String[] args) {
TreeNode n1 = new TreeNode(5);
TreeNode n2 = new TreeNode(6);
TreeNode n3 = new TreeNode(7);
TreeNode n4 = new TreeNode(8);
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = null;
n3.left = null;
n3.right = null;
n4.left = null;
n4.right = null;
System.out.println("先序递归");
preOrderRecur(n1);
System.out.println("中序递归");
inOrderRecur(n1);
System.out.println("后序递归");
posOrderRecur(n1);
preOrderUnRecur(n1);
inOrderUnRecur(n1);
posOrderUnRecur(n1);
}
//先序递归遍历
public static void preOrderRecur(TreeNode root) {
if (root == null) {
return;
}
System.out.println(root.val + " ");
preOrderRecur(root.left);
preOrderRecur(root.right);
}
//中序递归遍历
public static void inOrderRecur(TreeNode root) {
if (root == null) {
return;
}
preOrderRecur(root.left);
System.out.println(root.val + " ");
preOrderRecur(root.right);
}
//后序递归遍历
public static void posOrderRecur(TreeNode root) {
if (root == null) {
return;
}
preOrderRecur(root.left);
preOrderRecur(root.right);
System.out.println(root.val + " ");
}
/***
* 先序遍历非递归
* 1、申请一个新的栈 stack 。将头节点 root 压入 stack 中。
*
* 2、从 stack 中弹出栈顶节点，记为 cur ,然后打印 cur 节点的值，
* 再将节点 cur 的右孩子（不为空的话）压入 stack 中，
* 最后将 cur 的左孩子（不为空的话）压入 stack 中。
*
* 3、不断重复步骤 2，直到 stack 为空，全部过程结束。
* @param root
*/
public static void preOrderUnRecur(TreeNode root) {
System.out.println("非递归先序递归");
if (root != null) {
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
root = stack.pop();
System.out.println(root.val + " ");
if (root.right != null) {
stack.push(root.right);
}
if (root.left != null) {
stack.push(root.left);
}
}
}
}
/***
* 中序非递归遍历
* 1、申请一个新的栈 stack 。初始时，令变量 cur = head。
*
* 2、先把 cur 节点压入栈中，对以 cur 节点为头的整棵树来说，
* 依次把左边界压入栈中，即不停的令 cur = cur.left，然后重复步骤 2
*
* 3、不断重复步骤 2 ，直到发现 cur 为空。此时从 stack 中弹出一个节点，
* 记为 node 。打印 node 的值，并且让 cur = cur.right, 然后重复步骤 2
* @param root
*/
public static void inOrderUnRecur(TreeNode root) {
System.out.println("非递归中序遍历");
if (root != null) {
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || root != null) {
if (root != null) {
stack.push(root);
root = root.left;
} else {
root = stack.pop();
System.out.println(root.val + " ");
root = root.right;
}
}
}
}
/***
* 非递归后续遍历
* 1、申请一个栈，记为 s1 ，然后将头节点 root 压入 s1 中。
*
* 2、从 s1 中弹出的节点记为 cur ,然后依次将 cur 的左孩子和右孩子压入 s1 中。
*
* 3、在整个过程中，每一个从 s1 弹出的节点都放入 s2 中。
*
* 4、 不断重复步骤 2 和步骤 3 ，直到 s1 为空，过程停止
*
* 5、从 s2 中依次弹出节点并打印。
* @param root
*/
public static void posOrderUnRecur(TreeNode root) {
System.out.println("非递归后续遍历");
if (root != null) {
Stack<TreeNode> s1 = new Stack<>();
Stack<TreeNode> s2 = new Stack<>();
s1.push(root);
while (!s1.isEmpty()) {
root = s1.pop();
s2.push(root);
if (root.left != null) {
s1.push(root.left);
}
if (root.right != null) {
s1.push(root.right);
}
}
while (!s2.isEmpty()) {
System.out.println(s2.pop().val + " ");
}
}
}
}
PS:非递归遍历搞得头脑发晕....
参考文献 :左神的书
