java实现二叉树的创建及5种遍历方法(总结)
作者:jingxian 时间:2022-03-14 09:00:28
用java实现的数组创建二叉树以及递归先序遍历,递归中序遍历,递归后序遍历,非递归前序遍历,非递归中序遍历,非递归后序遍历,深度优先遍历,广度优先遍历8种遍历方式:
package myTest;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
public class myClass {
public static void main(String[] args) {
// TODO Auto-generated method stub
myClass tree = new myClass();
int[] datas = new int[]{1,2,3,4,5,6,7,8,9};
List<Node> nodelist = new LinkedList<>();
tree.creatBinaryTree(datas, nodelist);
Node root = nodelist.get(0);
System.out.println("递归先序遍历:");
tree.preOrderTraversal(root);
System.out.println();
System.out.println("非递归先序遍历:");
tree.preOrderTraversalbyLoop(root);
System.out.println();
System.out.println("递归中序遍历:");
tree.inOrderTraversal(root);
System.out.println();
System.out.println("非递归中序遍历:");
tree.inOrderTraversalbyLoop(root);
System.out.println();
System.out.println("递归后序遍历:");
tree.postOrderTraversal(root);
System.out.println();
System.out.println("非递归后序遍历:");
tree.postOrderTraversalbyLoop(root);
System.out.println();
System.out.println("广度优先遍历:");
tree.bfs(root);
System.out.println();
System.out.println("深度优先遍历:");
List<List<Integer>> rst = new ArrayList<>();
List<Integer> list = new ArrayList<>();
tree.dfs(root,rst,list);
System.out.println(rst);
}
/**
*
* @param datas 实现二叉树各节点值的数组
* @param nodelist 二叉树list
*/
private void creatBinaryTree(int[] datas,List<Node> nodelist){
//将数组变成node节点
for(int nodeindex=0;nodeindex<datas.length;nodeindex++){
Node node = new Node(datas[nodeindex]);
nodelist.add(node);
}
//给所有父节点设定子节点
for(int index=0;index<nodelist.size()/2-1;index++){
//编号为n的节点他的左子节点编号为2*n 右子节点编号为2*n+1 但是因为list从0开始编号,所以还要+1
//这里父节点有1(2,3),2(4,5),3(6,7),4(8,9) 但是最后一个父节点有可能没有右子节点 需要单独处理
nodelist.get(index).setLeft(nodelist.get(index*2+1));
nodelist.get(index).setRight(nodelist.get(index*2+2));
}
//单独处理最后一个父节点 因为它有可能没有右子节点
int index = nodelist.size()/2-1;
nodelist.get(index).setLeft(nodelist.get(index*2+1)); //先设置左子节点
if(nodelist.size() % 2 == 1){ //如果有奇数个节点,最后一个父节点才有右子节点
nodelist.get(index).setRight(nodelist.get(index*2+2));
}
}
/**
* 遍历当前节点的值
* @param nodelist
* @param node
*/
public void checkCurrentNode(Node node){
System.out.print(node.getVar()+" ");
}
/**
* 先序遍历二叉树
* @param root 二叉树根节点
*/
public void preOrderTraversal(Node node){
if (node == null) //很重要,必须加上 当遇到叶子节点用来停止向下遍历
return;
checkCurrentNode(node);
preOrderTraversal(node.getLeft());
preOrderTraversal(node.getRight());
}
/**
* 中序遍历二叉树
* @param root 根节点
*/
public void inOrderTraversal(Node node){
if (node == null) //很重要,必须加上
return;
inOrderTraversal(node.getLeft());
checkCurrentNode(node);
inOrderTraversal(node.getRight());
}
/**
* 后序遍历二叉树
* @param root 根节点
*/
public void postOrderTraversal(Node node){
if (node == null) //很重要,必须加上
return;
postOrderTraversal(node.getLeft());
postOrderTraversal(node.getRight());
checkCurrentNode(node);
}
/**
* 非递归前序遍历
* @param node
*/
public void preOrderTraversalbyLoop(Node node){
Stack<Node> stack = new Stack();
Node p = node;
while(p!=null || !stack.isEmpty()){
while(p!=null){ //当p不为空时,就读取p的值,并不断更新p为其左子节点,即不断读取左子节点
checkCurrentNode(p);
stack.push(p); //将p入栈
p = p.getLeft();
}
if(!stack.isEmpty()){
p = stack.pop();
p = p.getRight();
}
}
}
/**
* 非递归中序遍历
* @param node
*/
public void inOrderTraversalbyLoop(Node node){
Stack<Node> stack = new Stack();
Node p = node;
while(p!=null || !stack.isEmpty()){
while(p!=null){
stack.push(p);
p = p.getLeft();
}
if(!stack.isEmpty()){
p = stack.pop();
checkCurrentNode(p);
p = p.getRight();
}
}
}
/**
* 非递归后序遍历
* @param node
*/
public void postOrderTraversalbyLoop(Node node){
Stack<Node> stack = new Stack<>();
Node p = node,prev = node;
while(p!=null || !stack.isEmpty()){
while(p!=null){
stack.push(p);
p = p.getLeft();
}
if(!stack.isEmpty()){
Node temp = stack.peek().getRight();
if(temp == null||temp == prev){
p = stack.pop();
checkCurrentNode(p);
prev = p;
p = null;
}else{
p = temp;
}
}
}
}
/**
* 广度优先遍历(从上到下遍历二叉树)
* @param root
*/
public void bfs(Node root){
if(root == null) return;
LinkedList<Node> queue = new LinkedList<Node>();
queue.offer(root); //首先将根节点存入队列
//当队列里有值时,每次取出队首的node打印,打印之后判断node是否有子节点,若有,则将子节点加入队列
while(queue.size() > 0){
Node node = queue.peek();
queue.poll(); //取出队首元素并打印
System.out.print(node.var+" ");
if(node.left != null){ //如果有左子节点,则将其存入队列
queue.offer(node.left);
}
if(node.right != null){ //如果有右子节点,则将其存入队列
queue.offer(node.right);
}
}
}
/**
* 深度优先遍历
* @param node
* @param rst
* @param list
*/
public void dfs(Node node,List<List<Integer>> rst,List<Integer> list){
if(node == null) return;
if(node.left == null && node.right == null){
list.add(node.var);
/* 这里将list存入rst中时,不能直接将list存入,而是通过新建一个list来实现,
* 因为如果直接用list的话,后面remove的时候也会将其最后一个存的节点删掉*/
rst.add(new ArrayList<>(list));
list.remove(list.size()-1);
}
list.add(node.var);
dfs(node.left,rst,list);
dfs(node.right,rst,list);
list.remove(list.size()-1);
}
/**
* 节点类
* var 节点值
* left 节点左子节点
* right 右子节点
*/
class Node{
int var;
Node left;
Node right;
public Node(int var){
this.var = var;
this.left = null;
this.right = null;
}
public void setLeft(Node left) {
this.left = left;
}
public void setRight(Node right) {
this.right = right;
}
public int getVar() {
return var;
}
public void setVar(int var) {
this.var = var;
}
public Node getLeft() {
return left;
}
public Node getRight() {
return right;
}
}
}
运行结果:
递归先序遍历:
1 2 4 8 9 5 3 6 7
非递归先序遍历:
1 2 4 8 9 5 3 6 7
递归中序遍历:
8 4 9 2 5 1 6 3 7
非递归中序遍历:
8 4 9 2 5 1 6 3 7
递归后序遍历:
8 9 4 5 2 6 7 3 1
非递归后序遍历:
8 9 4 5 2 6 7 3 1
广度优先遍历:
1 2 3 4 5 6 7 8 9
深度优先遍历:
[[1, 2, 4, 8], [1, 2, 4, 9], [1, 2, 5], [1, 3, 6], [1, 3, 7]]
标签:二叉树,创建,遍历
0
投稿
猜你喜欢
Java实现合并两个有序序列算法示例
2021-09-06 23:23:53
Java设计模式之命令模式(Command模式)介绍
2021-12-02 01:01:02
C#二进制读写BinaryReader、BinaryWriter、BinaryFormatter
2022-03-07 23:01:28
Java单例模式下的MongoDB数据库操作工具类
2023-11-20 12:55:01
一文彻底搞懂Java和JDK的版本命名问题
2023-11-24 01:39:25
springboot配置mysql数据库spring.datasource.url报错的解决
2023-10-04 12:49:26
JAVA抽象类,接口,内部类详解
2023-11-09 16:37:25
Flink支持哪些数据类型?
2023-01-15 06:55:43
Java定时调用.ktr文件的示例代码(解决方案)
2021-12-29 13:21:49
Java数据结构之常见排序算法(下)
2022-05-03 12:49:51
Winform跨线程操作的简单方法
2023-04-28 09:38:46
Mybatis注解实现多数据源读写分离详解
2021-12-15 21:44:16
Idea如何导入一个SpringBoot项目的方法(图文教程)
2022-08-10 22:40:49
Java 1.8使用数组实现循环队列
2022-02-11 04:00:10
Java实现简单台球游戏
2022-06-28 23:55:59
MyBatis数据脱敏的实现方案介绍
2021-10-06 19:22:34
引入SpringCloud-gateway报错的解决方案
2022-04-02 21:47:17
实例讲解JAVA设计模式之备忘录模式
2023-08-29 16:31:19
Java正则验证正整数的方法分析【测试可用】
2022-08-02 21:50:05
一文解决springboot打包成jar文件无法正常运行的问题
2021-11-03 14:54:28