首页 > 代码库 > 数据结构——二叉树遍历之“层遍历”
数据结构——二叉树遍历之“层遍历”
系列文章:数据结构与算法系列——从菜鸟到入门
层次遍历
二叉树的层次遍历是指,从二叉树的第一层(根结点)开始,从上至下逐层遍历,在同一层中从左至右依次遍历。
- 设置一个队列,将二叉树的根结点放入队列中。
- 将队列中的头结点出队,赋值给临时变量 temp,同时输出打印 temp.val。
- 判断 temp 是否有左结点和右结点,若有,分别将左、右结点放入队列中。
- 重复步骤 2~3,直至队列为空,表示二叉树的层次遍历结束。
private static void cengci(TreeNode root) { Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); while (!queue.isEmpty()) { root = queue.poll(); System.out.print(root.val+"-"); if (root.left != null) { queue.add(root.left); } if (root.right != null) { queue.add(root.right); } }}
按层打印
按层打印要求,在不同的层打印后加上换行。问题的关键就是如何知道该换行了。只需要两个 node 类型的变量 last 和 nlast 就可以解决。同样进行从左到右的宽度优先遍历,如果发现遍历到的结点等于 last,就该换行了。换行后将 last=nlast,继续下一行的打印,重复过程,直到遍历结束。
- 记二叉树的根节点为 root,设置临时变量 last 和 nlast。使 last=root、nlast=null。
- 申请一个空队列 queue,将二叉树的根结点放入队列中。
- 从队列中出队头结点 temp,判断其是否有左孩子,若有,放入队列中,将 nlast=temp.left。若有右孩子,也放入队列中,将 nlast=temp.right。
- 若 last==root,那么打印换行,并将 last=nlast。
- 重复步骤 3~4,直至队列为空,表示二叉树的按层打印结束。
private static int[][] ceng(TreeNode root) { List<ArrayList<Integer>> resultMap = new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> ceng = new ArrayList<Integer>(); Queue<TreeNode> queue = new LinkedList<TreeNode>(); TreeNode last = root; TreeNode nlast = null; queue.offer(root); while (!queue.isEmpty()) { root = queue.poll(); ceng.add(root.val); if (root.left != null) { queue.offer(root.left); nlast = root.left; } if (root.right != null) { queue.offer(root.right); nlast = root.right; } if (last==root) { last = nlast; resultMap.add(ceng); ceng = new ArrayList<Integer>(); } } // 转数组 int[][] result = new int[resultMap.size()][]; int i = 0; for (List<Integer> list : resultMap) { int[] temp = new int[list.size()]; int j = 0; for (Integer integer : list) { temp[j++] = integer; } result[i++] = temp; } return result;}
方法返回的是二维数组,一维代表二叉树的层,二维代表每一层所有的结点。
参考资料
[1] 数据结构与算法分析——Java语言描述, 5.5.4 - 二叉树的层次遍历
[2] 程序员面试代码指南, 第3章 - 二叉树的按层打印
数据结构——二叉树遍历之“层遍历”
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。