Java实现广度遍历二叉树

标题：Java实现广度遍历二叉树

public class TestMyTreeBroad12 { /**方法一：不保存二叉树节点【使用递归】 * 我写的另一种递归 * 不过队列q要先赋值 【使用下面的函数hh】 * @param q */ public void boradorder(Queue<IntNode> q) { if(q.isEmpty()) { return ; }else { IntNode p = q.peek(); System.out.print(p.val + " "); q.poll(); if(p.left != null) { q.offer(p.left); } if(p.right != null) { q.offer(p.right); } this.boradorder(q); } } //和上面的递归一起的，为队列q赋值 public void hh(IntNode p1) { Queue<IntNode> q = new LinkedList<IntNode>(); q.offer(p1); this.boradorder(q); } /** * 方法二：保存二叉树节点【使用递归】 * 上面递归的升级版，【使用List<List<IntNode>> blist保存】 * 测试遍历二叉树的广度遍历 * * 执行结果： 通过 显示详情 执行用时：19 ms, 在所有 Java 提交中击败了15.14% 的用户 内存消耗：38.9 MB, 在所有 Java 提交中击败了75.16% 的用户 * @param p */ public void boradorder03( Queue<IntNode> q, int count, List<List<IntNode>> blist, List<IntNode> slist) { if(q.isEmpty()) { blist.add(slist); return ; }else { if(count == 0) { //== 0 说明，已经把本次要放入List中的IntNode放完了 blist.add(slist); //，添加到blist中，新创建一个slist slist = new ArrayList<IntNode>(); count = q.size(); //获取下一次需要放入slist中的count【个数】 } IntNode node = q.poll(); //放入slist中，count--，输出， count--; System.out.print(node.val + " "); slist.add(node); if(node.left != null) { //添加到q中 q.offer(node.left); } if(node.right != null) { q.offer(node.right); } this.boradorder03(q, count, blist, slist); } } //调用上面的递归，同时给予初始化 public void hh03(IntNode p) { if(p == null) { return ; } Queue<IntNode> q = new LinkedList<>(); int count = 1; List<List<IntNode>> blist = new ArrayList<>(); List<IntNode> slist = new ArrayList<>(); q.offer(p); this.boradorder03(q, count, blist, slist); System.out.println(); System.out.println("输出list中的值"); this.printListList(blist); } /**方法三： 使用非递归实现广度遍历 * 执行用时：17 ms, 在所有 Java 提交中击败了15.14% 的用户 内存消耗：38.8 MB, 在所有 Java 提交中击败了92.09% 的用户 * @param p */ public List<List<IntNode>> broadorder02(IntNode p) { Queue<IntNode> q = new LinkedList<>(); List<List<IntNode>> blist = new ArrayList<>(); List<IntNode> mlist = new ArrayList<IntNode>(); if(p == null) { return null; } q.offer(p); mlist.add(p); blist.add(mlist); while(!q.isEmpty()) { int size = q.size(); List<IntNode> mlist02 = new ArrayList<IntNode>(); for(int i = 0; i < size; i++) { //size，队列中元素的个数，【待删除元素的个数】 IntNode node = q.poll(); System.out.print(node.val + " "); if(node.left != null) { //添加到队列中 q.offer(node.left); mlist02.add(node.left); } if(node.right != null) { q.offer(node.right); mlist02.add(node.right); } } if(mlist02.size() != 0) { //最后一个小的list【mlist02】里面没有元素，此时队列q为null blist.add(mlist02); } } return blist; } /** * 输出List<List<IntNode>> list中的list * @param list */ public void printListList(List<List<IntNode>> list) { System.out.println("\n开始输出："); for(List<IntNode> lis: list) { for(IntNode node: lis) { System.out.print(node.val + " "); } System.out.println(); } System.out.println(); } @Test public void test02() { IntNode p1 = new IntNode('a'); IntNode p2 = new IntNode('b'); IntNode p3 = new IntNode('c'); IntNode p4 = new IntNode('d'); IntNode p5 = new IntNode('e'); IntNode p6 = new IntNode('f'); IntNode p7 = new IntNode('g'); IntNode p8 = new IntNode('h'); IntNode p9 = new IntNode('i'); IntNode p10 = new IntNode('j'); IntNode p11 = new IntNode('k'); p1.left = p2; p1.right = p3; p2.left = p4; p2.right = p5; p4.right = p6; p5.left = p7; p5.right = p8; p3.left = p9; p3.right = p10; p10.right =p11; System.out.println("使用递归的广度遍历"); // this.boradorder(p1, new LinkedList<IntNode>()); this.hh(p1); System.out.println(); System.out.println("使用递归的广度遍历，【保存到了ListList中】"); this.hh03(p1); System.out.println("不使用递归的广度遍历"); List<List<IntNode>> list = this.broadorder02(p1); this.printListList(list); } }