用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 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> rst = new ArrayList<>();
List list = new ArrayList<>();
tree.dfs(root,rst,list);
System.out.println(rst);
}
private void creatBinaryTree(int[] datas,List nodelist){
//将数组变成node节点
for(int nodeindex=0;nodeindex 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();
}
}
}
public void inOrderTraversalbyLoop(Node node){
Stack 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();
}
}
}
public void postOrderTraversalbyLoop(Node node){
Stack 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;
}
}
}
}
public void bfs(Node root){
if(root == null) return;
linkedList queue = new linkedList();
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);
}
}
}
public void dfs(Node node,List> rst,List list){
if(node == null) return;
if(node.left == null && node.right == null){
list.add(node.var);
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);
}
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]]
以上这篇java实现二叉树的创建及5种遍历方法(总结)就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持考高分网。
