java实现二叉树的创建及5种遍历方法(总结)

用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]]

以上这篇java实现二叉树的创建及5种遍历方法(总结)就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持。