Java|Java 二叉树递归与非递归所有遍历
二叉树的递归与非递归遍历
/**
* @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 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 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 s1 = new Stack<>();
Stack 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 + " ");
}
}
}
} 【Java|Java 二叉树递归与非递归所有遍历】PS:非递归遍历搞得头脑发晕....
参考文献 :左神的书
推荐阅读
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- 【生信技能树】R语言练习题|【生信技能树】R语言练习题 - 中级
- 事件代理
- Java|Java OpenCV图像处理之SIFT角点检测详解
- java中如何实现重建二叉树
- 数组常用方法一
- 【Hadoop踩雷】Mac下安装Hadoop3以及Java版本问题
- 种树郭橐驼传（文言句式+古今异义+词类活用+通假字）
- Java|Java基础——数组
- RxJava|RxJava 在Android项目中的使用（一）