import java.util.HashMap; import java.util.LinkedList; import java.util.Queue; public class test15 { public static class Node{ public int value; public Node left; public Node right; public Node(int data){ this.value = data; } } //按层次遍历二叉树并打印每个节点的值,使用了队列来实现广度优先搜索(BFS) public static void level(Node head){ if(head == null){ return; } Queue<Node> queue = new LinkedList<>(); queue.add(head); while (!queue.isEmpty()){ Node cur = queue.poll(); System.out.println(cur.value); if(cur.left != null){ queue.add(cur.left); } if(cur.right != null){ queue.add(cur.right); } } } //求树的最大宽度 //方法1使用HashMap public static int maxWidthUseMap(Node head){ if(head == null){ return 0; } Queue<Node> queue= new LinkedList<>(); queue.add(head); //key在哪一层为value的值 HashMap<Node , Integer> levelMap= new HashMap<>(); levelMap.put(head ,1); int curLevel = 1;//当前统计哪一层的宽度 int curLevelNodes = 0;//当前层的宽度为多少 int max = 0; while (!queue.isEmpty()){ Node cur = queue.poll(); int curNodeLevel = levelMap.get(cur); if(cur.left != null){ levelMap.put(cur.left ,curNodeLevel +1); queue.add(cur.left); } if(cur.right != null){ levelMap.put(cur.left , curNodeLevel + 1); queue.add(cur.right); } if(curNodeLevel == curLevel){ curLevelNodes++; }else{ max = Math.max(max , curLevelNodes); curLevel++; curLevelNodes =1; } } max = Math.max(max , curLevelNodes); return max; } //方法2不用HashMap public static int maxWidthNoMap(Node head){ if(head == null){ return 0; } Queue<Node> queue = new LinkedList<>(); queue.add(head); Node curEnd = head;//当前层最后一个节点是谁 Node nextEnd = null;//如果有下一层,那么下一层最后节点是谁 int max =0; int curLevelNodes = 0;//当前层的节点数 while (!queue.isEmpty()){ Node cur = queue.poll(); if(cur.left != null){ queue.add(cur.left); nextEnd = cur.left; } if(cur.right != null){ queue.add(cur.right); nextEnd = cur.right; } curLevelNodes++; if(cur == curEnd){ max = Math.max(max , curLevelNodes); curLevelNodes = 0; curEnd = nextEnd; } } return max; } }
本站资源均来自互联网,仅供研究学习,禁止违法使用和商用,产生法律纠纷本站概不负责!如果侵犯了您的权益请与我们联系!
转载请注明出处: 免费源码网-免费的源码资源网站 » 二叉树的广度优先搜索BFS(两种实现方法)
发表评论 取消回复