java实现二叉树的创建及5种遍历方法(总结)
用java实现的数组创建二叉树以及递归先序遍历，递归中序遍历，递归后序遍历，非递归前序遍历，非递归中序遍历，非递归后序遍历，深度优先遍历，广度优先遍历8种遍历方式：
packagemyTest;
importjava.util.ArrayList;
importjava.util.LinkedList;
importjava.util.List;
importjava.util.Stack;
publicclassmyClass{
publicstaticvoidmain(String[]args){
//TODOAuto-generatedmethodstub
myClasstree=newmyClass();
int[]datas=newint[]{1,2,3,4,5,6,7,8,9};
Listnodelist=newLinkedList<>();
tree.creatBinaryTree(datas,nodelist);
Noderoot=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>rst=newArrayList<>();
Listlist=newArrayList<>();
tree.dfs(root,rst,list);
System.out.println(rst);
}
/**
*
*@paramdatas实现二叉树各节点值的数组
*@paramnodelist二叉树list
*/
privatevoidcreatBinaryTree(int[]datas,Listnodelist){
//将数组变成node节点
for(intnodeindex=0;nodeindexstack=newStack();
Nodep=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();
}
}
}
/**
*非递归中序遍历
*@paramnode
*/
publicvoidinOrderTraversalbyLoop(Nodenode){
Stackstack=newStack();
Nodep=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();
}
}
}
/**
*非递归后序遍历
*@paramnode
*/
publicvoidpostOrderTraversalbyLoop(Nodenode){
Stackstack=newStack<>();
Nodep=node,prev=node;
while(p!=null||!stack.isEmpty()){
while(p!=null){
stack.push(p);
p=p.getLeft();
}
if(!stack.isEmpty()){
Nodetemp=stack.peek().getRight();
if(temp==null||temp==prev){
p=stack.pop();
checkCurrentNode(p);
prev=p;
p=null;
}else{
p=temp;
}
}
}
}
/**
*广度优先遍历（从上到下遍历二叉树）
*@paramroot
*/
publicvoidbfs(Noderoot){
if(root==null)return;
LinkedListqueue=newLinkedList();
queue.offer(root);//首先将根节点存入队列
//当队列里有值时，每次取出队首的node打印，打印之后判断node是否有子节点，若有，则将子节点加入队列
while(queue.size()>0){
Nodenode=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);
}
}
}
/**
*深度优先遍历
*@paramnode
*@paramrst
*@paramlist
*/
publicvoiddfs(Nodenode,List>rst,Listlist){
if(node==null)return;
if(node.left==null&&node.right==null){
list.add(node.var);
/*这里将list存入rst中时，不能直接将list存入，而是通过新建一个list来实现，
*因为如果直接用list的话，后面remove的时候也会将其最后一个存的节点删掉*/
rst.add(newArrayList<>(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右子节点
*/
classNode{
intvar;
Nodeleft;
Noderight;
publicNode(intvar){
this.var=var;
this.left=null;
this.right=null;
}
publicvoidsetLeft(Nodeleft){
this.left=left;
}
publicvoidsetRight(Noderight){
this.right=right;
}
publicintgetVar(){
returnvar;
}
publicvoidsetVar(intvar){
this.var=var;
}
publicNodegetLeft(){
returnleft;
}
publicNodegetRight(){
returnright;
}
}
}
运行结果：
递归先序遍历：
124895367
非递归先序遍历：
124895367
递归中序遍历：
849251637
非递归中序遍历：
849251637
递归后序遍历：
894526731
非递归后序遍历：
894526731
广度优先遍历：
123456789
深度优先遍历：
[[1,2,4,8],[1,2,4,9],[1,2,5],[1,3,6],[1,3,7]]
以上这篇java实现二叉树的创建及5种遍历方法(总结)就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持毛票票。