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<>(); List
list=newArrayList<>(); tree.dfs(root,rst,list); System.out.println(rst); } /** * *@paramdatas实现二叉树各节点值的数组 *@paramnodelist二叉树list */ privatevoidcreatBinaryTree(int[]datas,List nodelist){ //将数组变成node节点 for(intnodeindex=0;nodeindex stack=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){ Stack stack=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){ Stack stack=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; LinkedList queue=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,List
list){ 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种遍历方法(总结)就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持毛票票。